cluster法（聚类分析（cluster analysis））

本文目录

• 聚类分析（cluster analysis)
• 如何运用聚类分析法

聚类分析（cluster analysis)

我们这里来看看聚类分析。 比较流行的有聚类方法有k均值聚类,属于分割式聚类的方法。 K-Means算法的思想很简单，对于给定的样本集，按照样本之间的距离大小，将样本集划分为K个簇。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大。目的是最小化E=sum(x-\miu_i), 其中\miu_i是每个簇的均值。 直接求上式的最小值并不容易，这是一个NP难的问题，因此采用启发式的迭代方法K-Means。 K-Means很简单，用下面一组图就可以形象的描述。上图a表达了初始的数据集，假设k=3。在图b中，我们随机选择了三个k类所对应的类别质心，即图中的红绿和草绿色质心，然后分别求样本中所有点到这三个质心的距离，并标记每个样本的类别为和该样本距离最小的质心的类别，如图c所示，经过计算样本和红绿和草绿色质心的距离，我们得到了所有样本点的第一轮迭代后的类别。此时我们对我们当前标记为红绿和草绿色点分别求其新的质心，重复了这个过程，将所有点的类别标记为距离最近的质心的类别并求新的质心。最终我们得到的三个类别如图。首先我们看看K-Means算法的一些要点。 1 对于K-Means算法，首先要注意的是k值的选择，一般来说，我们会根据对数据的先验经验选择一个合适的k值，如果没有什么先验知识，则可以通过交叉验证选择一个合适的k值。 2 在确定了k的个数后，我们需要选择k个初始化的质心，就像上图b中的随机质心。由于我们是启发式方法，k个初始化的质心的位置选择对最后的聚类结果和运行时间都有很大的影响，因此需要选择合适的k个质心，最好这些质心不能太近。 传统的K-Means算法流程。 输入样本集合，然后划分成k 人为分类，凭经验将样品进行初步的分类 选择凝聚点后，求均值，求距离，归类 更新质心 重新求均值和距离，再重新归类   大样本优化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算法，用得到不同的随机采样集来得到聚类簇，选择其中最优的聚类簇。 K-Means与KNN K-Means是无监督学习的聚类算法，没有样本输出；而KNN是监督学习的分类算法，有对应的类别输出。KNN基本不需要训练，对测试集里面的点，只需要找到在训练集中最近的k个点，用这最近的k个点的类别来决定测试点的类别。而K-Means则有明显的训练过程，找到k个类别的最佳质心，从而决定样本的簇类别。 两者也有一些相似点，两个算法都包含一个过程，即找出和某一个点最近的点。两者都利用了最近邻(nearest neighbors)的思想。 KNN(K-NearestNeighbor）分类算法是数据挖掘分类技术中最简单的方法之一。所谓K最近邻，就是K个最近的邻居的意思，说的是每个样本都可以用它最接近的K个邻近值来代表。近邻算法就是将数据集合中每一个记录进行分类的方法。 总体来说，KNN分类算法包括以下4个步骤：  1准备数据，对数据进行预处理  2计算测试样本点（也就是待分类点）到其他每个样本点的距离  3对每个距离进行排序，然后选择出距离最小的K个点  4对K个点所属的类别进行比较，根据少数服从多数的原则，将测试样本点归入在K个点中占比最高的那一类 该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数 , 该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点 。 K-Means小结 K-Means的主要优点有： 1）原理比较简单，实现也是很容易，收敛速度快。 2）聚类效果较优。 3）算法的可解释度比较强。 4）主要需要调参的参数仅仅是簇数k。 K-Means的主要缺点有： 1）K值的选取不好把握 2）对于不是凸的数据集比较难收敛 3）如果各隐含类别的数据不平衡，比如各隐含类别的数据量严重失衡，或者各隐含类别的方差不同，则聚类效果不佳。 4） 采用迭代方法，得到的结果只是局部最优。 5） 对噪音和异常点比较的敏感。 PAM算法。 PAM法和K-means法很相似，但是它保证跑出来你的数据是最优的，和k-means不一样的是，虽然它也随机选择群中心，但是群中心的选择并非虚拟的，而是选取真正的数据点作为群中心。比如一开始选择3和20两个点作为群中心，并得到SS值。然后用不同的点去替换3或者20，选择最小SS值的点作为新的群中心，依次类推，直到SS值不能进一步优化。然后根据最后的群中心去聚类。PAM算法能够处理非数值类型的字段，但是其效率很慢，难以处理大数据量的情况。 除了分割聚类的方法,还有阶层式聚类的方法。我们看看ward方法。 华德法（ Ward’s Method ）:  华德法是阶层式聚类分析法中效果最好的，但是其运算速度较慢。理论差平方是判断聚类效果好不好的一个指标（每个资料点同群中心距离的平方和），其计算方式如下，SS值最小则说明聚类效果最好。华德法采用了一个取巧的方法，保证效果最好，仍然以上述例子示范。第一次聚类（聚成4类）有十种可能性，选择AB使得SS值最小，第二次（聚成3类）选择DE使得SS最小，第三次（聚成2类）选择CDE使得SS最小，直到聚成一类。 聚类分析是非常有用的,比如在公司可以给客户分类,或者说客户画像。如何了解用户的需求，把握用户的期望，对迅速对用户作出精准的投放这些手段已经成为企业能否的关键了。 某移动运营商在5月发展了19999个新用户，在新用户入网后一个月后，1、希望通过提供一些优惠提高用户的忠诚度  2、希望通过推荐一些产品提升客单价。 为达到这一目的，我们需要对新用户进行洞察，弄清楚以下的问题: a、应该给客户提供什么优惠？ 我们的优惠能否给客户带来惊喜？不同的客户是否该根据他们的喜好提供不同的优惠？b、客户对我们的什么产品感兴趣？不同的客户是否应该推荐不同的产品？ 这个时候就可以使用聚类分析。

如何运用聚类分析法

聚类分析法是理想的多变量统计技术，主要有分层聚类法和迭代聚类法。聚类通过把目标数据放入少数相对同源的组或“类”（cluster）里。分析表达数据，（1）通过一系列的检测将待测的一组基因的变异标准化，然后成对比较线性协方差。（2）通过把用最紧密关联的谱来放基因进行样本聚类，例如用简单的层级聚类（hierarchical clustering）方法。这种聚类亦可扩展到每个实验样本，利用一组基因总的线性相关进行聚类。（3）多维等级分析（multidimensional scaling analysis,MDS）是一种在二维Euclidean “距离”中显示实验样本相关的大约程度。（4）K-means方法聚类，通过重复再分配类成员来使“类”内分散度最小化的方法。聚类方法有两个显著的局限：首先，要聚类结果要明确就需分离度很好（well-separated）的数据。几乎所有现存的算法都是从互相区别的不重叠的类数据中产生同样的聚类。但是，如果类是扩散且互相渗透，那么每种算法的的结果将有点不同。结果，每种算法界定的边界不清，每种聚类算法得到各自的最适结果，每个数据部分将产生单一的信息。为解释因不同算法使同样数据产生不同结果，必须注意判断不同的方式。对遗传学家来说，正确解释来自任一算法的聚类内容的实际结果是困难的（特别是边界）。最终，将需要经验可信度通过序列比较来指导聚类解释。第二个局限由线性相关产生。上述的所有聚类方法分析的仅是简单的一对一的关系。因为只是成对的线性比较，大大减少发现表达类型关系的计算量，但忽视了生物系统多因素和非线性的特点。从统计学的观点看，聚类分析是通过数据建模简化数据的一种方法。传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。采用k-均值、k-中心点等算法的聚类分析工具已被加入到许多著名的统计分析软件包中，如SPSS、SAS等。从机器学习的角度讲，簇相当于隐藏模式。聚类是搜索簇的无监督学习过程。与分类不同，无监督学习不依赖预先定义的类或带类标记的训练实例，需要由聚类学习算法自动确定标记，而分类学习的实例或数据对象有类别标记。聚类是观察式学习，而不是示例式的学习。从实际应用的角度看，聚类分析是数据挖掘的主要任务之一。就数据挖掘功能而言，聚类能够作为一个独立的工具获得数据的分布状况，观察每一簇数据的特征，集中对特定的聚簇集合作进一步地分析。聚类分析还可以作为其他数据挖掘任务（如分类、关联规则）的预处理步骤。数据挖掘领域主要研究面向大型数据库、数据仓库的高效实用的聚类分析算法。 聚类分析是数据挖掘中的一个很活跃的研究领域，并提出了许多聚类算法。这些算法可以被分为划分方法、层次方法、基于密度方法、基于网格方法和基于模型方法。1 划分方法(PAM:PArtitioning method) 首先创建k个划分，k为要创建的划分个数；然后利用一个循环定位技术通过将对象从一个划分移到另一个划分来帮助改善划分质量。典型的划分方法包括：k-means,k-medoids,CLARA(Clustering LARge Application),CLARANS(Clustering Large Application based upon RANdomized Search). FCM2 层次方法(hierarchical method) 创建一个层次以分解给定的数据集。该方法可以分为自上而下（分解）和自下而上（合并）两种操作方式。为弥补分解与合并的不足，层次合并经常要与其它聚类方法相结合，如循环定位。典型的这类方法包括：第一个是;BIRCH(Balanced Iterative Reducing and Clustering using Hierarchies) 方法，它首先利用树的结构对对象集进行划分；然后再利用其它聚类方法对这些聚类进行优化。第二个是CURE(Clustering Using REprisentatives) 方法，它利用固定数目代表对象来表示相应聚类；然后对各聚类按照指定量（向聚类中心）进行收缩。第三个是ROCK方法，它利用聚类间的连接进行聚类合并。最后一个CHEMALOEN，它则是在层次聚类时构造动态模型。3 基于密度方法，根据密度完成对象的聚类。它根据对象周围的密度（如DBSCAN）不断增长聚类。典型的基于密度方法包括： DBSCAN(Densit-based Spatial Clustering of Application with Noise):该算法通过不断生长足够高密度区域来进行聚类；它能从含有噪声的空间数据库中发现任意形状的聚类。此方法将一个聚类定义为一组“密度连接”的点集。 OPTICS(Ordering Points To Identify the Clustering Structure):并不明确产生一个聚类，而是为自动交互的聚类分析计算出一个增强聚类顺序。。4 基于网格方法，首先将对象空间划分为有限个单元以构成网格结构；然后利用网格结构完成聚类。 STING(STatistical INformation Grid) 就是一个利用网格单元保存的统计信息进行基于网格聚类的方法。 CLIQUE(Clustering In QUEst)和Wave-Cluster 则是一个将基于网格与基于密度相结合的方法。5 基于模型方法，它假设每个聚类的模型并发现适合相应模型的数据。典型的基于模型方法包括： 统计方法COBWEB:是一个常用的且简单的增量式概念聚类方法。它的输入对象是采用符号量（属性-值）对来加以描述的。采用分类树的形式来创建一个层次聚类。 CLASSIT是COBWEB的另一个版本.。它可以对连续取值属性进行增量式聚类。它为每个结点中的每个属性保存相应的连续正态分布（均值与方差）；并利用一个改进的分类能力描述方法，即不象COBWEB那样计算离散属性（取值）和而是对连续属性求积分。但是CLASSIT方法也存在与COBWEB类似的问题。因此它们都不适合对大数据库进行聚类处理.