前面几章已经探讨了若干种分类器，包括决策树、贝叶斯分类器和神经网络。本章将引入线性分类器和核方法的概念，并以此为铺垫进而向大家介绍一种最为高阶的分类器，同时这也是目前仍然处于活跃状态的一个研究领域，我们称之为支持向量机(SVMs)。

不过站在 2024 的这个时间节点上，好像并不是很高阶了

婚介数据集 #

本章中将要使用的数据集基于假象的婚恋数据。 matchmaker.csv

如果仅仅根据年龄，我们可以获得如下的图

基本的线性分类 #

虽然线性分类是分类器中最简单的一种，但是这对于我们的后续讨论是一个很好的基础。线性分类的工作原理是寻找每个分类中所有数据的平均值，并构造一个代表该分类中心位置的点。然后我们就可以通过判断距离哪个中心点位置最近来对新的坐标点进行分类了。

首先我们需要一个函数计算分类的 均值点(average point) 本例的分类就是 0 和 1，代码 advancedclassify.py

def lineartrain(rows):
  averages={}
  counts={}
  
  for row in rows:
    # 得到类别
    cl=row.match
    
    # 初始化
    averages.setdefault(cl,[0.0]*(len(row.data)))
    counts.setdefault(cl,0)
    
    # 增加这个点到 averages 中
    for i in range(len(row.data)):
      averages[cl][i]+=float(row.data[i])
      
    # 增加计数
    counts[cl]+=1
    
  # 计算均值
  for cl,avg in averages.items():
    for i in range(len(avg)):
      avg[i]/=counts[cl]
  
  return averages

结果如下

{0: [26.914529914529915, 35.888888888888886], 1: [35.48041775456919, 33.01566579634465]}

我们在图上将其标记出来，划分数据的直线，位于两个点中间位置，左边的就更接近 0，右边的就更接近 1。

为了计算距离，我们可以采用 欧几里得距离 作为距离度量。这里用向量和点积。

• 向量: 具有大小和方向，标记为一个箭头，或者一个数字集合
• 点积: 两个向量的长度的乘积

def dotproduct(v1,v2):
  return sum([v1[i]*v2[i] for i in range(len(v1))])

点积还可以利用两个向量的长度乘积，再乘以两者夹角的余弦值。

分类算法可以推导出来是

转为代码就是

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

请记住这是一个线性分类器，所以它只找出了一条分界线来。这意味着，如果找不到一条划分数据的直线来，或者如果实际存在多条直线时，就如同前面那个年龄对比的例子中所呈现的那样，那么此时分类器将会得到错误的答案。在那个例子中，48岁与20岁的年龄对比实际上应该是“不相匹配”的结果，但是因为我们只找到了一条直线，而相应的坐标点又落在了这条直线的右侧，所以函数得出了“相匹配”的结论。在本章稍后的“理解核方法”一节中，将会学习如何对这一分类器进行改进，使其能够处理非线性分类。

分类特征 #

婚介数据集中既包含有数值数据，也包含有分类数据(categorical data)。‘一些像决策树这样的分类器不须要对数据作任何预处理，就可以同时应对这两种类型的数据，但是本章接下来要介绍的分类器只能处理数值型数据。为了解决这一问题，我们需要一种能够将数据转换成数值类型的方法，以使得分类器能够处理这些数据。

是否问题 #

如果是是否问题就很容易转换了。

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

家庭住址 #

这里其实考虑的是距离长短。因为需要 API 支持，这里就 SKIP

def milesdistance(a1,a2):
  return 0

构建新数据集 #

利用上面的一些函数，将对象变型成数字

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倍于观念之差。

def scaledata(rows):
  low=[999999999.0]*len(rows[0].data)
  high=[-999999999.0]*len(rows[0].data)
  # 寻找最大值和最小值
  for row in rows:
    d=row.data
    for i in range(len(d)):
      if d[i]<low[i]: low[i]=d[i]
      if d[i]>high[i]: high[i]=d[i]
  
  # 定义一个缩放函数
  def scaleinput(d):
     return [(d[i]-low[i])/(high[i]-low[i])
            for i in range(len(low))]
  
  # 缩放所有数据
  newrows=[matchrow(scaleinput(row.data)+[row.match])
           for row in rows]
  
  # 返回新数据和缩放函数
  return newrows,scaleinput

Kernel Methods 核方法 #

每个分类的均值点在哪儿呢？它们恰好都位于相同的位置！尽管大家都很清楚，任何位于圆圈内的都是X,位于圆圈外的都是O,但是线性分类器却无法识别这两个分类。

不过请试想一下，假如先对每一个x值和y值求平方，情况又会如何呢。原来位于(-1,2)处的坐标点现在将变成(1,4)，原来位于(0.5,1)处的坐标点现在将变成(0.25,1)，依此类推。新的坐标点分布情况如下页图98所示。所有的X现在都已经偏移到了图上的角落处，所有的O都则位于角落以外的区域。现在，要用一条直线来划分X和O已经变得非常容易了，并且任何时候只要有待分类的新数据，我们只须对x值和y值求平方，并观察其落于直线的哪一侧即可。

Kernel Trick 核技巧 #

核技法的思路是用一个新的函数来取代原来的点积函数，当借助某个映射函数将数据第一次变换到更高维度的坐标空间时，新函数将会返回高维度坐标空间内的点积结果。此处，就变换方法的数量而言并没有任何的限制，但是在现实中我们其实只会采用少数几种变换方法。其中备受人们推崇的一种方法（也是将要在此处采用的方法)：被称为 径向基函数 (radial-basis function)

def rbf(v1,v2,gamma=10):
  dv=[v1[i]-v2[i] for i in range(len(v1))]
  l=veclength(dv)
  return math.e**(-gamma*l)

现在，我们需要一个新的函数，用以计算坐标点在变换后的空间中与均值点间的距离。遗憾的是，目前的均值点是在原始空间中计算得到的，因此无法在此处直接使用它们一事实上，根本无法计算均值点，因为实际上不会在新的坐标空间中计算坐标点的位置。所幸的是，先对一组向量求均值，然后再计算均值与向量A的点积结果，与先对向量A与该组向量中的每一个向量求点积，然后再计算均值，在效果上是完全等价的。

那么代码可以编写为

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

支持向量机 #

还有一种新困境

我们注意到，有两个坐标点因为与其他大多数数据相比，都更加接近于利用均值点计算得到的分界线，所以它们被划归到了错误的分类。此处的问题在于，因为大多数数据都是远离分界线的，所以判断坐标点的分类与是否位于直线的某一侧并没有太大的关系。

支持向量机是广为人知的一组方法的统称，借助于它我们可以构造出解决上述问题的分类器。其思路就是，尝试寻找一条尽可能远离所有分类的线，这条线被称为最大间隔超平面(maximum-margin hyperplane),如下图所示。

此处选择分界线的依据是：寻找两条分别经过各分类相应坐标点的平行线，并使其与分界线的距离尽可能的远。同样，对于新的数据点，可以通过观察其位于分界线的哪一侧来判断其所属的分类。请注意，只有位于间隔区边缘的坐标点才是确定分界线位置所必需的，我们可以去掉其余所有的数据，而分界线依然还会处于相同的位置。

线附近的坐标点称做支持向量。寻找支持向量，并利用支持向量来寻找分界线的算法便是支持向量机。