机器学习（7）

前面介绍的集中算法都是属于有监督机器学习方法，这章和前面不同，介绍无监督学习算法，也就是聚类算法。在无监督学习中，目标属性是不存在的，也就是所说的不存在“y”值，我们是根据内部存在的数据特征，划分不同的类别，使得类别内的数据比较相似。

我们对数据进行聚类的思想不同可以设计不同的聚类算法，本章主要谈论三种聚类思想以及该聚类思想下的三种聚类算法。666

本章主要涉及到的知识点有：

“距离”

K-Means算法

几种优化K-Means算法

密度聚类

本节首先通过聚类算法的基本思想，引出样本相似度这个概念，并且介绍几种基本的样本相识度方法。

俗话说：“物以类聚，人以群分”，在自然科学和社会科学中，存在着大量的分类问题。所谓类，通俗地说，就是指相似元素的集合。例如，我们刚生下来父母就开始教我们分类，给我们买很多卡片，告诉我们：（一定要用现实中的例子说名，注重趣味性）

“这是汽车。”。 “这是飞机。” “这是鱼类。” “这是鸟类。” “这是圆。” “这是长方形。” “……。”

可见我们作为一个刚刚进入尘世的人，首先接触的就是分类了。然而到了今天，回顾我们的科学史，我们很多比较重要的就是发现一个新事物，然后给新事物分类。当然，我们眼里所熟悉的类别，都是根据常识，已经做好的分类。对于计算机来说，更具体一些，对于这里聚类算法；来说也是一样，只不过，通过算法把那些相识的数据划分在一起。这是我们本章主要解决的任务。 由上面可得我们本章的重点是将给定的数据划分为不同的数据类别，是类别之间的相识度最小。

通过计算样本之间的相识度，将相识度大的划分为一个类别。衡量样本之间的相识度的大小的方式有下面几种：

当p=2时，为欧几里得距离，公式如下：

当p=为无穷大时候，为切比雪夫距离，公式如下：

一般情况下用欧几里得距离比较多，当数据量出现扁平化时候，一般用切夫雪比距离。

假设两个样本有2个特征， 则这两个样本的夹角余弦相似度公式如下：

最常见的应用就是计算文本相似度。将两个文本根据他们词，建立两个向量，计算这两个向量的余弦值，就可以知道两个文本在统计学方法中他们的相似度情况。实践证明，这是一个非常有效的方法。

将杰卡德相似性度量应用到基于物品的协同过滤系统中，并建立起相应的评价分析方法。 与传统相似性度量方法相比，杰卡德方法完善了余弦相似性只考虑用户评分而忽略了其他信息量的弊端，特别适合于应用到稀疏度过高的数据。

前面我们讲到把数据划分为不同类别，机器学习给这个类别定义一个新的名字—簇。 将具有M个样本的数据换分为k个簇，必然kT2) （2）从列表L中获取一个节点P,计算P到所有聚簇中心点的距离(如果不存在聚簇中心,那么此时点P形成一个新的聚簇),并选择出最小距离D(P,aj)。 （3）如果距离D小于T1,表示该节点属于该聚簇,添加到该聚簇列表中 （4）如果距离D小于T2,表示该节点不仅仅属于该聚簇,还表示和当前聚簇中心点非常近,所以将该聚簇的中心点设置为该簇中所有样本的中心点,并将P从列表L中删除。 （5）如果距离D大于T1,那么节点P形成一个新的聚簇。 （6）直到列表L中的元素数据不再有变化或者元素数量为0的时候,结束循环操作。 该步骤用流程图表示如下图所示：

Canopy算法得到的最终结果的值,聚簇之间是可能存在重叠的,但是不会存在某个对象不属于任何聚簇的情况。

可以看到canopy算法将可以将一堆杂乱的数据大致的划分为几块所以Canopy算法一般会和kmeans算法配合使用来到达使用者的目的在使用Canopy算法时，阈值t1，t2的确定是十分重要的。t1的值过大，会导致更多的数据会被重复迭代，形成过多的Canopy；值过小则导致相反的效果t2的值过大，会导致一个canopy中的数据太多，反之则过少这样的情况都会导致运行的结果不准确。该算法的过程图形说明如图所示：

Mini Batch K-Means使用了一个种叫做Mini Batch（分批处理）的方法对数据点之间的距离进行计算。Mini Batch的好处是计算过程中不必使用所有的数据样本，而是从不同类别的样本中抽取一部分样本来代表各自类型进行计算。由于计算样本量少，所以会相应的减少运行时间，但另一方面抽样也必然会带来准确度的下降。这样使用于存在巨大的数据集合的情况下。 实际上，这种思路不仅应用于K-Means聚类，还广泛应用于梯度下降、深度网络等机器学习和深度学习算法。

