《集体智慧编程》读书笔记 — Chapter 9 高阶分类:核函数与SVM_1

本实验的内容基于婚介的背景,使用到的数据集可以在https://github.com/GreenGitHuber/Programming-Collective-Intelligence/tree/master/chapter9_Advance%20Classification 上面下载。

基本的线性分类器:

它的工作原理是寻找到所有数据的均值,并且构造一个可以代表该分类的中心位置的点。然后我们就可以通过判断距离哪一个中心点近来对新的坐标点进行分类。
首先我们只考虑年龄这一因素,使用agesonly.cvs这个数据集,可视化该数据集:


年龄分布.png

为了计算两个不同类的中心点,我们需要一个计算分类的均值点:

#基本的线性分类
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

运行上面的函数,可以求得我们需要的均值点:

利用均值.png

求得“不匹配(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
数据数值化.png
对数据进行缩放处理

当我们只有年龄这一特征的时候,保持数据原始状态的均值和距离是没有问题的,但是当有很多类型的变量,每一种变量与年龄也没有可比性,相比较而言它们的值要小很多。比如说双方是否要小孩——介于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:

于是就引入了“核函数”,核函数的价值在于它虽然也是讲特征进行从低维到高维的转换。

有一个分类对其他分类呈现环绕状.png

从上图我们可以看出一个理想的分界应该是一个“圆圈”而不是一条线(超平面)。这个问题我们就采用了核函数的方法来解决,因为我们这里主要是应用,至于核函数的原理我们这里就不具体展开,要是感兴趣的同学可以看这篇文章,讲的不错→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)。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,839评论 6 482
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,543评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 153,116评论 0 344
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,371评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,384评论 5 374
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,111评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,416评论 3 400
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,053评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,558评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,007评论 2 325
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,117评论 1 334
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,756评论 4 324
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,324评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,315评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,539评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,578评论 2 355
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,877评论 2 345

推荐阅读更多精彩内容