6. 相似度、邻居和聚类

Fundamental concepts:calculating similarity of objects described by data(计算由数据描述的客体相似度);using similarity for prediction(用相似度来做预测);clustering as similarity-based segmentation(将数据根据相似度进行聚集和分割)。

Exemplary techniques:searching for similar entities(寻找相似的个体);nearest neighbor methods(最近邻方法or邻近算法);clustering methods(聚类算法);distance metrics for calculating similarity(相似度计算的距离度量)。


Similarity and Distance

图6-1 欧几里得距离

如上图所示,经常会将不同的特征当做不同的坐标轴进行数字化,并通过勾股定理来计算点之间的距离,通过这个距离来体现个体间的相似性。

当特征数量为3的时候,可以使用两点的x,y,z三个坐标值差值的平方和的平方根来表示,当特征数更多时继续使用此方法扩展,得到一般性的计算公式如下:

公式6-1 通用欧几里得距离

\sqrt{(d_{1,A}-d_{1,B})^2+(d_{2,A}-d_{2,B})^2+\cdot \cdot \cdot +(d_{n,A}-d_{n,B})^2}

这个公式得到的结果并没有什么绝对意义,但是在针对不同的点的组合之间的相似度进行对比的时候,十分有用。


Nearest-Neighbor Reasoning(最近邻推理)

Example:Whiskey Analytics

有一种威士忌叫做“bunnahabhain”,味道很好,但只有一面之缘就再也没见到哪里卖了,为了能找到这种酒类似的其他威士忌,我们提取了威士忌以下的特征:

威士忌特征,用于对威士忌进行量化的相似度计算

计算之后,得到了如下图所示的距离排序表,距离升序排列:

不同的其他几种可买到的威士忌和bunnahabhain的距离表

然后,拿着这边表,去店里买就行了,记得买距离最近的,应该和bunnahabhain味道类似。


Nearest Neighbors for Predictive Modeling

Classification(分类)

先看下面这个图:

图6-2 由上图来预测,那个新的圆圈由于和大部分的加号的距离要更近,所以我们预测这个点应该是归类为加号,这就是距离在分类上的应用

回到一个人是否会办理信用卡的问题,看下表:

表6-1 得知各人员的年龄、收入、已有卡数,是否已经办卡之后,来对David的是否会办卡进行预测

直观来看,John、Rachel、Norah离David最近,而且结果是2个yes和一个no,那么我们应该基于此预测David为yes吗?更详细的判断标准(需要几个neighbors,分别票数多少)将在后面章节讲解。

Probability Estimation(概率预测)

在上面的问题中由于John、Rachel、Norah离David最近,而且结果是2个yes和一个no,直观计算这个结果的得分应该是2/3(yes=1 & no=0)。但是实际操作中我们会期望有更多的样本拿来做这个比较。

Regression(回归)

同样适用表6-1的数据,我们还可以对David的收入进行预测,和他距离最近的3个人的收入分别是50,35和40,那么我们可以预测David的收入是42(平均数)或40(中位数)。(此处注意,当对收入进行预测时,收入不应当加入距离计算的要素中,因为收入是目标变量)


How Many Neighbors and How Much Influence?

最近邻算法通常被叫做k-NN算法,这里的k就是要使用的最近邻元素的数量,比如3-NN。

还是回到表6-1的问题,如果对David进行预测时,使用4-NN的方法,那么第四个元素的距离将非常远,第四个元素不应该和3个很近的元素有相同的权重比,所以在进行KNN算法时,通常会采用“加权平均”计算或者“相似度约束的投票”方法。

还是回到表6-1的数据,使用所有的元素当做最近邻,即使用5-NN方法,同时将权重设置为“距离的平方的倒数”,得到下表所示的结果:

由此可以得到预测结果是contribution和class的乘积和(yes=1 & no=0)

这样加权运算后,得到的David的概率是0.65概率是yes,0.35概率是no。

当增加元素数量或者使用在其他算法(回归或分类预测)中时,也可以使用相似的方法,通过距离来给每个影响因素添加权重。

CBR:case-based reasoning 基于案例的算法。(CBR和KNN的差异在用,CBR中的案例往往不是简单的多个特征向量简单表示的,而是通过案例的很多细节特征组成的,在实际计算领域中,也会复杂许多)


