黑马程序员技术交流社区

标题: 【上海校区】机器学习算法（9）之聚类算法 [打印本页]

---

作者: 不二晨    时间: 2018-10-19 09:53
标题: 【上海校区】机器学习算法（9）之聚类算法
1、什么是聚类分析？

1.1 聚类的定义：

       聚类就是对大量未知标注的数据集，按数据的内在相似性将数据集划分为多个类别，使类别内的数据相似度较大，而类别间的数据相似度较小。

聚类：一种把相似的数据合并成一组（group）的方法。就是我们常说的“人以群分，物以类聚”
聚类是一种“非监督的学习算法”——事先并不需要有类别标注的样本来辅助学习，而是直接从数据中学习模式
所以，聚类是一种“数据探索”的分析方法：它帮助我们在大量的数据中探索和发现数据的结构。
1.2 聚类的目标      

聚类分析的目标就是在相似的基础上收集数据来分类。在不同的应用领域，很多聚类技术都得到了发展，这些技术方法被用作描述数据，衡量不同数据源间的相似性，以及把数据源分类到不同的簇中。

商业：

聚类分析被用来发现不同的客户群，并且通过购买模式刻画不同的客户群的特征。
聚类分析是细分市场的有效工具，同时也可用于研究消费者行为，寻找新的潜在市场、选择实验的市场，并作为多元分析的预处理。
生物：

聚类分析被用来动植物分类和对基因进行分类，获取对种群固有结构的认识
地理：

聚类能够帮助在地球中被观察的数据库商趋于的相似性
保险行业：

聚类分析通过一个高的平均消费来鉴定汽车保险单持有者的分组，同时根据住宅类型，价值，地理位置来鉴定一个城市的房产分组
电子商务：

聚类分析在电子商务中网站建设数据挖掘中也是很重要的一个方面，通过分组聚类出具有相似浏览行为的客户，并分析客户的共同特征，可以更好的帮助电子商务的用户了解自己的客户，向客户提供更合适的服务。
2、聚类方法之K-means算法

2.1 距离的度量方式

       在前言中，我们就提到了K-means算法是要找出一个点与另一个点最近，那要用什么来衡量最近呢，什么样的数据叫相似的？有多相似？

我们常用的方法还是利用距离来衡量远近，这里就介绍几种距离的度量方式。

欧氏距离(Euclidean Distance)
曼哈顿距离(Manhattan Distance)
切比雪夫距离 (Chebyshev Distance)
闵可夫斯基距离(Minkowski Distance)
余弦距离(Cosine Distance)
相关距离(Correlation distance)
        其中，欧氏距离(Euclidean Distance)、曼哈顿距离(Manhattan Distance)、切比雪夫距离 (Chebyshev Distance)、闵可夫斯基距离(Minkowski Distance)这里就不做介绍了，需要了解的可自行查阅相关资料。其中需要说明下，相关距离(Correlation distance)就是皮尔逊相关系数，是衡量变量之间相关程度的，这里我也给个链接，以供查阅。

2.2基本概念

      要得到簇的个数，需要指定K值

      质心：均值，即向量各维取平均即

      距离的度量：常用欧几里得距离和余弦相似度（先标准化）

      优化目标：后面会讲述到

2.3K-Means原理

       K-Means算法的思想很简单，对于给定的样本集，按照样本与类中心距离大小，将样本集划分为K个簇。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大。

如果用数据表达式表示，假设簇划分为(C1,C2,...Ck)，则我们的目标是最小化平方误差E：



其中μi是簇Ci的均值向量，有时也称为质心，表达式为：



如果我们想直接求上面损失函数的最小值并不容易，这是一个NP难的问题，因此只能采用启发式的迭代方法。

K-Means采用的启发式方式很简单，用下面一组图就可以形象的描述。



传统K-Means算法流程

     1）对于K-Means算法，首先要注意的是k值的选择，一般来说，我们会根据对数据的先验经验选择一个合适的k值，如果没有            什么先验知识，则可以通过交叉验证选择一个合适的k值。

