监督学习和非监督学习

利用样本输入和期望输出来学习如何预测的技术称为监督学习。非监督学习的目标是采集数据，然后从中找出不同的群组。

单词向量

为聚类算法准备数据的常见做法是定义一组公共的数值型属性，我们可以利用这些属性对数据项进行比较。

对订阅源中的单词进行计数

本章我们将会对两个数据集进行处理，第一个数据集中，被用来聚类的是排名在前120位的一系列博客，对这些博客进行聚类，为了对这些博客进行聚类，我们需要的是一组指定的词汇在每个博客订阅源中出现的次数，有关这一数据的一个小范围的子集，如下表所示

单词在博客中出现的次数

|博客|”china“|“kids”|“music”|“yahoo”|

|------|---------|-------|----------|-----------|

|Gothamist|0|3|3|0|

|GigaOM|6|0|0|2|

|Quick Online Tips|0|2|2|22|

根据单词出现的频度对博客进行聚类，或许可以帮助我们分析出是否存在这个一类博客用户，这些人撰写相似的主题，或者在写作风格上十分相似。这样的分析结果对于搜索、分类和数据挖掘当前大量的在线博客而言，可能是非常有价值的。

对数据源中的单词进行计数

几乎所有的博客都可以在线阅读，或者通过RSS订阅源进行阅读。RSS订阅源是一个包含博客及其所有文章条目信息的简单的XML文档。为了给每个博客的单词进行计数，首先第一步就是要解析这些订阅源。有一个非常不错的程序能够完成这项工作，它就是Universal Feed Parser，它可以很轻松的从任何RSS或Atom订阅源中得到标题、链接和文章的条目，可以从http://www.feedparser.org 上下载它。

第二步，编写一个从订阅源中提取所有单词的函数。建立generatefeedvector.py，加入如下代码：

import feedparserimport redef getwordcounts(url):    #解析订阅源    d=feedparser.parse(url)    wc={}        #循环遍历所有的文章条目    for e in d.entries:        if 'summary' in e : summary=e.summary        else: summary=e.description                #提取一个单词列表        words=getwords(e.title+''+summary)        for word in words:            wc.setdefault(word,0)            wc[word]+=1    return d.feed.title,wc

每个RSS和Atom订阅源都会包含一个标题和一组文章条目。通常，每个文章条目都有一段摘要或者包含条目中实际文本的描述性标签。函数getwordcounts将摘要传给函数getwords，后者会将其中所有的HTML标记剥离掉，并以非字母字符作为分隔符拆分出单词，再讲结果以列表的形式加以返回。将getwords函数加入generatefeedvector.py中：

def getwords(html):    #去除所有HTML标记    txt=re.compile(r'<[^>]+>').sub('',html)    #利用所有非字母字符拆分出单词    words=re.compile(r'[^A-Z^a-z]+').split(txt)    #转换成小写形式    return [word.lower() for word in words if word!='']

订阅源列表可以在http://kiwitobes.com/clusters/feedlist.txt下载。这是一个普通的文本文件，每一行对应一个url。

generatefeedvector.py文件中的主体代码循环遍历订阅源并生成数据集，代码的第一部分遍历feedlist.txt文件中的每一行，然后生成针对每个博客单词统计，以及出现这些单词的博客数目（apcount）。请将下列代码加入generatefeedvector.py文件的末尾。

apcount={}wordcounts={}f=open('feedlist.txt','r')feedlist=[line for line in f] f.close()for feedurl in feedlist:    title,wc=getwordcounts(feedurl)    wordcounts[title]=wc    for word,count in wc.items():        apcount.setdefault(word,0)        if count>1:            apcount[word]+=1

下一步，我们建立一个单词列表，将其实际用于针对每个博客的单词计数。因为像‘the’这样的单词几乎到处都是，而像“flim-flame”这样的单词则只可能只出现在个别微博中，所有只选择介于某个百分比范围的单词，我们可以减少需要考察的单词总量。这里选择10%的下届，50%的上届。这个数值可以调整。

