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
如上图所示,经常会将不同的特征当做不同的坐标轴进行数字化,并通过勾股定理来计算点之间的距离,通过这个距离来体现个体间的相似性。
当特征数量为3的时候,可以使用两点的x,y,z三个坐标值差值的平方和的平方根来表示,当特征数更多时继续使用此方法扩展,得到一般性的计算公式如下:
公式6-1 通用欧几里得距离
这个公式得到的结果并没有什么绝对意义,但是在针对不同的点的组合之间的相似度进行对比的时候,十分有用。
Nearest-Neighbor Reasoning(最近邻推理)
Example:Whiskey Analytics
有一种威士忌叫做“bunnahabhain”,味道很好,但只有一面之缘就再也没见到哪里卖了,为了能找到这种酒类似的其他威士忌,我们提取了威士忌以下的特征:
计算之后,得到了如下图所示的距离排序表,距离升序排列:
然后,拿着这边表,去店里买就行了,记得买距离最近的,应该和bunnahabhain味道类似。
Nearest Neighbors for Predictive Modeling
Classification(分类)
先看下面这个图:
回到一个人是否会办理信用卡的问题,看下表:
直观来看,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方法,同时将权重设置为“距离的平方的倒数”,得到下表所示的结果:
这样加权运算后,得到的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值的选择,目前通常电脑软件可以自动完成这样的步骤。
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的欧氏距离):
曼哈顿距离(L1 norm,L1范数)(taxicab出租车)的计算公式如下:
杰卡德距离(Jaccard distance)的计算公式如下:
杰卡德距离说明:杰卡德距离将不同的点当做数据集来处理,X和Y的所有特征数量为并集,当做分母,X和Y的共同特征数量为交集,当做分子,从而通过数据集分数的形式来计算出距离的具体值结果。
余弦距离(cosine distance)的计算公式如下:
此处,仍然表示欧氏长度,或L2范数,其他书中说的余弦相似度通常指上公式中的分数部分,即,此处的公式可以表述为“1-余弦距离”。
使用余弦相似度计算文档的相似程度,过程如下:
文档A和B对三个关键词performance,transition,monetary包含的数量分别为,A=<7,3,2>和B=<2,3,0>,此时余弦距离结果为:
余弦相似度算法是一个可以有效规避特征的数据规模影响的算法,例如有一个文档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的k个最近邻,表示返回的结果是score函数获得最大值时的函数式,得分函数(score function)的表达式如下:
majority scoring function(多数得分函数):
这里,表达式在的时候值为1,否则为0。
注:(对上式的查资料后理解:多数投票分类函数的目的是找到一个c值,使得在x元素的k个最近邻元素中,与c一致的元素数量达到最大。先看得分函数,c目标值,y为逐个带入的自变量,N为元素全集,当即尝试元素得分等于c,此时记1分,否则记0分。多数投票函数就是找到一个元素c,当全集为即k个元素x的最近邻时,这些最近邻元素的得分最高值。类似于在N全集中,找到出现次数最多的元素c。)
公式6-8,相似度适中(平滑)分类函数:
此处是基于x和y的相似度的权重函数,通常情况下是使用x和y的距离的倒数作为其函数表达式,如下:
此处的的含义是,任意一种需要使用的距离函数,包括欧氏距离、曼哈顿距离、余弦距离等。
公式6-8给出了可以当做概率预测的得分,对公式6-8进行变式可以得到最终得分函数,如下:
公式6-9,相识度适中(平滑)得分函数:
最后,我们通过一个调整,来通过上式进行回归运算。在回归问题中,我们不对x进行分类预测,而是去计算他对应的一个目标数值,我们把公式6-9中的分类函数用数值函数进行替换,这样可以得到最近邻的加权平均数值结果,权重即为距离,表达式如下:
公式6-10,相识度适中(平滑)回归函数:
所以,以上就完成了一个对函数进行组合的过程。
对上述过程进行实际的场景应用举例比如,要对一个具有一个特征组合的客户进行消费数额的预测,那么就根据他的邻居客户的历史消费数额的距离加权平居值进行预估。(仍然是使用KNN算法,在视频推荐领域也经常使用这个方案,根据对相同一个视频的评分结果得到不同观众的距离值,再根据已有的距离值,对新的视频,进行评分的预测,从而推荐预测可以得到高分的视频)
Clustering(聚类)
在针对客户的分类问题中,去除监督学习的目标变量(target variable),客户群体可以自然地被分成不同的分组吗?
没有特定的目标变量的分类方式,被叫做无监督分类(无监督学习),或者更直白讲,叫聚类(clustering)。
聚类是相似度的另一个基础应用概念。在聚类中,要找到元素的一个分组,使得组内各元素相似,而组之间的元素不那么相似。
Example:whiskey analytics revisited(举例:回顾威士忌分析)
没看到啥实质性内容,开始下一个小节吧。
Hierarchical Clustering(层次聚类)
层次聚类不仅对元素进行类别划分,同时也产生了多种分类划分的方法。图6-6中的横虚线可以直观表述这一点,当虚线下降时,我们可以得到更多的类别数。
层次聚类的优势是,可以让数据分析师在决定聚类的具体类别数量前就看到数据相似性的全景(landscape)。根据图6-6中的虚线,可以对需要的类别数量进行横切并选择。并且,一旦两个类别在某个点汇聚后,那么在这个点上方,这两个类别依然一直是聚合在一起的。
linkage function(linkage函数):一般情况下是独立的两个元素间的最小的欧氏距离值(考虑到分类的最小类别范围为单个元素自成一类)。
关于层次聚类树状图(dendrogram)的补充:①图6-6中,由下到上为从每个元素自成一类到逐步汇总的一个过程,看到分类3和分类4的距离(y轴间距)较远,可以认为分类4是一个较好的分类结果;②点F在各分类层次中都比较独立,可以将点F当做异常值来进行研究。
书里针对威士忌的其他讨论没什么新的信息,只是说了,通过外观特征进行的分类和实际的口味分类的结果不太一样,可以根据口味层次聚类树来进行威士忌的推荐。
Nearest Neighbors Revisited:Clustering Around Centroids(回顾KNN,围绕聚类中心来聚类)
看图6-10,圆圈元素们被分成了3个类别,实心五角星就是每个类别的聚类中心(centroid),这个聚类中心,不必要是某个已有元素的位置。
最常用的基于聚类中心的聚类算法是k-means算法,在k-means算法中,means就是聚类中心(centroid),means的实际值是该类别中所有元素的算术平均数结果(即横坐标是类别中众元素的x平均值,y亦然,同时若是多维向量元素数据,则它是每个特征向量的平均值结果)。
k-means算法中,从一开始就定义好了一个聚类类别数k,之后再进行元素的划分。
同时从图6-10可以看出,初始定义的虚线五星的centroid在确定了每个类别中的元素后,会进行平移,移动到实线五星的位置,然而中心的移动使得元素点可能需要重新划归它的所属类别,类别划归后,可能又会影响中心位置导致其再次平移,k-means的过程就是持续这种调整直到循环停止。
通常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):
将这个新增特征使用决策树进行区分,可以得到下面的决策树:
将这个结论描述出来,可以是以下两种方式其一:
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(回顾:解决商业问题和数据探索)
对于无法在一开始就定义准确的要处理的问题的数据分析工作,可以先进行非监督学习来发现数据本身的自然规律。
数据(非监督学习)分析可用于各种领域,只是大多不能得到一个精确的函数公式,此时需要做一个权衡,若前期的函数公式不够精确,那么后续的再评估的工作量就会相应增加。
summary
本章结束。