　 2）在确定了k的个数后，我们需要选择k个初始化的质心，就像上图b中的随机质心。由于我们是启发式方法，k个初始化的质           心的位置选择对最后的聚类结果和运行时间都有很大的影响，因此需要选择合适的k个质心，最好这些质心不能太近。

　传统的K-Means算法流程。　

　输入是样本集D={x1,x2,...xm},聚类的簇树k,最大迭代次数N

　输出是簇划分C={C1,C2,...Ck}

　　   1) 从数据集D中随机选择k个样本作为初始的k个质心向量： {μ1,μ2,...,μk}

　　　2）对于n=1,2,...,N（迭代次数）

　　　　　　a) 将簇划分C初始化为

　　　　　　b) 对于i=1,2...m,计算样本xi和各个质心向量μj(j=1,2,...k)的距离：，将xi标记最小的为dij所对应的                              类别λi。此时更新

                     c) 对于j=1,2,...,k,对Cj中所有的样本点重新计算新的质心:



　　　　　　e) 如果所有的k个质心向量都没有发生变化，则转到步骤3）

　　　　3） 输出簇划分C={C1,C2,...Ck}

初选质心优化K-Means++

        上面我们提到，k个初始化的质心的位置选择对最后的聚类结果和运行时间都有很大的影响，因此需要选择合适的k个质心。如果仅仅是完全随机的选择，有可能导致算法收敛很慢。K-Means++算法就是对K-Means随机初始化质心的方法的优化。

K-Means++的对于初始化质心的优化策略也很简单，如下：

          a)  从输入的数据点集合中随机选择一个点作为第一个聚类中心μ1
　　   b) 对于数据集中的每一个点xi，计算它与已选择的聚类中心中最近聚类中心的距离:                                                                                             

                   这里我解释下吧，当选第一个点最为聚类中心后，此时聚类中心只有一个，这时会计算所有点到这一个聚类中心的距离，第二个聚类中心点的选取有很大概率会倾向于选择中距离比较大的，注意我的用语，不是一定就选取中最大的，因为这里涉及到了一个概率的问题，详细的过程这里我就不展开了，当选取了第二个聚类中心后，此时聚类中心有2个，这里也需要注意了，在计算距离的时候要取小，数学语言表达就是min（）, 这里其实也很好理解，因为距离较近的话，很容易会被分到距离较近的簇中，更多的聚类中心与此类似。

         c) 选择一个新的数据点作为新的聚类中心，选择的原则是：D(x)较大的点，被选取作为聚类中心的概率较大
　　  d) 重复b和c直到选择出k个聚类质心
　　  e) 利用这k个质心来作为初始化质心去运行标准的K-Means算法

距离计算优化elkan K-Means

       在传统的K-Means算法中，我们在每轮迭代时，要计算所有的样本点到所有的质心的距离，这样会比较的耗时。那么，对于距离的计算有没有能够简化的地方呢？elkan K-Means算法就是从这块入手加以改进。它的目标是减少不必要的距离的计算。那么哪些距离不需要计算呢？

　　elkan K-Means利用了两边之和大于等于第三边,以及两边之差小于第三边的三角形性质，来减少距离的计算。

        第一种规律是对于一个样本点x和两个质心μj1,μj2。如果我们预先计算出了这两个质心之间的距离D(j1,j2)，则如果计算发现2D(x,j1)≤D(j1,j2)我们立即就可以知道D(x,j1)≤D(x,j2)。此时我们不需要再计算D(x,j2),也就是说省了一步距离计算。

　第二种规律是对于一个样本点x和两个质心μj1,μj2。我们可以得到D(x,j2)≥max{0,D(x,j1)−D(j1,j2)}。这个从三角形的性质也很容易得到。

　　利用上边的两个规律，elkan K-Means比起传统的K-Means迭代速度有很大的提高。但是如果我们的样本的特征是稀疏的，有缺失值的话，这个方法就不使用了，此时某些距离无法计算，则不能使用该算法。

大样本优化Mini Batch K-Means

      在统的K-Means算法中，要计算所有的样本点到所有的质心的距离。如果样本量非常大，比如达到10万以上，特征有100以上，此时用传统的K-Means算法非常的耗时，就算加上elkan K-Means优化也依旧。在大数据时代，这样的场景越来越多。此时Mini Batch K-Means应运而生。