Geometric Interpretation, Overfitting, and Complexity Control

在1-NN的模型中,由于互为最近neighbors的点会相互锁定,所以会有严重的过拟合现象发生,在使用KNN方法时需要挑选一个合适的K值。

通常情况下,和在防止过拟合当中一样,可以使用嵌套交叉验证(nested cross-validation)的方式来进行k值的选择,目前通常电脑软件可以自动完成这样的步骤。

图6-4 & 图6-5 使用同一批数据进行1-NN和30-NN两种方式进行区域划分,可以看出,30-NN的分割线明显更加平滑,记住这个特征就行,随着K值的增加,区域划分会更加平滑,1-NN是绝对化的过拟合,不能使用

Issues with Nearest-Neighbor Methods(最近邻方法的问题)

Intelligibility(可理解性)

nearest-neighbor方法的可解释性较差,当需要进行可理解性说明和理由提供时可以避免使用knn的算法。

Dimensionality and domain knowledge(维数和领域知识)

使用knn时还有一个问题是,knn算法通常对所有特征使用相同权重进行计算,但是不同特征(维度)在量化时的数值幅度会相差很多,数量级的差异会导致部分维度对接过的影响大于它应有的权重。

维度灾难(维度诅咒)(Curse of Dimensionality):在KNN算法下来理解的情况下,由于KNN寻找的特征值与目标变量是否相关、相关程度均未知,所以导致进行KNN算法得到的结果不能够很好地预测目标变量的情况,往往维度越多,偏差越大。(同时也有说法是维度增多导致点之间的距离直线增加,使关联性的判定会更容易出现错误)

维度诅咒的解决方案:

1. feature selection(特征选择,维度选择),由数据科学家人工进行特征筛选,这是领域知识介入数据科学的一种方式,通过背景知识来进行特征选择;另一种将领域知识介入数据科学的方法是,人工调整“相似度/距离函数”,通常通过对不同的特征进行权重调整实现。

Computational efficiency(计算效率)

KNN算法的建模过程简单不费时,但是进行计算的时候有时候会比较费时,当遇到需要快速得到预测结果的场景(如在线广告推荐)时,往往不能够及时得到算法推荐结果。

brute-force retrieval:暴力破解检索。


Some Important Technical Details Relating to Similarities and Neighbors(相似性和NN算法的技术细节)

Heterogeneous Attributes(多样化的特征)

配合说明用的数据样例表格

从上表数据可以看出,在使用KNN算法时,性别这个分类属性被强行转为了0-1的数值分类(M=0,F=1),而且年龄的数值范围是18-100,但收入却可能从10到1000000或更多,如果不对数据进行规模矫正,那么10元的收入差异和10岁年龄差异对预测结果的影响将是一样的,所以在实践中,数据比较前都会进行规模的调整。


*Other Distance Functions(其他距离函数)

目前为止距离计算方面只提及了欧氏距离(Euchidean distance),这个小节会讲述几个其他的距离计算方法。

欧氏距离(L2 norm,L2范数)的计算公式如下(计算点X和Y的欧氏距离):

d_{Euclidean} (X,Y)=\vert \vert X-Y \vert \vert _{2} =\sqrt{(x_{1} -y_{1} )^2+ (x_{2} -y_{2} )^2+\cdot \cdot \cdot }

曼哈顿距离(L1 norm,L1范数)(taxicab出租车)的计算公式如下:

d_{Manhattan} (X,Y)=\vert \vert X-Y \vert \vert _{1} =\vert x_{1} -y_{1} \vert+ \vert x_{2} -y_{2} \vert+\cdot \cdot \cdot

杰卡德距离(Jaccard distance)的计算公式如下:

d_{Jaccard} (X,Y)=1- \frac{\vert X\cap Y \vert }{\vert X\cup Y \vert}

杰卡德距离说明:杰卡德距离将不同的点当做数据集来处理,X和Y的所有特征数量为并集,当做分母,X和Y的共同特征数量为交集,当做分子,从而通过数据集分数的形式来计算出距离的具体值结果。

余弦距离(cosine distance)的计算公式如下:

d_{Jaccard} (X,Y)=1- \frac{X\ast Y}{\vert\vert X \vert\vert_{2}\ast \vert\vert Y \vert\vert_{2}}