wordlist=[]for w,bc in apcount.items():    frac=float(bc)/len(feedlist)    if frac>0.1 and frac<0.5: wordlist.appenf(w)

最后，我们利用上述单词列表和微博列表来建立一个文本文档，其中包含一个大的矩阵，记录针对每个微博的所有单词的统计情况。

out=open('blogdata.txt','w')out.write('blog')for word in wordlist: out.write('\t%s' %word)out.write('\n')for blog,wc in wordcounts.items():    out.write(blog)    for word in wordlist:        if word in wc: out.write('\t%s'%wc[word])        else: out.write('\t0')    out.write('\n')

分级聚类

分级聚类通过连续不断的将最为相似的群组两两结合，来构造出一个群组的层级结构。其中的每个群组都是从单一元素开始的，在本章例子中，每个单一元素就是博客。在每次迭代过程中，分级聚类算法会计算每两个群组之间的距离，将距离最近的两个群组合并成一个新的群组，这一过程会一直重复下去，直到只剩下一个群组为止。

树状体能够帮助我们有效地确定一个聚类中各元素间的相似程度，并以此来指示聚类的紧密程度。

本节将示范如何对博客数据集进行聚类，以构造博客的层级结构；如果构建成功，我们将实现按主题对博客进行分组。

首先，我们需要一个方法来加载数据文件。建立一个名为clusters.py的文件，将下列代码加入其中。

def readfile(filename):    f=open(filename,'r')  #以读的方式打开文件        lines=f.readlines()    #将文件中的数据读入lines列表    f.close()        #第一行是列标题    colnames=lines[0].strip().split('\t')[1:]   #将第一行数据读入colnames列表    rownames=[]    data=[]    for line in lines[1:]:        p=line.strip().split('\t')        #每一行的第一列是行名        rownames.append(p[0])        #剩余部分就是该行所对应的数据        data.append([float(x) for x in p[1:]])    return rownames,colnames,data

下一步就是来定义紧密度，此处用皮尔逊相关度。皮尔逊相关度的计算结果在两者完全匹配的情况下为1.0，而在两者毫无关系的情况下则为0.0，代码最后一行是用1.0减去皮尔逊相关度，这样做的目的是为了让相似度越大的两个元素之间的距离变得更小。

from math import sqrtdef pearson(v1,v2):    #简单求和    sum1=sum(v1)    sum2=sum(v2)        #求平方和    sum1Sq=sum([pow(v,2) for v in v1])    sum2Sq=sum([pow(v,2) for v in v2])        #求乘积之和    pSum=sum(v1[i]*v2[i] for i in range(len(v1)))        #计算r（Pearson score）    num=pSum-(sum1*sum2/len(v1))    den=sqrt((sum1Sq-pow(sum1,2)/len(v1))*(sum2Sq-pow(sum2,2)/len(v2)))    if den==0:        return 0    return 1.0-num/den

分级聚类算法中的每一个聚类，可以是树中的枝结点，也可以是与数据集中实际数据行相对应的叶节点。每一个聚类还包含了指示其位置的信息，这一信息可以是来自叶节点的行数据，也可以是来自枝节点的经合并后的数据。我们可以新建一个bicluster类，将所有这些属性放在其中，并以此来描述这棵层级树。在cluster.py中新建一个类，以代表‘聚类’这一类型。

class bicluster:    def __init__(self,vec,left=None,right=None,distance=0,id=None):        self.left=left        self.right=right        self.vec=vec        self.id=id        self.distance=distance

分级聚类算法以一组对应于原始数据项的聚类开始。函数的主循环部分会尝试每一组可能的配对并计算它们的相关度，以此来找出最佳配对。最佳配对的两个聚类会合并成一个新的聚类。新生成的聚类中所包含的数据，等于将两个旧聚类的数据求平均值之后得到的结果。这一过程会一直重复下去，直到只剩下一个聚类为止。将hcluster算法加入cluster.py文件中。