　　顾名思义，Mini Batch，也就是用样本集中的一部分的样本来做传统的K-Means，这样可以避免样本量太大时的计算难题，算法收敛速度大大加快。当然此时的代价就是我们的聚类的精确度也会有一些降低。一般来说这个降低的幅度在可以接受的范围之内。

　　在Mini Batch K-Means中，我们会选择一个合适的批样本大小batch size，我们仅仅用batch size个样本来做K-Means聚类。那么这batch size个样本怎么来的？一般是通过无放回的随机采样得到的。

　　为了增加算法的准确性，我们一般会多跑几次Mini Batch K-Means算法，用得到不同的随机采样集来得到聚类簇，选择其中最优的聚类簇。

2.4 K-means算法参数

K-means官网API

classsklearn.cluster.KMeans(n_clusters=8,init='kmeans++', n_init=10, max_iter=300, tol=0.0001, precompute_distances='auto', verbose=0, random_state=None, copy_x=True, n_jobs=1, algorithm='auto')¶

　KMeans类的主要参数有：

　　 1) n_clusters: 即我们的k值，一般需要多试一些值以获得较好的聚类效果。k值好坏的评估标准在下面会讲。

　　 2）max_iter： 最大的迭代次数，一般如果是凸数据集的话可以不管这个值，如果数据集不是凸的，可能很难收敛，此时可以指定最大的迭代次数让算法可以及时退出循环。

　　 3）n_init：用不同的初始化质心运行算法的次数。由于K-Means是结果受初始值影响的局部最优的迭代算法，因此需要多跑几次以选择一个较好的聚类效果，默认是10，一般不需要改。如果你的k值较大，则可以适当增大这个值。

　　 4）init： 即初始值选择的方式，可以为完全随机选择'random',优化过的'k-means++'或者自己指定初始化的k个质心。一般建议使用默认的'k-means++'。

　　 5）algorithm：有“auto”, “full” or “elkan”三种选择。"full"就是我们传统的K-Means算法， “elkan”是我们原理篇讲的elkan K-Means算法。默认的"auto"则会根据数据值是否是稀疏的，来决定如何选择"full"和“elkan”。一般数据是稠密的，那么就是 “elkan”，否则就是"full"。一般来说建议直接用默认的"auto"

K均值算法调参：

K值的评估标准：这里介绍的是轮廓系数Silhouette Coefficient

聚类的目标是让“组内数据尽量相似”而“组间数据差异明显”。轮廓系数Silhouette Coefficient就是为了衡量这一目标

轮廓系数定义：

针对每一条数据i
           a(i) :表示数据i与组内其他数据的平均距离
           b(i):表示数据i与距离最近的邻居组内的数据的平均距离

数据i的轮廓系数s(i)


计算所有数据点的轮廓系数s(i)均值
官网轮廓系数SilhouetteCoefficient的API

sklearn.metrics.silhouette_score(X, labels, metric='euclidean', sample_size=None, random_state=None, **kwds)¶

X：聚类的输入特征数据
labels：类标签数组
metric： [‘cityblock’, ‘cosine’, ‘euclidean’, ‘l1’, ‘l2’,‘manhattan’]，[‘braycurtis’, ‘canberra’, ‘chebyshev’,
‘correlation’, ‘dice’, ‘hamming’, ‘jaccard’, ‘kulsinski’,‘mahalanobis’, ‘matching’, ‘minkowski’,‘rogerstanimoto’, ‘russellrao’, ‘seuclidean’,‘sokalmichener’, ‘sokalsneath’, ‘sqeuclidean’, ‘yule’]
sample_size：是否抽样计算，默认None表示不抽样