此处,\vert\vert \bullet  \vert\vert_{2}仍然表示欧氏长度,或L2范数,其他书中说的余弦相似度通常指上公式中的分数部分,即\frac{X\ast Y}{\vert\vert X \vert\vert_{2}\ast \vert\vert Y \vert\vert_{2}} ,此处的公式可以表述为“1-余弦距离”。

使用余弦相似度计算文档的相似程度,过程如下:

文档A和B对三个关键词performance,transition,monetary包含的数量分别为,A=<7,3,2>和B=<2,3,0>,此时余弦距离结果为:

d_{Jaccard} (A,B)=1- \frac{<7,3,2>\ast }{\vert\vert  \vert\vert_{2}\ast \vert\vert  \vert\vert_{2}}

d_{Jaccard} (A,B)=1- \frac{7\cdot 2+3\cdot 3+2\cdot 0}{\sqrt{49+9+4} \ast \sqrt{4+9} }

d_{Jaccard} (A,B)=1- \frac{23}{28.4}\approx 0.19

余弦相似度算法是一个可以有效规避特征的数据规模影响的算法,例如有一个文档C的特征为C=<70,30,20>,此时A和C的余弦距离就是0,因为这只是每个特征值乘以10的结果。

对比字符串的差异的方法,对比如下两个字符串:

1. 1113 Bleaker St.

2. 113 Bleecker St.

此处使用编辑距离(edit distance)或者叫levenshtein metric(中文亦作编辑距离),这个算法的计量方式是找到实现变换的最少编辑步骤,每个编辑步骤定义为一次插入、删除、替换一个字母,在上面案例中,编辑操作包括:

1. 删除一个1,

2. 插入一个c,然后

3. 用一个e来替换a。

所以这两个字符串的编辑距离是3,编辑距离在字符串比对的时候十分有用,尤其是字符顺序对整体内容会产生较大影响时。


*Combining Functions:Calculating Scores from Neighbors(组合函数:从邻居计算得分)

多数票决分类(majority vote classification),从多数票决分类开始讲组合函数。

公式6-6,多数票决分类函数表达式如下(表达式比较难打出来,拍照片解决):

多数票决分类函数,对此公式的理解是,寻求得分函数的最大值结果时的x值,即c(x)等于得分函数最大值时的得分函数式

这里neighbors_{k} (x)返回距离为x的k个最近邻,arg max表示返回的结果是score函数获得最大值时的函数式,得分函数(score function)的表达式如下:

majority scoring function(多数得分函数):

score(c,N)=\sum_{y\in N}^n[class(y)=c]

这里,表达式[class(y)=c]class(y)=c的时候值为1,否则为0。

注:(对上式的查资料后理解:多数投票分类函数的目的是找到一个c值,使得在x元素的k个最近邻元素中,与c一致的元素数量达到最大。先看得分函数,c目标值,y为逐个带入的自变量,N为元素全集,当class(y)=c即尝试元素得分等于c,此时记1分,否则记0分。多数投票函数就是找到一个元素c,当全集为neighbors_{k} (x)即k个元素x的最近邻时,这些最近邻元素的得分最高值。类似于在N全集中,找到出现次数最多的元素c。)

公式6-8,相似度适中(平滑)分类函数:

score(c,N)=\sum_{y\in N}^kw(x,y)\times [class(y)=c]

此处w是基于x和y的相似度的权重函数,通常情况下是使用x和y的距离的倒数作为其函数表达式,如下:

w(x,y)=\frac{1}{dist^2 (x,y)}

此处的dist的含义是,任意一种需要使用的距离函数,包括欧氏距离、曼哈顿距离、余弦距离等。

公式6-8给出了可以当做概率预测的得分,对公式6-8进行变式可以得到最终得分函数,如下:

公式6-9,相识度适中(平滑)得分函数:

p(c\vert x)=\frac{\sum_{y\in neighbors(x)}^k w(x,y)\times [class(y)=c]}{\sum_{y\in neighbors(x)}^k w(x,y)}

最后,我们通过一个调整,来通过上式进行回归运算。在回归问题中,我们不对x进行分类预测,而是去计算他对应的一个目标数值f(x),我们把公式6-9中的分类函数用数值函数进行替换,这样可以得到最近邻的加权平均数值结果,权重即为距离,表达式如下:

