本实验的内容基于婚介的背景,使用到的数据集可以在https://github.com/GreenGitHuber/Programming-Collective-Intelligence/tree/master/chapter9_Advance%20Classification 上面下载。
基本的线性分类器:
它的工作原理是寻找到所有数据的均值,并且构造一个可以代表该分类的中心位置的点。然后我们就可以通过判断距离哪一个中心点近来对新的坐标点进行分类。
首先我们只考虑年龄这一因素,使用agesonly.cvs这个数据集,可视化该数据集:
为了计算两个不同类的中心点,我们需要一个计算分类的均值点:
#基本的线性分类
def lineartrain(rows):
averages={}
counts={}
for row in rows:
cl = row.match
averages.setdefault(cl,[0.0]*(len(row.data)))
counts.setdefault(cl,0)
for i in range(len(row.data)):
averages[cl][i]+=row.data[i]
counts[cl]+=1
for cl,avg in averages.items():
for i in range(len(avg)):
avg[i]/=counts[cl]
return averages
运行上面的函数,可以求得我们需要的均值点:
求得“不匹配(no match)”和“匹配(match)”这两类的均值点以后,当一个新的年龄数据来的时候,只需要判断该点离哪一个均值点更近就可以了。
计算一个坐标点和均值点的远近程度,有很多种方法,有欧几里得距离,这里我们采用的是向量和点积。
在文件中添加计算向量点积的函数:
#向量点积
def dotproduct(v1,v2):
return sum([v1[i]*v2[i] for i in range(len(v1))])
寻找分类的公式为:class=sign((X-(M0-M1)/2).(M0-M1))
我们将上述公式化简,然后编写下面的代码添加到文件中:
def dpclassify(point,avgs):
b=(dotproduct(avgs[1],avgs[1])-dotproduct(avgs[0],avgs[0]))/2
y=dotproduct(point,avgs[0])-dotproduct(point,avgs[1])+b
if y>0: return 0
else: return 1
这里我们只使用了年龄这一特征,其实实际生活中影响结果有很原因,比如说:兴趣,是否要孩子,距离等等,但是这些数据不是数值数据,不能直接拿来使用,所以要使用这些数据需要我们将这些分类数据进行数值化:
def yesno(v):
if v=='yes': return 1
elif v=='no': return -1
else: return 0
#兴趣列表
def matchcount(interest1, interest2):
l1 = interest1.split(':')
l2 = interest2.split(':')
x = 0
for v in l1:
if v in l2: x += 1
return x
#计算距离,因为我们无法使用Yahoo!Maps,所以就直接写了一个空函数
def milesdistance(a1,a2):
return 0.1
#构造新的数据集,利用我们上面准备的数据处理方式
def loadnumerical():
oldrows=loadmatch('matchmaker.csv')
newrows=[]
for row in oldrows:
d=row.data
data=[float(d[0]),yesno(d[1]),yesno(d[2]),
float(d[5]),yesno(d[6]),yesno(d[7]),
matchcount(d[3],d[8]),
milesdistance(d[4],d[9]),
row.match]
newrows.append(matchrow(data))
return newrows
对数据进行缩放处理
当我们只有年龄这一特征的时候,保持数据原始状态的均值和距离是没有问题的,但是当有很多类型的变量,每一种变量与年龄也没有可比性,相比较而言它们的值要小很多。比如说双方是否要小孩——介于1和-1之间,那么这个变量最大的差值就是2——而对于年龄这个变量,两人的年纪相差6岁的很常见。如果不对我们的数据进行处理,那么年龄之差将会被视为3倍于观念之差.
为了解决这一问题,一种推荐的做法是,将所有的数据缩放到同一尺度,从而使每一个变量上的差值都具有可比性。将数据进行相应的缩放,使其值介于0和1之间。
def scaledata(rows):
# low = 999999999.0
# high = -999999999.0
#找到每一行数据当中的最小最大值
for row in rows:
low = 999999999.0
high = -999999999.0
d = row.data
for i in range(len(d)):
if d[i] < low: low = d[i]
if d[i] > high: high = d[i]
# 对数据进行缩放处理的函数
def scaleinput(d):
return [(d[i] - low) / (high - low)#将结果减去最小值,这样值域的范围就变为以0为起点,除以最大值和最小值的差,就将所有的数据转化为介于0-1的值
for i in range(len(d))]
# 对所有的数据进行缩放处理
newrows = [matchrow(scaleinput(row.data) + [row.match])
for row in rows]
#返回新的数据和缩放处理函数
return newrows, scaleinput
理解核方法
问题1:
SVM显然是线性分类器,但数据如果根本就线性不可分怎么办?
解决方案1:
数据在原始空间(称为输入空间)线性不可分,但是映射到高维空间(称为特征空间)后很可能就线性可分了。
问题2:
映射到高维空间同时带来一个问题:在高维空间上求解一个带约束的优化问题显然比在低维空间上计算量要大得多,这就是所谓的“维数灾难”。
解决方案2:
于是就引入了“核函数”,核函数的价值在于它虽然也是讲特征进行从低维到高维的转换。
从上图我们可以看出一个理想的分界应该是一个“圆圈”而不是一条线(超平面)。这个问题我们就采用了核函数的方法来解决,因为我们这里主要是应用,至于核函数的原理我们这里就不具体展开,要是感兴趣的同学可以看这篇文章,讲的不错→https://wizardforcel.gitbooks.io/dm-algo-top10/content/svm-4.html
我们实验采用了径向基函数(radial-basis function),这个函数和点积函数很相似,接受两个向量,并且返回一个标量值。与点积函数不同的是,径向基函数是一个非线性的函数,所以它可以把数据映射到一个更加复杂的空间当中,将下面这个函数添加到文件当中:
#定义一个径向基函数,径向基函数和点积函数很相似,但是和点积函数不同的是径向基函数是一个__非线性__的
def rbf(v1,v2,gamma=10):
dv=[v1[i]-v2[i] for i in range(len(v1))]
l=sum(dv)
return math.e**(-gamma*l)
利用这个径向基函数,我们定义下面这个非线性分类器:
#定义一个非线性分类器
def nlclassify(point, rows, offset, gamma=10):
sum0 = 0.0
sum1 = 0.0
count0 = 0
count1 = 0
for row in rows:
if row.match == 0:
sum0 += rbf(point, row.data, gamma)
count0 += 1
else:
sum1 += rbf(point, row.data, gamma)
count1 += 1
y = (1.0 / count0) * sum0 - (1.0 / count1) * sum1 + offset
if y > 0:
return 0
else:
return 1
到目前为止,我们通过一个线性分类器发现它的不足,然后介绍了核函数。接下去,我们会介绍支持向量机(SVM)。