Parameters:       
X : array [n_samples_a, n_samples_a] if metric == “precomputed”, or, [n_samples_a, n_features] otherwise
Array of pairwise distances between samples, or a feature array.
labels : array, shape = [n_samples]
Predicted labels for each sample.
metric : string, or callable
The metric to use when calculating distance between instances in a feature array. If metric is a string, it must be one of the options allowed by metrics.pairwise.pairwise_distances. If X is the distance array itself, use metric="precomputed".
sample_size : int or None
The size of the sample to use when computing the Silhouette Coefficient on a random subset of the data. If sample_size is None, no sampling is used.
random_state : int, RandomState instance or None, optional (default=None)
The generator used to randomly select a subset of samples. If int, random_state is the seed used by the random number generator; If RandomState instance, random_state is the random number generator; If None, the random number generator is the RandomState instance used by np.random. Used when sample_size is not None.
**kwds : optional keyword parameters
Any further parameters are passed directly to the distance function. If using a scipy.spatial.distance metric, the parameters are still metric dependent. See the scipy docs for usage examples.
Returns:       
silhouette : float
Mean Silhouette Coefficient for all samples.
3、聚类算法之密度聚类DBSCAN

       DBSCAN(Density-Based Spatial Clustering of Applications with Noise，具有噪声的基于密度的聚类方法)是一种很典型的密度聚类算法，和K-Means，BIRCH这些一般只适用于凸样本集的聚类相比，DBSCAN既可以适用于凸样本集，也可以适用于非凸样本集。

3.1密度聚类DBSCAN的基本原理

　   DBSCAN是一种基于密度的聚类算法，这类密度聚类算法一般假定类别可以通过样本分布的紧密程度决定。同一类别的样本，他们之间的紧密相连的，也就是说，在该类别任意样本周围不远处一定有同类别的样本存在。通过将紧密相连的样本划为一类，这样就得到了一个聚类类别。通过将所有各组紧密相连的样本划为各个不同的类别，则我们就得到了最终的所有聚类类别结果。

      密度聚类方法的指导思想，只要样本点的密度大于某阈值，则将该样本添加到最近的簇中，可发现容易形状的聚类，且对噪声数据不敏感，但计算密度单元的计算复杂度大。

3.2密度定义

        DBSCAN是基于一组邻域来描述样本集的紧密程度的，参数(ϵ, MinPts)用来描述邻域的样本分布紧密程度。其中，ϵ描述了某一样本的邻域距离阈值，MinPts描述了某一样本的距离为ϵ的邻域中样本个数的阈值。

　　假设样本集是D=(x1,x2,...,xm),则DBSCAN具体的密度描述定义如下：

　　1） ϵ-邻域：对于xj∈D，其ϵ-邻域包含样本集D中与xj的距离不大于ϵ的子样本集，即Nϵ(xj)={xi∈D|distance(xi,xj)≤ϵ}, 这个子样本集的个数记为|Nϵ(xj)|

　　2) 核心对象：对于任一样本xj∈D，如果其ϵ-邻域对应的Nϵ(xj)至少包含MinPts个样本，即如果|Nϵ(xj)|≥MinPts，则xj是核心对象。　

　　 3）密度直达：如果xi位于xj的ϵ-邻域中，且xj是核心对象，则称xi由xj密度直达。注意反之不一定成立，即此时不能说xj由xi密度直达, 除非且xi也是核心对象。

　　 4）密度可达：如果存在一个对象链，对是从关于(ϵ, MinPts)直接密度可达的，则对象p是从对象q关于(ϵ, MinPts)密度可达的。也就是说，密度可达满足传递性。此时序列中的传递样本均为核心对象，因为只有核心对象才能使其他样本密度直达。注意密度可达也不满足对称性，这个可以由密度直达的不对称性得出。

　　 5）密度相连：对于xi和xj,如果存在核心对象样本xk，使xi和xj均由xk密度可达，则称xi和xj密度相连。注意密度相连关系是满足对称性的。

        从下图可以很容易看出理解上述定义，图中MinPts=5，红色的点都是核心对象，因为其ϵ-邻域至少有5个样本。黑色的样本是非核心对象。所有核心对象密度直达的样本在以红色核心对象为中心的超球体内，如果不在超球体内，则不能密度直达。图中用绿色箭头连起来的核心对象组成了密度可达的样本序列。在这些密度可达的样本序列的ϵ-邻域内所有的样本相互都是密度相连的。