公式6-10,相识度适中(平滑)回归函数:

f(x)=\frac{\sum_{y\in neighbors(x)}^k w(x,y)\times t(y)}{\sum_{y\in neighbors(x)}^k w(x,y)}

所以,以上就完成了一个对函数进行组合的过程。

对上述过程进行实际的场景应用举例比如,要对一个具有一个特征组合的客户进行消费数额的预测,那么就根据他的邻居客户的历史消费数额的距离加权平居值进行预估。(仍然是使用KNN算法,在视频推荐领域也经常使用这个方案,根据对相同一个视频的评分结果得到不同观众的距离值,再根据已有的距离值,对新的视频,进行评分的预测,从而推荐预测可以得到高分的视频)


Clustering(聚类)

在针对客户的分类问题中,去除监督学习的目标变量(target variable),客户群体可以自然地被分成不同的分组吗?

没有特定的目标变量的分类方式,被叫做无监督分类(无监督学习),或者更直白讲,叫聚类(clustering)。

聚类是相似度的另一个基础应用概念。在聚类中,要找到元素的一个分组,使得组内各元素相似,而组之间的元素不那么相似。

Example:whiskey analytics revisited(举例:回顾威士忌分析)

没看到啥实质性内容,开始下一个小节吧。

Hierarchical Clustering(层次聚类)

图6-6 6个点和他们可能的聚类。根据距离,通过圆圈,将6个点划分进5个类别,底部是根据分类描绘的树状图(dendrogram),详细地描述了聚类过程。

层次聚类不仅对元素进行类别划分,同时也产生了多种分类划分的方法。图6-6中的横虚线可以直观表述这一点,当虚线下降时,我们可以得到更多的类别数。

层次聚类的优势是,可以让数据分析师在决定聚类的具体类别数量前就看到数据相似性的全景(landscape)。根据图6-6中的虚线,可以对需要的类别数量进行横切并选择。并且,一旦两个类别在某个点汇聚后,那么在这个点上方,这两个类别依然一直是聚合在一起的。

linkage function(linkage函数):一般情况下是独立的两个元素间的最小的欧氏距离值(考虑到分类的最小类别范围为单个元素自成一类)。

关于层次聚类树状图(dendrogram)的补充:①图6-6中,由下到上为从每个元素自成一类到逐步汇总的一个过程,看到分类3和分类4的距离(y轴间距)较远,可以认为分类4是一个较好的分类结果;②点F在各分类层次中都比较独立,可以将点F当做异常值来进行研究。

图6-9 威士忌的层次聚类树状图,这里摘录了整个树状图中,和Bunnahabhain相邻的一小段。

书里针对威士忌的其他讨论没什么新的信息,只是说了,通过外观特征进行的分类和实际的口味分类的结果不太一样,可以根据口味层次聚类树来进行威士忌的推荐。

Nearest Neighbors Revisited:Clustering Around Centroids(回顾KNN,围绕聚类中心来聚类)

图6-10 k-means聚类算法的第二步,找到第一步中定义的聚类中心。

看图6-10,圆圈元素们被分成了3个类别,实心五角星就是每个类别的聚类中心(centroid),这个聚类中心,不必要是某个已有元素的位置。

最常用的基于聚类中心的聚类算法是k-means算法,在k-means算法中,means就是聚类中心(centroid),means的实际值是该类别中所有元素的算术平均数结果(即横坐标是类别中众元素的x平均值,y亦然,同时若是多维向量元素数据,则它是每个特征向量的平均值结果)。

k-means算法中,从一开始就定义好了一个聚类类别数k,之后再进行元素的划分。

同时从图6-10可以看出,初始定义的虚线五星的centroid在确定了每个类别中的元素后,会进行平移,移动到实线五星的位置,然而中心的移动使得元素点可能需要重新划归它的所属类别,类别划归后,可能又会影响中心位置导致其再次平移,k-means的过程就是持续这种调整直到循环停止。

图6-13 对90个元素进行的k-means距离,k=3,图中的线是聚类中心在16次迭代循环中的移动轨迹,三角、叉号、圆圈分别是聚类完成后的3个类别划分。