def hcluster(rows,distance=pearson):    distances={}    currentclustid=-1        #最开始的聚类就是数据集中的行    clust=[bicluster(rows[i],id=i) for i in range(len(rows))]    while len(clust)>1:        lowestpair=(0,1)        closest=distance(clust[0].vec,clust[1].vec)                #遍历每一个配对，寻找最短距离        for i in range(len(clust)):            for j in range(i+1,len(clust)):                #用distance来缓存距离的计算值                if (clust[i].id,clust[j].id) not in distances:                    distances[(clust[i].id,clust[j].id)]=distance(clust[i].vec,clust[j].vec)                                    d=distances[(clust[i].id,clust[j].id)]                                if d

因为每个聚类都指向构造该聚类时被合并的另两个聚类，所以我们可以递归搜索由该函数最终返回的聚类，以重建所有的聚类及叶节点。

为了检视执行的结果，我们编写一个简单的函数来递归遍历聚类树，并将其以类似文件系统层级结构的形式打印出来。将printcluster函数添加到cluster.py中。

def printclust(clust,labels=None,n=0):    #利用缩进来建立层级布局    for i in range(n): print(' ',)     if clust.id<0:        #负数标记代表这是一个分支        print('-')    else:        #正数标记代表这是一个叶节点        if labels==None: print(clust.id)        else: print(labels[clust.id])    #现在开始打印右侧分支和左侧分支    if clust.left!=None: printclust(clust.left,labels=labels,n=n+1)    if clust.right!=None:printclust(clust.right,labels=labels,n=n+1)

调用上述函数：

blognames,words,data=readfile('blogdata.txt')clust=hcluster(data)printclust(clust,labels=blognames)

绘制树状图

借助树状图，可以清晰地理解聚类。

由于我们的树状图是图形的，并且要被保存成JPG格式，所以需要下载Python Imaging Library（PIL）

PIL是针对windows平台的安装程序和一个针对其他平台的源代码发布包。借助PIL我们可以轻松地生成带有文本和线条的图形。这是构造树状图所必需的。

将相关import加入到clusters.py的开始处。

from PIL import Image,ImageDraw

首先利用一个函数来返回给定聚类的总体宽度。如果聚类是一个叶子节点，则其高度为1；否则为所有分支高度之和。我们可以简单地将其定义成一个递归函数，并加入到clusters.py中：

def getheight(clust):    #这是一个叶节点么？若是，则高度为1    if clust.left==None and clust.right==None:return 1    else:        return getheight(clust.left)+getheight(clust.right)

我们还需要知道根节点的总体误差。因为线条的长度会根据每个节点的误差进行调整，所以我们需要根据总的误差值生成一个缩放因子。一个节点的误差深度等于其下所属的每个分支的最大误差。

def getdepth(clust):    #一个叶节点的距离是0.0     if clust.left==None and clust.right==None: return 0    else:        #一个枝结点的距离等于左右两侧分支中距离较大者加上该枝结点自身的距离        return max(getdepth(clust.left),getdepth(clust.right))+clust.distance

函数drawdendrogram为每一个最终生成的聚类创建一个高度为20像素、宽度固定的图片。其中的缩放因子是由固定宽度除以总的深度值得到的。该函数为图片建立相应的draw对象，然后在根节点的位置调用drawnode函数，并令其处于整幅图片左侧正中间的位置。

def drawdendrogram(clust,labels,jpeg='clusters.jpg'):    #高度和宽度    h=getheight(clust)*20    w=1200    depth=getdepth(clust)        #由于宽度值是固定的，所以我们需要对距离值做相应的调整    scaling=float(w-1500)/depth    #新建一个白色背景的图片    img=Image.new('RGB',(w,h),(255,255,255))    draw=ImageDraw.Draw(img)        draw.line((0,h/2,10,h/2),fill=(255,0,0))        #画第一个点    drawnode(draw,clust,10,(h/2),scaling,labels)    img.save(jpeg,'JPEG')

此处最为重要的是drawnode函数，它接受一个聚类及其位置作为输入参数。函数取到子节点的高度，并计算这些节点所在的位置，然后用线条将它们连接起来--包括一条长长的垂直线和两条水平线。水平线的长度是由聚类的误差决定的。线条越长就越说明，合并在一起的两个聚类差别越大，而线条越短则说明两个聚类的相似度很高。请将drawnode函数加入到clusters.py中。

