全栈工程师开发手册 （作者：栾鹏）
关于分类与聚类的区别，这里再简单描述一下。聚类算法是非监督算法，只是对一群输入对象进行分组，每组属于什么类别是不知道的。或者说聚类算法只是将相似的用户分在一起，或者找出与某对象相似的对象。
而分类器是分类器是监督算法，在没有任何样本数据前就已经定好了拥有哪些类。对一批已知所属分类的数据集进行统计训练，然后再对新来的数据进行判定属于哪个分类。
本文在对数据进行聚类分组前，先来解决一些简单的实用的问题。寻找相似对象，和根据相似对象估计对象的属性的值。
这种匹配相似对象的机制是聚类算法的基础，被称为过滤算法。
在样本数据集中，数据存储一般以矩阵的形式，每一行代表一个对象，每一列代表一个特征属性。而文本介绍一种稀疏高维的特征数据集。例如在文本分类中，文章的特征用文章包含的单词表示，在客户购物中，客户的特征用所购买的物品表示。这种对象的特征维度往往都是很大的，并且是稀疏的。对于这种数据集进行计算，算法往往比较复杂。
一个普通的特征数据集如下表：
人 身高 年龄 体重
小明1 182 23 67
小明2 181 24 65
小明3 184 24 65
小明4 183 21 68
小明5 185 22 66 一个稀疏高维特征数据集如下：0表示没买，1表示买
客户 宝贝1 宝贝2 宝贝3 宝贝4 宝贝5 宝贝6 宝贝7 ...
客户1 1 0 0 0 0 1 0 ...
客户2 0 0 1 0 1 0 0 ...
客户3 0 1 0 0 0 0 1 ...
客户4 0 0 1 0 0 0 0 ...
客户5 1 0 0 0 1 0 0 ...
客户6 0 0 0 1 0 0 0 ...
客户7 0 0 0 0 1 0 0 ...
客户8 0 1 0 0 0 1 0 ...
客户9 0 0 0 0 1 0 0 ...高维稀疏特征数据集是经常存在的，例如：
影评人给电影打分。 向影评人推荐相似影评人，向影评人推荐电影。
买家给宝贝评分。向淘宝买家推荐宝贝等。
读者停留在某类文章上的时间长度。向读者推荐类似文件的强度。
上网用户对某博客进行了点击。向用户推荐感性的博主。
有多的应用需要在工作中学会洞察。
对这种数据集进行聚类或者分类往往比较困难，而且尤其当我们关系的特征出现的数量很少还要主要注意进行样本均衡。这些读者可以在以后的学习中注意。
本文仅以电影推荐这个例子来讲述匹配与推荐的算法（协作性过滤算法）。
构造数据集
我们先使用如下简单的数据集。
注意：实际中特征数据集可能是稀疏的，因为本文重点是为了了解匹配和推荐机制。
# 偏好数据集（人-电影-评分）
prefs={
'name1': {'movie1': 2.5, 'movie2': 3.5,'movie3': 3.0, 'movie4': 3.5, 'movie5': 2.5, 'movie6': 3.0},
'name2': {'movie1': 3.0, 'movie2': 3.5,'movie3': 1.5, 'movie4': 5.0, 'movie6': 3.0,'movie5': 3.5},
'name3': {'movie1': 2.5, 'movie2': 3.0,'movie4': 3.5, 'movie6': 4.0},
'name4': {'movie2': 3.5, 'movie3': 3.0, 'movie6': 4.5, 'movie4': 4.0, 'movie5': 2.5},
'name5': {'movie1': 3.0, 'movie2': 4.0, 'movie3': 2.0, 'movie4': 3.0, 'movie6': 3.0,'movie5': 2.0},
'name6': {'movie1': 3.0, 'movie2': 4.0, 'movie6': 3.0, 'movie4': 5.0, 'movie5': 3.5},
'name7': {'movie2':4.5,'movie5':1.0,'movie4':4.0}
}
相似度计算方法
我们可以对行或对列进行相似度计算。这里先了解如何对计算两个行的相似程度。我们采用欧几里得距离和皮尔逊相似度。将计算的值映射的0-1范围上来代表相似程度，1代表完全相同，0代表完全不同。
注意：读者可以思考，如何计算高维稀疏特征数据集中两行之间的相似度
欧几里得距离计算
公式：|x| = √( x[1]2 + x[2]2 + … + x[n]2 ) 欧式距离百科
获取两个行（对象）的相同列，生成一个局部特征数据集。再根据这个局部特征数据集计算欧式距离（这是因为属性数据集太系数，直接计算相似度会计算出来的值特别小）。
from math import sqrt
# 计算两行之间的欧几里得距离，以此来代表相似度。prefs表示偏好数据集
def sim_distance(prefs,row1_name,row2_name):
# 首先计算是否有共同列（都看过的电影）
si={}
for item in prefs[row1_name]:
if item in prefs[row2_name]: si[item]=1
# 如果没有共同列，则两行之间相似度为0
if len(si)==0: return 0
# 根据共同列计算两行的欧几里得距离，并将距离映射到0-1上。0表示完全不相似，1表示完全相似
sum_of_squares=sum([pow(prefs[row1_name][item]-prefs[row2_name][item],2) for item in prefs[row1_name] if item in prefs[row2_name]])
return 1/(1+sum_of_squares)皮尔逊相似度计算
假设有两个向量X、Y，那么两向量间的皮尔逊相关系数可通过以下公式计算：
公式一：
可以将公式进行多种演变，其中一种转换为下面的公式。
公式二：
其中E是数学期望，cov表示协方差，N表示变量取值的个数。
我们就根据公式二进行计算。
获取两个行（对象）的相同列，生成一个局部特征数据集。再根据这个局部特征数据集计算皮尔逊相似度（这是因为属性数据集太系数，直接计算相似度会计算出来的值特别小）。
虽然皮尔逊相似度的计算过程更复杂一些，但它在数据不是很规范的时候（例如：影评者对影片的评价总是相对于平均水平偏离很大时），会倾向于给出很更好的结果。
# 计算两行的皮尔逊相似度，以此来代表相似度。prefs表示数据集
def sim_pearson(prefs,row1_name,row2_name):
# 首先计算是否有共同列（都看过的电影）
si={}
for item in prefs[row1_name]:
if item in prefs[row2_name]: si[item]=1
# 如果没有共同列，两行之间相似度为0
if len(si)==0: return 0
# 得到列表元素个数
n=len(si)
# 对两行的共同列求和
sum1=sum([prefs[row1_name][it] for it in si])
sum2=sum([prefs[row2_name][it] for it in si])
# 对两行的共同列求平方和
sum1Sq=sum([pow(prefs[row1_name][it],2) for it in si])
sum2Sq=sum([pow(prefs[row2_name][it],2) for it in si])
# 对两行的共同列求乘积之和
pSum=sum([prefs[row1_name][it]*prefs[row2_name][it] for it in si])
# 计算皮尔逊评价值
num=pSum-(sum1*sum2/n)
den=sqrt((sum1Sq-pow(sum1,2)/n)*(sum2Sq-pow(sum2,2)/n))
if den==0: return 0
r=num/den
return r
匹配相似行
有了每两行之间的相似度计算方法，就可以计算每行的相似行了。在计算相似行时，对于两个特征属性的数量不同的行计算相似度时，只用计算公共特征属性即可。
# 匹配相似行
# 根据偏好数据集，返回与某个行最匹配的n行。person表示要匹配的行（人），similarity表示相似度计算函数
def topMatches(prefs,row_name,n=5,similarity=sim_pearson):
scores=[(similarity(prefs,row_name,other),other) for other in prefs if other!=row_name]
scores.sort()
scores.reverse()
num = n
if n>len(scores):num= len(scores)
return scores[0:num]利用相似行估计列的值，并排名
有了相似行，某一行就可以根据相似行对各列的评值，来估计当前行各列存在的空白值。为了避免算法的不精准，所以相似行不止一个，每个相似行根据相似度确定权重。最后估值采用加权平均的方式。
对当前行各列存在的空白值进行估计以后，将估计的值进行排名推荐。
# 利用相似行，估计某行所有列存在的空白值，并排名（估计影片评分，并排名推荐）
# 利用所有其他行的各列取值的加权平均（相似度为权值），为某行各列提供估值
def getRecommendations(prefs,row_name,similarity=sim_pearson):
totals={}
simSums={}
for other in prefs:
# 不和自己做比较
if other==row_name: continue
sim=similarity(prefs,row_name,other)
# 忽略评价值为0或为负的情况
if sim<=0: continue
for item in prefs[other]:
# 只对自己还未有的列进行临时估值
if item not in prefs[row_name] or prefs[row_name][item]==0:
# 相似度*临时估值
totals.setdefault(item,0)
totals[item]+=prefs[other][item]*sim
# 相似度之和
simSums.setdefault(item,0)
simSums[item]+=sim
# 建立归一化列表
rankings=[(total/simSums[item],item) for item,total in totals.items()]
# 返回最终估值经过排序的列表
rankings.sort()
rankings.reverse()
return rankings匹配相似列
对于数据来说他无法识别每行的含义，只是在做行间运算。如果我们把数据矩阵进行转置，再做行间运算。那就是进行的列匹配。
数据集转置
def transformPrefs(prefs):
result={}
for row_name in prefs:
for item in prefs[row_name]:
result.setdefault(item,{})
# 将行与列对调
result[item][row_name]=prefs[row_name][item]
return result匹配相似列
# 匹配相似列，返回各列的匹配集合（因为各列的匹配可提前在用户登陆前完成），
# 根据转置后的偏好数据集，获取每列相似的n个其他列
def calculateSimilarItems(prefs,n=10):
# 建立字典，以给出与这些列最为相近的所有其他列
itemMatch={}
# 以列为中心对偏好矩阵实施转置处理
itemPrefs=transformPrefs(prefs)
c=0
for item in itemPrefs:
# 针对大数据集更新状态变量
c+=1
if c%100==0: print("%d / %d" % (c,len(itemPrefs)))
# 寻找最为相近的列
scores=topMatches(itemPrefs,item,n=n,similarity=sim_distance)
itemMatch[item]=scores
return itemMatch #返回每列匹配的其他列利用相似列，对某一行的各列空白处进行估值
与根据相似行对各列的空白值进行估计类似。
# 利用相似列，对某一行的各列进行估值，（估计影片评分，并排名推荐）：根据偏好数据集和提前构造好的物品匹配库，向用户推荐物品
def getRecommendedItems(prefs,itemMatch,row_name):
onerow=prefs[row_name] #获取当前行所拥有的列
scores={}
totalSim={}
# 循环遍历由当前行所拥有的列
for (item,rating) in onerow.items( ):
# 循环遍历与当前列相似的列
for (similarity,item2) in itemMatch[item]:
# 忽略行已经拥有的列
if item2 in onerow: continue
# 估值与相似度的加权之和
scores.setdefault(item2,0)
scores[item2]+=similarity*rating
# 全部相似度之和
totalSim.setdefault(item2,0)
totalSim[item2]+=similarity
# 将每个合计值除以加权和，求出平均值
rankings=[(score/totalSim[item],item) for item,score in scores.items( )]
# 按最高值到最低值的顺序，返回估值排行
rankings.sort( )
rankings.reverse( )
return rankings运行试验
有了上面的算法，我们就可以来尝试效果了。
if __name__=="__main__": #只有在执行当前模块时才会运行此函数
#利用相似人推荐相似物品
rankings = getRecommendations(prefs,'name7')
print(rankings) #打印推荐排名
#利用相似物品推荐相似物品
itemMatch = calculateSimilarItems(prefs) # 提前计算所有物品的相似物品
rankings = getRecommendedItems(prefs,itemMatch,'name7')
print(rankings) #打印推荐排名应该选用哪一种相似性度量方式
我们在此处已经介绍了两种不同的度量方式，但实际上，还有许多其他的衡量两个数组相似度的方式。例如jaccard系数和曼哈顿距离算法。使用哪种方式最优取决于具体的应用。如果你想看看哪种方式最优建议你都尝试一下。