通常k-means不会只进行一次运算,而是根据多个随机聚类中心进行运算和比较,各个聚类中心下的分类结果比较时,可以对他们的distortion进行比较(distortion就是类别中每个元素到聚类中心的距离平方和),distortion最小的分类方式就是最佳的k-means聚类结果。

k-means聚类的计算速度会比层次聚类要快(k-means只需要计算中心到各类别内点的距离并比较,而层次聚类每次迭代中需要计算每个聚类的距离,而在最开始的时候,是所有元素的相互距离)。

关于k-means算法中k值的选择,当某个类别元素过少或过于特殊时可减小k值,当某个类别太庞大或散开时可增大k值(但是没说具体要怎么量化衡量)。

Example:Clustering Business News Stories

书中的很多example,我个人认为是为了培养读者的数据思维方式提供一个牵引,书中的理论知识大多很基础,但是这些案例可以提供许多应用层面的实践,为读者铺路。

这里使用了一个新闻案例,从一个资料库中找出苹果公司的相关新闻报道。

这里首先需要做的是数据预处理,由于多数是文本类型数据,这个数据类型将在后面第十章更详细讲解。

由于会有很多股价变动的新闻导致出现很多实质内容和Apple无关的信息出来,所以此处只选取标题含有Apple的稿件。

特征,此处使用“TFIDF scores”(term frequency times inverse document frequency-词汇频率乘以文档频率的倒数)(即某个单词在某个文档中的出现次数,除以这个词在整个文库中的次数)。

距离,使用余弦相似度距离。

从文库中一共选出312偏结果文章,根据k-means分成9个类别,书中列了9种类别的分类特征,并从分类结果中总结了如下问题:

1. 有相关性的要素,并不构成因果关系;

2. 语法的相似性并不能表示语义的相似。

所以聚类是在我们未发现数据规律时帮我们了解数据结构的一个工具,可以帮我们找到数据挖掘的机会。


Understanding the Result of Clustering(对聚类结果的理解)

这里我发现的一个意义就是,在完成聚类后,在每个聚类中找到一个代表元素来对这个类别的特点进行呈现,通常可以让人更快地get到这个聚类的特征。帮助更好地理解这个类别,这个标本元素可以是聚类中心最近的元素、或销量最好的元素商品、或最知名的元素商品。


*Using Supervised Learning to Generate Cluster Descriptions(用监督学习来获取聚类的描述)

提示里面只说了这一个小节比较难理解,不用在意,直接开始阅读即可。

通常策略:对样本进行一个k-class任务,来进行样本的k个类别的聚类,同时启用另外k个监督学习任务,来对每一个聚类区别于其他(k-1)个聚类的特征值进行总结。

应用实际举例(威士忌问题):

12个威士忌的分组,分别是A~J组,选择J组来进行描述如下:

Group J:

Scotches:Glen Albyn,Glengoyne,Glen Grant,Glenlossie,Linkwood,North Port,Saint Magdalene,Tamdhu.

The best of its class:Linkwood(Speyside),12years,83 points.

Average characteristics:full gold;dry,peaty,sherry;light to medium,round;sweet;dry.

从本书145页可以看到每种威士忌都用了68种特征来描述,目前每一种又新增了一个特征(J or not_J):

加上(J or not_J)特征后,数据应该是这样的,%后面的是对应的威士忌的名称

将这个新增特征使用决策树进行区分,可以得到下面的决策树:

图6-14 基于scotches数据对J组进行的决策树学习。满足round body和Sherry nose这两个特征的威士忌大多数是从J组找到的。

将这个结论描述出来,可以是以下两种方式其一:

1. A round body and a sherry nose, or

2. A full gold(but not red)color with a light(but not round)body and a dry finish。


Stepping Back:Solving a Business Problem Versus Data Exploration(回顾:解决商业问题和数据探索)

图6-15 CRISP数据挖掘过程(CRISP = Cross Industry Standard Process for Data Mining)

对于无法在一开始就定义准确的要处理的问题的数据分析工作,可以先进行非监督学习来发现数据本身的自然规律。

数据(非监督学习)分析可用于各种领域,只是大多不能得到一个精确的函数公式,此时需要做一个权衡,若前期的函数公式不够精确,那么后续的再评估的工作量就会相应增加。


summary

本章结束。

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

推荐阅读更多精彩内容