def drawnode(draw,clust,x,y,scaling,labels):    if clust.id<0:        h1=getheight(clust.left)*20        h2=getheight(clust.right)*20        top=y-(h1+h2)/2        bottom=y+(h1+h2)/2        #线的长度        ll=clust.distance*scaling        #聚类到其子节点的垂直线        draw.line((x,top+h1/2,x,bottom-h2/2),fill=(255,0,0))                #连接到左侧节点的水平线        draw.line((x,top+h1/2,x+ll,top+h1/2),fill=(255,0,0))                #连接右侧节点的水平线        draw.line((x,bottom-h2/2,x+ll,bottom-h2/2),fill=(255,0,0))                #调用函数绘制左右节点        drawnode(draw,clust.left,x+ll,top+h1/2,scaling,labels)        drawnode(draw,clust.right,x+ll,bottom-h2/2,scaling,labels)            else:        #如果这是一个叶子节点，则绘制节点的标签        draw.text((x+5,y-7),labels[clust.id],(0,0,0))

加入如下的代码运行,将生成一个包含树状图的blogclust.jpg文件：

blognames,words,data=readfile('blogdata.txt')clust=hcluster(data)drawdendrogram(clust,blognames,jpeg='blogclust.jpg')

列聚类

同时在行和列上对数据进行聚类常常是很有必要的。在博客数据中，列代表的是单词，知道哪些单词时常会结合在一起使用，可能是非常有意义的。

要利用此前编好的函数实现针对列的聚类，最容易的一种方式就是将整个数据集转置，使列变成行。其中每一行都对应一个数字，这组数字指明某个单词在每篇博客中出现的次数。请将下列函数加入到clusters.py中。

def rotatematrix(data):    newdata=[]    for i in range(len(data[0])):        newrow=[data[j][i] for j in range(len(data))]        newdata.append(newrow)    return newdata

现在我们可以将矩阵进行转置，然后执行同样的聚类操作，并将最终的结果以树状图的形式绘制出来。要记住，矩阵已经被转置，所以现在的标签已经不再是博客，而变成了单词。

blognames,words,data=readfile('blogdata.txt')rdata=rotatematrix(data)wordclust=hcluster(rdata)drawdendrogram(wordclust,labels=words,jpeg='wordclust.jpg')

关于聚类有一点很重要：当数据项的数量比变量多的时候，出现无意义聚类的可能性就会增加。由于单词的数量比博客多很多，因此我们会发现，在博客聚类中出现的模式要比单词聚类中出现的更为合理。

K-均值聚类

K-均值聚类算法首先会随机确定k个中心位置（位于空间中代表聚类中心的点），然后将各个数据项分配给最邻近的中心点。待分配完成之后，聚类中心就会移到分配给该聚类的所有节点的平均位置处，然后整个分配过程重新开始，这一过程会重新重复下去，直到分配过程不再发生变化为止。下图显示这一过程。

代码如下，将其加入到clusters.py中。

def kcluster(rows,distance=pearson,k=4):    #确定每个点的最小值和最大值    ranges=[(min([row[i] for row in rows]),max([row[i] for row in rows])) for i in range(len(rows[0]))]    #随机创建k个中心点    clusters=[[random.random()*(ranges[i][1]-ranges[i][0])+ranges[i][0] for i in range(len(rows[0]))] for j in range(k)]        lastmatches=None        for t in range(100):        print('Iteration %d'%t)        bestmatches=[[] for i in range(k)]        #在每一行中寻找距离最近的中心点        for j in range(len(rows)):            row=rows[j]            bestmatch=0            for i in range(k):                d=distance(clusters[i],row)                if d
    
     0:                for rowid in bestmatches[i]:                    for m in range(len(rows[rowid])):                        avgs[m]+=rows[rowid][m]                for j in range(len(avgs)):                    avgs[j]/=len(bestmatches[i])                clusters[i]=avgs             return bestmatches
    

调用该函数，运行代码。