该算法的算法流程和k- Means类似，流程如下：

（1）首先抽取部分数据集,使用K- Means算法构建出K个聚簇点的模型。 （2）继续抽取训练数据集中的部分数据集样本数据,并将其添加到模型中,分配给距离最近的聚簇中心点。 （3）更新聚簇的中心点值。 （4）循环迭代第二步和第三步操作,直到中心点稳定或者达到迭代次数,停止计算操作。 应用场景，由于Mini Batch KMeans跟K-Means是极其相似的两种聚类算法，因此应用场景基本一致。 后面我们就以 Mini batch k- Means算法为例子，比较一下它和 k- Means算法的区别。

有监督的分类算法的评价指标通常是accuracy, precision, recall, etc；由于聚类算法是无监督的学习算法，评价指标则没有那么简单了。因为聚类算法得到的类别实际上不能说明任何问题，除非这些类别的分布和样本的真实类别分布相似，或者聚类的结果满足某种假设，即同一类别中样本间的相似性高于不同类别间样本的相似性。

下面介绍几种常见的评估方法：

兰德系数（Rand index）需要给定实际类别信息C，假设K是聚类结果，a表示在C与K中都是同类别的元素对数，b表示在C与K中都是不同类别的元素对数，则兰德指数为：

分子：属性一致的样本数，即同属于这一类或都不属于这一类。a是真实在同一类、预测也在同一类的样本数；b是真实在不同类、预测也在不同类的样本数； 分母：任意两个样本为一类有多少种组合，是数据集中可以组成的总元素对数； RI取值范围为[0,1]，值越大意味着聚类结果与真实情况越吻合。 对于随机结果，RI并不能保证分数接近零。为了实现“在聚类结果随机产生的情况下，指标应该接近零”，调整兰德系数（Adjusted rand index）被提出，它具有更高的区分度：

ARI取值范围为[-1,1]，值越大意味着聚类结果与真实情况越吻合。从广义的角度来讲，ARI衡量的是两个数据分布的吻合程度。

优点：

（1）对任意数量的聚类中心和样本数，随机聚类的ARI都非常接近于0； （2）取值在［－1，1］之间，负数代表结果不好，越接近于1越好； （3）可用于聚类算法之间的比较。

缺点： ARI需要真实标签

轮廓系数适用于实际类别信息未知的情况。

簇内不相似度:计算样本i倒同簇其它样本的平均距离为a;a越小,表示样本越应该被聚类到该簇,簇C中的所有样本的a的均值被称为簇C的簇不相似度。

簇间不相似度:计算样本i到其它簇C的所有样本的平均距离b;b=min{b;1,bi2,bi};b越大,表示样本越不属于其它簇。

轮廓系数:s值越接近1表示样本麇类越合理,越接近-1,表示样本j应该分类到另外的簇中,近似为0,表示样本应该在边界上;所有样本的s的均值被成为聚类结果的轮廓系数。伦敦系数可以写作：

Scikit-learn中有兰求德系数方法metrics.silhouette_score。

Python中实现的代码如下：

输出：

要求：给定较多数据，来比较两种算法的聚类速度，且用刚学到的聚类评估算法对，这两种算法进行评估。

两种的算法的API详情可以参考网址：

http://scikit-learn.org/0.19/modules/generated/sklearn.cluster.KMeans.html#sklearn.cluster.KMeans。

分析：从上图，我们看出Mini batch k- Means算法比 k- Means算法速度快了不止一倍，而效果还是不错的。

思考：如果出现如图9.7所示出现的数据类型用类 k- Means算法就不能正确地对他们进行聚类了，因为他们属于非凸类数据。这时候就要转变聚类思想了，采用别的聚类方法了。

本章主要介绍了聚类中的一种最常见的算法—K-Means算法以及其优化算法，聚类是一种无监督学习的方法。我们通过簇来把数据划分为不同的种类，介绍了该算法的构建流程，根据构建的流程中的初始值敏感问题，我们对最基本的K-Means算法进行了改进，其中Mini batch k- Means算法可以适用于数据量比较多的情况，且效果也不错。 本章的最后我们根据样本不同的特征，有时候不适合采用K-Means算法，我们将在下一章介绍几种其他思想产生的算法。