3.3DBSCAN聚类算法

     输入：样本集D=(x1,x2,...,xm)，邻域参数(ϵ,MinPts) 样本距离度量方式

　 输出： 簇划分C.　

　　　1）初始化核心对象集合Ω=∅, 初始化聚类簇数k=0，初始化未访问样本集合Γ = D,  簇划分C = ∅

　　　2) 对于j=1,2,...m, 按下面的步骤找出所有的核心对象：

　　　　a) 通过距离度量方式，找到样本xj的ϵ-邻域子样本集Nϵ(xj)

　　　　b) 如果子样本集样本个数满足|Nϵ(xj)|≥MinPts， 将样本xj加入核心对象样本集合：Ω=Ω∪{xj}

　　　3）如果核心对象集合Ω=∅，则算法结束，否则转入步骤4.

　　　4）在核心对象集合Ω中，随机选择一个核心对象，初始化当前簇核心对象队列, 初始化类别序号k=k+1，初始化当前簇样本集合, 更新未访问样本集合Γ=Γ−{o}

　　　　5）如果当前簇核心对象队列Ωcur=∅，则当前聚类簇Ck生成完毕, 更新簇划分C={C1,C2,...,Ck}, 更新核心对象集合Ω=Ω−Ck， 转入步骤3。

　　　　6）在当前簇核心对象队列Ωcur中取出一个核心对象o′,通过邻域距离阈值ϵ找出所有的ϵ-邻域子样本集Nϵ(o′)，令Δ=Nϵ(o′)∩Γ, 更新当前簇样本集合Ck=Ck∪Δ, 更新未访问样本集合Γ=Γ−Δ,  更新Ωcur=Ωcur∪(Δ∩Ω)−o′，转入步骤5.

　　　　输出结果为： 簇划分C={C1,C2,...,Ck}

官网参数：sklearn.cluster.DBSCAN API

class sklearn.cluster.DBSCAN(eps=0.5, min_samples=5, metric='euclidean', metric_params=None, algorithm='auto', leaf_size=30, p=None, n_jobs=1)¶

         1）eps： DBSCAN算法参数，即我们的ϵ-邻域的距离阈值，和样本距离超过ϵ的样本点不在ϵ-邻域内。默认值是0.5.一般    需要通过在多组值里面选择一个合适的阈值。eps过大，则更多的点会落在核心对象的ϵ-邻域，此时我们的类别数可能会减少， 本来不应该是一类的样本也会被划为一类。反之则类别数可能会增大，本来是一类的样本却被划分开。

　　 2）min_samples： DBSCAN算法参数，即样本点要成为核心对象所需要的ϵϵ-邻域的样本数阈值。默认值是5. 一般需要通 过在多组值里面选择一个合适的阈值。通常和eps一起调参。在eps一定的情况下，min_samples过大，则核心对象会过少，此时簇内部分本来是一类的样本可能会被标为噪音点，类别数也会变多。反之min_samples过小的话，则会产生大量的核心对象，可能会导致类别数过少。

　　 3）metric：最近邻距离度量参数。

        4）algorithm：最近邻搜索算法参数，算法一共有三种，第一种是蛮力实现，第二种是KD树实现，第三种是球树实现。对于这个参数，一共有4种可选输入，‘brute’对应第一种蛮力实现，‘kd_tree’对应第二种KD树实现，‘ball_tree’对应第三种的球树实现， ‘auto’则会在上面三种算法中做权衡，选择一个拟合最好的最优算法。需要注意的是，如果输入样本特征是稀疏的时候，无论我们选择哪种算法，最后scikit-learn都会去用蛮力实现‘brute’。个人的经验，一般情况使用默认的 ‘auto’就够了。 如果数据量很大或者特征也很多，用"auto"建树时间可能会很长，效率不高，建议选择KD树实现‘kd_tree’，此时如果发现‘kd_tree’速度比较慢或者已经知道样本分布不是很均匀时，可以尝试用‘ball_tree’。而如果输入样本是稀疏的，无论你选择哪个算法最后实际运行的都是‘brute’。