blognames,words,data=readfile('blogdata.txt')kclust=kcluster(data,k=10)blogclust=[[blognames[r] for r in range(len(kclust[i]))] for i in range(len(kclust))]print(blogclust)

针对偏好的聚类

我们可以从网站上获取越来越多的数据，而所有这些数据都是网站用户无偿贡献的。在这些网站中有一个叫做Zebo（。

获取数据和准备数据

本节将介绍如何利用zebo网点来构造数据集，如何从网点将大量网页下载到本地加以解析，并从中提取每位用户希望拥有的物品。

Beautiful Soup

Beautiful Soup是一个解析网页和构造结构化数据表达形式的优秀函数库。它允许我们利用类型（type）、ID，或者任何其他的属性来访问网页内的任何元素，并获取到代表其内容的字符串。Beautiful Soup还可以很好地处理包含不规范HTML标记的Web页面，当我们根据站点的内容来构造数据集时，这一点是非常有用的。

在Anaconda Prompt中使用conda install beautifulsoup4安装该函数库。然后就可以直接使用它。

import urllibfrom bs4 import BeautifulSoup    #要导入 bs4 库c=urllib.request.urlopen('http://kiwitobes.com/wiki/Programming_language.html')soup=BeautifulSoup(c.read())links=soup('a')print(links)

要构造一个soup对象——这是Beautiful Soup描述Web网页的方式——只需要利用网页内容对其进行初始化即可。我们可以将标签类型作为参数来调用soup，比如上例中的‘a’，调用的结果将返回一个属于该标签类型的对象列表。其中的每一个对象也都是可访问的（addressable），我们可以逐层深入地访问到对象的属性，以及其下所属的其他对象。

收集来自zebo的结果

在Zebo上搜索到的网页，其结构是相当复杂的，但是我们很容易就可以判断出网页的哪些部分对应于物品的列表，因为他们都带有名为bgverdanasmall的CSS类。我们可以利用这一点来提取网页中的重要数据。请新建一个名为downloadzebodata.py的文件，并将下面的代码加入其中：

import urllibfrom bs4 import BeautifulSoup    #要导入 bs4 库import rechare=re.compile(r'[!-\.&]')   #将正则化表达式编译成模式对象itemowners={}#去除的单词dropwords=['a','new','some','more','my','own','the','many','other','another']currentuser=0for i in range(1,51):    #搜索“用户希望拥有的物品”所对应的URL    c=urllib.request.urlopen('http://member.zebo.com/Main?event_key=USERSEARCH&wiowiw=wiw&keyword=car&page=%d'%(i))    soup=BeautifulSoup(c.read())    for td in soup('td'):        #寻找带有bgverdanasmall类的表格单元格        if('class' in dict(td.attrs) and td['class']==bgverdanasmall):            items=[re.sub(chare,'',a.contents[0].lower()).strip() for a in td('a')]            for item in items:                #去除多余的单词                txt=''.join([t for t in item.split('') if t not in dropwords])                if len(txt)<2:continue                itemowners.setdefault(txt,{})                itemowners[txt][currentuser]=1            currentuser+=1

上述代码将下载和解析从Zebo上搜索到的包含“用户希望拥有的物品”的前50个页面，因为所有物品的文字都是随意输入的，所以我们需要进行大量的清理工作，其中包括去除像“a”和“some”这样的单词，去除标点符号，以及将所有文本转换为小写。

待完成上述工作之后，代码首先会构造一个列表，其中包含的是超过5个人都希望拥有的物品，然后再构造一个以匿名用户为列、以物品为行的矩阵，最后再将该矩阵写入一个文件。将下列代码加入到downloadzebodata.py文件中。

out=file('zebo.txt','w')out.write('Item')for user in range(0,currentuser): out.write('\tU%d' % user)out.write('\n')for item,owners in itemowners.items():    if len(owners)>10:        out.write(item)        for user in range(0,currentuser):            if user in owners:out.write('\t1')        else:out.write('\t0')    out.write('\n')

