本文共 5502 字，大约阅读时间需要 18 分钟。
总述：聚类分析是寻找数据当中高数据浓度的集合，这些高数据浓度的集合可以辅助后续的数据规约、数据变换、数据分类等操作。这些具体的处理方法需要根据实际的业务数据需要进行配合。
1、什么是聚类分析
答：将物理或抽象对象的集合分成相似对象类的过程为聚类。簇是数据对象的集合，这些对象与同一个簇内的对象彼此相似，与其他簇中的对象相异。聚类在某些应用中也称为数据分割，因为聚类根据数据相似性把大型数据集合划分成组。聚类也可以用于离群点检测，离群点是不在任何聚类分组中的点，多用于异常数据业务分析。数据挖掘对聚类分析的要求有：可伸缩性、处理不同类型属性的能力、发现任意形状的聚类、对于决定输入参数的领域知识需求最小、处理带噪声数据的能力、增量聚类和对输入记录的次序不敏感、高维性、基于约束的聚类、可解释性和可用性。聚类是观察式学习，不同于前面分类部分的内容，分类部分的内容属于示例式学习。
2、聚类分析中的数据类型
答：基于内存的聚类算法通常选择数据矩阵、相异度矩阵两种数据结构进行。数据矩阵是表示簇中多个对象，对象可以包含多个维度的信息描述，矩阵的每一个列或者行都是一个对象。相异度矩阵是描述一个簇中所有对象的差异，是一个对称矩阵，对角线上全为0。d（i，j）和d（j，i）是相等的，表示第i个对象和第j的对象的差异度，其值是一个大于0的数值，越接近0就是差异度越小。数据矩阵常称为二模矩阵，相异度举证称为单模矩阵。
区间标度变量是一种粗略线性标度的连续度量。选用的度量单位会影响聚类分析的结果，统一度量单位则需要使用一些数学方法：第一种是采用均值的绝对偏差，Sf=（每个簇内的点距离均值点的距离之和）/（簇内点的个数）；第二种是标准度量，采用z-score值Zif=（簇内第i点距离均值点的距离）/（均值的绝对偏差Sf）。这些方法都是为了度量聚类中关键的条件数据时使用的。二元以上变量的比较除了用多维空间点与点之间的距离公式之外，还可以采用人为规定的加权计算的方式，无论怎么去度量，都需要定义多元变量的比较规则。
对象之间的相异度因为可以规定比较规则，必然可以得到大小，可以按照大小规则进行排序、分类，这与一维的变量没有什么区别。如果无法比较对象之间的大小，那么一定是没有定义比较规则或者忽视了比较规则。
3、主要聚类方法的分类
答：第一种，划分方法，给定n个对象或数据元组的数据库，划分方法构建数据的k个划分，每个划分表示一簇，k<=n。该方法首先创建一个初始划分，然后再用迭代重定位技术，尝试通过对象在组间移动来改进划分。好的划分准则是：簇内对象相似，簇间对象不同。比较流行的划分方法有k均值算法、k中心点算法。
第二种，层次方法，创建给定数据对象集的层次分解。根据层次分解的形成方式，层次方法可以分类为凝聚的或分裂的方法。凝聚法是自底向上，向上凝聚到终止条件或者最顶层次；分裂法是自顶向下，将所有对象置于一个簇中，然后进行迭代，簇分裂为更小的簇，直到每一个对象都存在于某一个簇中或满足终止条件。层次方法一旦开始就不可以终止，中途不可以更正错误的决定。
第三种，基于密度的方法，只要邻域中的密度超过某个阈值，就继续聚类。这个方法发现任意形状的簇，也可以过滤噪声数据。基于密度方法的代表是DBSCAN算法和其扩展算法OPTICS、DENCLUE算法。
第四种，基于网格的方法，基于网格的方法把对象空间量化为有限数目的单元，形成一个网格结构。所有的聚类操作都在这个网格上进行。这种方法的优点是处理速度很快，代表方法是STING算法。
第五种，基于模型的方法，基于模型的方法为每簇假定一个模型，并寻找数据对给定模型的最佳拟合。基于模型的算法通过构建反应数据点空间分布的密度函数来定位簇，会自动确定簇的数目，也同时考虑离群点数据和噪声数据，产生抗干扰的聚类方法。基于模型的方法中，代表性的算法有EM、COBWEB、SOM等。
聚类算法的选择既依赖于可用的数据类型，也依赖于应用的特定目标。除了上述聚类方法，还有两类聚类任务需要特别关注，分别是聚类高维数据和基于约束的聚类。聚类高维数据存在的难点在于大量的数据特征项或者维数、数据点稀疏。基于约束的聚类存在的难点在于约束条件对聚类空间的切割。
4、划分方法的常用方法
答：k均值方法，也称为基于质心的技术，算法处理流程如下：1、随机选择k个对象，每个对象代表一个簇的初始均值或中心；2、对剩余的每个对象，根据其余各个簇均值的距离，将其指派到最相似的簇，然后重新计算每个簇的新均值；3、重复步骤2，直到准则函数收敛。这种算法对簇之间分离比较明显的数据效果较好，具有相对可伸缩和有效率的，经常终止于局部最优解。此算法不适合发现非凸形状的簇或者大小差别很大的簇，对噪声和离群点是敏感的。
看均值方法有一些变种，会对初始k个均值的选择、相异度的计算、计算簇均值的策略做出一些改变，可以对聚类结果做出改善。常用的改善策略是先采用层次凝聚算法决定簇的数目并找到一个初始类，然后用迭代重定位来改进聚类。k均值方法提高伸缩性的方法应从数据规约方面进行考虑。
k中心点方法是对k均值方法的一种改进，它在算法处理的时候，每个簇的中心是会发生变化的，每当新加入对象的时候，就重新计算绝对误差标准，将绝对误差标准值最小的点定义为新的中心，依次迭代直到满足终止条件。k中心点法的算法执行代价要比k均值方法代价要高，不过k中心点法对噪声和离群点是不敏感的。
k中心方法的应用到大型数据集合上有一些困难，可以采用抽样的方法从大型数据集合上抽取一个小型的样本，在这个小型的样本上进行运行。样本的质量决定了k中心方法的有效性，所以根据数据的情况按比例抽取的样本是质量最好的样本。
5、层次方法的常用方法
答：层次方法分为凝聚和分裂两大类，在这两种算法中，终止条件的设定是关键之处，实际操作中通常指定一个距离的值，凝聚算法的凝聚距离如果超过这个限制就停止凝聚，分裂算法的分裂距离如果小于这个限制就停止分裂。在分裂或者凝聚过程中，最常遇到的困难是分裂点或合并点选择困难的问题，解决这种问题时需要检查和估算大量的对象或簇来决定选择结果。层次类方法中：BIRCH先用树结构对对象进行层次划分，叶节点或低层次的非叶节点可以看做由分辨率决定的微簇，然后使用其他聚类算法处理微簇的聚类；ROCK方法是基于簇间互联性进行合并；Chameleon方法探查层次聚类的动态建模。
BIRCH方法，利用层次方法的平衡迭代规约和聚类。BITCH引入了聚类特征和聚类特征树，使得这个方法克服了可伸缩性和对象增量难题。这个方法的算法分为两个主要的阶段：第一个阶段，先扫描数据库，建立一颗存放于内存的初始CF树，这是一种高度平衡的树，可以看做是数据的多层压缩，试图保存数据内在的聚类结构，主要作用是建立一个主体结构；第二阶段是采用某个聚类算法对CF树的叶子节点进行聚类，把稀疏的簇当做离群点删除而把稠密的簇合并为更大的簇。算法运行的最后产生的结果非常类似于B+树。
ROCK是一种层次聚类算法，针对具有分类属性的数据使用链接。算法的核心思想：如果两个数据点是近邻，定义它们的之间共同近邻个数为它们之间的链接，链接数越大则它们在同一个簇内的可能性越高。这种算法可以更加有效的产生有意义的聚类结果。这种算法思想考虑了相似度阈值和共享近邻的概念，先构件一个稀疏图，然后使用优先度度量评价聚类。
Chameleon（变色龙）是一种层次聚类算法，采用动态建模确定簇对之间相似度。这种聚类算法的操作步骤如下：1、采用k最近邻图的方法构建一个稀疏图，图的每个顶点代表一个数据对象，如果一个对象是另一个对象的k个最类似对象之一，那么两个对象之间存在一条边。这些边加权后反应对象间的相似度。2、然后采用凝聚层次聚类算法，基于子簇的相似度反复合并子簇，合并过程中既要考虑簇的互联性，也要考虑簇的接近度。
6、基于密度的方法
答：DBSCAN是一种基于密度的聚类算法，将具有足够高密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇。DBSCAN通过检查数据库中每点的邻域来搜索簇，如果簇的邻域包含的点多于簇最低密度阈值个，则创建一个以p为核心对象的新簇。然后DBSCAN迭代聚集这些从核心对象直接密度可达的对象，一直到没有新的点可以添加到任何簇时结束。
OPTICS是一种基于密度的聚类算法，针对DBSCAN中邻域长度设定难点上进行改进，算法对DBSCAN算法进行扩展，在处理过长中保存核心对象间的核心距离（即邻域半径）和对象间的可达距离（对象所属的核心对象核心距离和对象与其他对象的欧几里得距离的较大者），这样再扫描完成全部对象之后可以根据这两个长度信息产生排除，最后提取簇即可。
DENCLUE是一种基于密度分布函数的聚类，算法基于：1、每个数据点的影响可以用一个数学函数形式化建模，该函数称为影响函数，描述数据点在邻域内的影响；2、数据空间的整体密度可以用所有数据点的影响函数的和建模；3、簇可以设备密度吸引点数学确认，其中密度吸引点是全局密度函数的局部极大值。
7、基于网格的方法
答：STING是基于网格多分辨率聚类技术，这是一种自顶向下的聚类技术，先处理高层信息再处理底层信息，数据处理的精度取决于最底层网格的数据精度。这种网格划分属于硬性划分，不考虑相邻网格之间的联系，但是这种处理方法处理数据的效率很不错，支持增量处理和并行处理。
WaveCluster是一种多分辨率聚类算法，首先通过在数据空间强加一个多维网格结构汇总数据，然后采用小波变换来变换原特征空间，在变换后的空间中发现密集区域。这种算法可以通过小波变换自动排除离群点，在不同分辨率下发现不同精度的聚类，效率比较高，事实上这种算法是基于网格和基于密度的算法。
8、基于模型的聚类方法
答：基于模型的聚类方法试图优化给定数据和某数学模型之间的拟合。这种方法经常基于这样的假设：数据根据潜在的混合概率分布生成。这种算法的使用都是在验证某些结论或者尝试去发现数据的规律。
EM（期望最大化）算法是一种流行的迭代算法，可以求得参数的估计值。这种算法可以看做是k均值算法的一种扩展，基于簇的均值把对象指派到最相似的簇中，然后根据一个代表隶属概率的权值将每个对象指派簇中，新的均值基于加权的度量来计算。EM算法简单易实现，收敛速度很快，可能达不到全局最优。
概念聚类是一种机器学习聚类方法，给定一组未标记的对象，产生对象的分类模式。这类方法一般分为两个过程，第一个过程是先进行聚类，第二个过程是给出特征描述。COBWEB以分类树的形式创建层次聚类，处理离散性的数据；CLASSIT是COBWEB的扩展，处理连续性数据的增量聚类。这种方法主要流行于机器学习界。
神经网络聚类方法经每一个簇描述为一个标本，标本充当簇的原型。根据某种距离的度量，新的对象可以分布到其标本最相似的簇。分配给簇的对象属性可以根据该簇的标本属性来预测。SOM（自组织特征映射）是最流行的神经网络聚类分析方法之一，该方法已经成功应用到Web文档聚类。
9、聚类高维数据
答：聚类高维数据与聚类低维数据不同，高维数据通常是呈现出稀疏的特征，常用的操作方法是做数据规约提高数据的密集程度，但是这种变换和规约有时效果也不好，于是进一步提出了删除无关维度数据或者无效的数据，最后甚至是进行子空间聚集。高维数据聚类的代表性算法有：以CLIQUE为代表的维增长子空间聚集、以PROCLUS为代表的维规约投影聚类、以pCluster为代表的基于频繁模式的聚类。
维增长子空间聚集算法的聚类过程开始于单维子空间，并且向上增长至更高维的子空间。由于CLIQUE把每一个维划分成网格状的结构，并且根据每个网格单元包含的点数目确定网格单元是否稠密，可以看做是一种基于密度和基于网格的一种聚类方法集成。
PROCLUS是一种维规约子空间聚类方法，算法由三个阶段组成。初始化阶段，使用贪心算法选择一组彼此距离很远的初始中心点，确保每个簇都能由其中至少一个对象来代表。迭代阶段，从这个规约后的集合中随机选择k个中心点，随机选择新中心店取代那些不好的中心点，然后比较取代之前的点 ，如果更加符合期望则替换掉原先的中心点，最终选择出一组平均距离小于统计期望值的维集合。改进阶段基于发现簇，为每个中心点计算新的为，把数据点分配给中心点，删除离群点。
还可以使用基于频繁模式的聚类方法，具体操作方法请查阅其他文档。
10、基于约束的聚类分析
答：聚类分析中存在约束是一种常见的情况，约束主要来自于用户的偏好、参数设定、操作等。在这种情况下的聚类分析必须考虑约束对聚类过程造成的影响，有许多方法：从正面思考，将约束视为障碍物，对于以立体方式处理的聚类很有效；从反面思考，将约束条件视为一种分类规则；从侧面思考，用户可以不断调整参数边界的，则先将数据设定为与参数相关的聚类，然后再进行处理。
11、离群点分析
答：前面的处理主要是面向聚类的数据点，最后这部分是处理离群点的。离群点在某些情况下也是存在业务意义的，在这种情况下分析离群点的特征是需要认真考虑的。离群点的分析方法有统计学方法、基于距离的方法、基于密度的局部离群点方法、基于偏差的方法等这四大类。
转载地址：http://kqpdi.baihongyu.com/