　　 5）leaf_size：最近邻搜索算法参数，为使用KD树或者球树时， 停止建子树的叶子节点数量的阈值。这个值越小，则生成的KD树或者球树就越大，层数越深，建树时间越长，反之，则生成的KD树或者球树会小，层数较浅，建树时间较短。默认是30. 因为这个值一般只影响算法的运行速度和使用内存大小，因此一般情况下可以不管它。

　　 6） p: 最近邻距离度量参数。只用于闵可夫斯基距离和带权重闵可夫斯基距离中p值的选择，p=1为曼哈顿距离， p=2为欧式距离。如果使用默认的欧式距离不需要管这个参数。

4、聚类算法之谱聚类（spectral clustering）

      谱聚类（spectral clustering）是广泛使用的聚类算法，比起传统的K-Means算法，谱聚类对数据分布的适应性更强，聚类效果也很优秀，同时聚类的计算量也小很多，更加难能可贵的是实现起来也不复杂。在处理实际的聚类问题时，谱聚类是应该首先考虑的几种算法之一。

        说实话，由于自己对谱聚类的算法推导过程还有疑惑，这其中涉及矩阵分析，图论，以及中间的一些推导，故这里也不在写出谱聚类的算法推导过程，以免贻笑大方，哪天真正弄懂了，没有疑问了，再补充上来，这里只给出谱聚类算法流程。

        输入：样本集D=(x1,x2,...,xn)，相似矩阵的生成方式, 降维后的维度k1, 聚类方法，聚类后的维度k2

　　 输出： 簇划分C(c1,c2,...ck2).　

　　　　1) 根据输入的相似矩阵的生成方式构建样本的相似矩阵S

　　　　2）根据相似矩阵S构建邻接矩阵W，构建度矩阵D

　　　　3）计算出拉普拉斯矩阵L

　　　　4）构建标准化后的拉普拉斯矩阵

　　　　5）计算最小的k1个特征值所各自对应的特征向量

　　　　6) 将各自对应的特征向量组成的矩阵按行标准化，最终组成维的特征矩阵F

　　　　7）对F中的每一行作为一个k1维的样本，共n个样本，用输入的聚类方法进行聚类，聚类维数为k2。

　　　　8）得到簇划分C(c1,c2,...ck2)　　

谱聚类算法的主要优点有：

　　1）谱聚类只需要数据之间的相似度矩阵，因此对于处理稀疏数据的聚类很有效。这点传统聚类算法比如K-Means很难做到

　　2）由于使用了降维，因此在处理高维数据聚类时的复杂度比传统聚类算法好。

谱聚类算法的主要缺点有：

　　1）如果最终聚类的维度非常高，则由于降维的幅度不够，谱聚类的运行速度和最后的聚类效果均不好。

　　2) 聚类效果依赖于相似矩阵，不同的相似矩阵得到的最终聚类效果可能很不同。

谱聚类算法的参数

       在scikit-learn的类库中，sklearn.cluster.SpectralClustering实现了基于Ncut的谱聚类，没有实现基于RatioCut的切图聚类。同时，对于相似矩阵的建立，也只是实现了基于K邻近法和全连接法的方式，没有基于ϵϵ-邻近法的相似矩阵。最后一步的聚类方法则提供了两种，K-Means算法和 discretize算法。

　　对于SpectralClustering的参数，我们主要需要调参的是相似矩阵建立相关的参数和聚类类别数目，它对聚类的结果有很大的影响。当然其他的一些参数也需要理解，在必要时需要修改默认参数。

官网SpectralClustering API

class sklearn.cluster.SpectralClustering(n_clusters=8, eigen_solver=None, random_state=None, n_init=10, gamma=1.0, affinity='rbf', n_neighbors=10, eigen_tol=0.0, assign_labels='kmeans', degree=3, coef0=1, kernel_params=None, n_jobs=1)¶
---------------------
【转载】
作者：不曾走远~
原文：https://blog.csdn.net/qq_20412595/article/details/82251232

---

作者: 不二晨    时间: 2018-10-25 10:45

---

作者: 魔都黑马少年梦    时间: 2018-11-1 16:20

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2