运行程序生成一个与博客数据集相同格式的名为zebo.txtd 文件。和博客数据集相比，此处唯一的区别在于没有了计数，如果一个人希望拥有某件商品，那么我们将其标记为1，否则就标记为0.

定义距离度量标准

Tanimoto系数代表的是交集（只包含那些在两个集合中都出现的项）和并集（包含所有出现于任一集合中的项）比率。利用如下两个向量，我们可以很容易的定义出这样的向量。

def tanimoto(v1,v2):    c1,c2,shr=0,0,0    for i in range(len(v1)):        if v1[i]!=0:c1+=1        if v2[i]!=0:c2+=1        if v1[i]!=0 and v2[i]!=0:shr+=1    return 1.0-(float(shr)/(c1+c2-shr))

上述代码将返回一个介于1.0到0.0之间的值，其中1.0代表不存在同时喜欢两件物品的人，而0.0代表所有人都喜欢两个向量中的物品。

对结果进行聚类

将tanimoto和下面的代码加入到clusters.py 运行。

wants,people,data=readfile('zebo.txt')clust=hcluster(data,distance=tanimoto)drawdendrogram(clust,wants)

上述代码会生成一个新的文件clusters.py，其中包含的聚类反映了人们希望拥有的物品。

以二维形式展示数据

在本章中，我们已经采用一种程式化的数据可视化表达方法，在二维空间中为大家演示了聚类算法的运用，利用不同物品间的图上距离来指示他们彼此间的差异。由于大多数真实生活的例子中，我们所要聚类的内容不只包含两个数值，所以我们不可能按照前面的方法来采集数据并以二维的形式将其描绘出来。但是，为了弄明白不同物品之间的关系，将它们绘制在一页纸上，并且用距离的远近来表达相似程度，又是一种非常有效的方法。

实现这种功能的函数接收一个数据向量作为参数，并返回一个只包含两列向量的函数，即数据项在二维图上的X坐标和Y坐标，将该函数加入到clusters.py中

def scaledown(data,distance=pearson,rate=0.01):    n=len(data)        #每一对数据项之间的真实距离    realdist=[[distance(data[i],data[j]) for j in range(n)] for i in range(0,n)]    outersum=0.0    #随机初始化节点在二维空间中的起始位置    loc=[[random.random(),random.random()] for i in range(n)]    fakedist=[[0.0 for i in range(n)] for j in range(n)]        lasterror=None    for m in range(1000):        #寻找投影后的距离        for i in range(n):            for j in range(n):                fakedist[i][j]=sqrt(sum([pow(loc[i][x]-loc[j][x],2) for x in range(len(loc[i]))]))                        #移动节点        grad=[[0.0,0.0] for i in range(n)]        totalerror=0        for k in range(n):            for j in range(n):                if k==j:continue                #误差等于目标距离与当前距离的差值的百分比                errorterm=(fakedist[j][k]-realdist[j][k])/realdist[j][k]                                           #每个节点都需要根据误差的多少，按比例移离或移向其他节点                grad[k][0]+=((loc[k][0]-loc[j][0])/fakedist[j][k])*errorterm                grad[k][1]+=((loc[k][1]-loc[j][1])/fakedist[j][k])*errorterm                                #记录总的误差值                totalerror+=abs(errorterm)        print(totalerror)                #如果节点移动之后的情况变得更糟，则程序结束        if lasterror and lasterror

为了看到函数执行的效果，我们可以利用PIL再生成一幅图，根据生成的坐标值，在图上标出所有数据项的位置及其对应的标签。

def draw2d(data,labels,jpeg='mds2d.jpg'):    img=Image.new('RGB',(2000,2000),(255,255,255))    draw=ImageDraw.Draw(img)    for i in range(len(data)):        x=(data[i][0]+0.5)*1000        y=(data[i][1]+0.5)*1000        draw.text((x,y),labels[i],(0,0,0))    img.save(jpeg,'JPEG')

将下列代码加入到cluster.py中并且运行。

blognames,words,data=readfile('blogdata.txt')coords=scaledown(data)draw2d(coords,blognames,jpeg='blogs2d.jpg')

下面的图显示了多维缩放算法的执行结果。