感知机

                   

                      

                      

                       

                         

                                  

                        

from numpy import *  
import operator
import os



# create a dataset which contains 3 samples with 2 classes  
def createDataSet():  
    # create a matrix: each row as a sample  
    group = array([[3,3], [4,3], [1,1]])  
    labels = [1, 1, -1] # four samples and two classes  
    return group, labels

#classify using perceptron
def perceptronClassify(trainGroup,trainLabels):
    global w, b
    isFind = False  #the flag of find the best w and b
    numSamples = trainGroup.shape[0]
    mLenth = trainGroup.shape[1]
    w = [0]*mLenth
    b = 0
    while(not isFind):
        for i in xrange(numSamples):
            if cal(trainGroup[i],trainLabels[i]) <= 0:
                print w,b
                update(trainGroup[i],trainLabels[i])
                break    #end for loop
            elif i == numSamples-1:
                print w,b
                isFind = True   #end while loop


def cal(row,trainLabel):
    global w, b
    res = 0
    for i in xrange(len(row)):
        res += row[i] * w[i]
    res += b
    res *= trainLabel
    return res
def update(row,trainLabel):
    global w, b
    for i in xrange(len(row)):
        w[i] += trainLabel * row[i]
    b += trainLabel

createDataSet()
perceptronClassify(g,l)

 

                        

                       

                      

from numpy import *  
import operator
import os



# create a dataset which contains 3 samples with 2 classes  
def createDataSet():  
    # create a matrix: each row as a sample  
    group = array([[3,3], [4,3], [1,1]])  
    labels = [1, 1, -1] # four samples and two classes  
    return group, labels

#classify using DualPerception
def dualPerceptionClassify(trainGroup,trainLabels):
    global a,b
    isFind = False
    numSamples = trainGroup.shape[0]
    #mLenth = trainGroup.shape[1]
    a = [0]*numSamples
    b = 0
    gMatrix = cal_gram(trainGroup)
    while(not isFind):
        for i in xrange(numSamples):
            if cal(gMatrix,trainLabels,i) <= 0:
                cal_wb(trainGroup,trainLabels)
                update(i,trainLabels[i])
                break
            elif i == numSamples-1:
                cal_wb(trainGroup,trainLabels)
                isFind = True
    

# caculate the Gram matrix
def cal_gram(group):
    mLenth = group.shape[0]
    gMatrix = zeros((mLenth,mLenth))
    for i in xrange(mLenth):
        for j in xrange(mLenth):
            gMatrix[i][j] =  dot(group[i],group[j])
    return gMatrix

def update(i,trainLabel):
    global a,b
    a[i] += 1
    b += trainLabel

def cal(gMatrix,trainLabels,key):
    global a,b
    res = 0
    for i in xrange(len(trainLabels)):
        res += a[i]*trainLabels[i]*gMatrix[key][i]
    res = (res + b)*trainLabels[key]
    return res

#caculator w and b,then print it
def cal_wb(group,labels):
    global a,b
    w=[0]*(group.shape[1])
    h = 0
    for i in xrange(len(labels)):
        h +=a[i]*labels[i]
        w +=a[i]*labels[i]*group[i]
    print w,h

 

createDataSet()
dualPerceptionClassify(g,l)

                      

感知机算法分析：

　　（1）感知机二分类模型为  f(x) = sign(w.x+b)  分类超平面为w.x+b=0

　　（2） 感知机学习策略是极小化损失函数  minL(w,b)  损失函数对应于误分类点到超平面之间的距离

　　（3）感知机学习算法是基于随机梯度下降算法的对损失函数的最优化算法，有原始形式，对偶形式。

　　（4）当数据是线性可分的时候，感知机学习算法是收敛的，即经过有限次迭代之后，总能找到一个超平面正确进行分类。此外，感知机学习算法存在无穷多个解，其解由于初值以及迭代顺序的不同而可能不同。

 

补充： 为什么要用对偶形式

对偶形式的目的是降低运算量，但是并不是在任何情况下都能降低运算量，而是在特征空间的维度很高时才起到作用。

不妨设特征空间是 ， 很大，一共有 个训练数据， 相对 很小。我们考虑原始形式的感知机学习算法，每一轮迭代中我们至少都要判断某个输入实例是不是误判点，既对于 ,是否有 。这里的运算量主要集中在求输入实例 和权值向量 的内积上， 的时间复杂度，由于特征空间维度很高，所以这很慢。

而在对偶形式的感知机学习算法中，对于输入实例 是否误判的条件变换为 。注意到这里所有输入实例都仅仅以内积的形式出现，所以我们可以预先计算输入实例两两之间的内积，得到所谓的Gram矩阵 。这样一来每次做误判检测的时候我们直接在Gram矩阵里查表就能拿到内积 ，所以这个误判检测的时间复杂度是 。

也就是说，对偶形式的感知机，把每轮迭代的时间复杂度的数据规模从特征空间维度 转移到了训练集大小 上，那么对于维度非常高的空间，自然就能提升性能了。