商务智能-聚类分析

聚类分析基础聚类算法目录2基于聚类的异常检测3高级聚类方法4基本概念11基本概念聚类分析(ClusterAnalysis)简称聚类（clustering），是把一个数据对象划分子集的过程。每个子集是一个簇，使得同一簇内的对象具有尽可能高的同质性(homogeneity)，而与其他簇中的对象之间则应具有尽可能高的异质性(heterogeneity)。由聚类分析产生的簇的集合称作一个聚类。

聚类分析是一种非监督学习，处理的数据对象集是无类别标记的，算法需要对原始数据的特征进行探索，进而挖掘出一些数据对象之间的共性特点。1基本概念聚类的过程通常包括如下阶段：

（1）数据准备：包括对数据特征进行标准化、属性降维、噪音处理；（2）特征选择：从最初的特征集中选择最有代表性的特征或特征组合，并将其存储于向量中；（3）特征提取：通过对所选择的特征进行转换进而形成新的特征；（4）聚类：选择适合特征类型的某种距离函数进行接近度或相似度的测量，而后根据距离进行聚类或分组；（5）结果评估：对聚类结果进行评估，评估主要有3种：外部有效性评估、内部有效性评估和相关性测试评估。2基础聚类算法聚类是将研究对象分为相对同质的群组或簇技术，现有研究和文献中有大量关于聚类的算法和技术。聚类的主要基础算法，包括如下几类：划分方法（partitioningmethod）、层次方法（hierarchicalmethod）、基于密度方法（density-basedmethod）和基于网格方法（grid-basedmethod）。2基础聚类算法划分方法（partitioningmethod）聚类分析中最简单、最基本的方法是划分。给定一个具有n个对象的数据集，划分方法（PartitionMethods）构建数据的k个分区，其中每个分区代表一个簇，并且k≤n。也就是说，划分方法把数据划分为K个组，使得每个组至少包含一个对象，且每个对象只能属于一个组。目前常用的划分方法有如下几种：K-means算法与K-medoids算法2基础聚类算法划分方法（partitioningmethod）K-means算法：给定一个数据集和需要划分的簇的数目k后，该算法根据某个距离函数反复把数据划分到k个簇中，直至收敛。算法：K-means输入：包含n个对象的数据库，簇的数目k输出：k个簇，使平方误差最小步骤：（1） 任选k个对象作为初始的簇中心；（2） repeat（3） 根据与每个中心的距离，将每一对象赋给“最近”的簇（4） 重新计算每个簇的平均值（5） Until不再发生变化2基础聚类算法划分方法（partitioningmethod）首先在数据集中随机抽取的k个对象，每个对象代表一个簇的初始均值或簇中心，然后计算每个数据点到每个簇中心的距离，并把每个数据点分配到离它最近的簇中心；一旦所有的数据点都被分配完成，每个聚类的簇中心按照本聚类的现有数据点重新计算；该过程不断重复，直至收敛，即满足某个终止条件为止，最常见的终止条件是误差平方和局部最小。2基础聚类算法划分方法（partitioningmethod）

2基础聚类算法划分方法（partitioningmethod）K-medoids算法：又叫K中心点算法，K-Medoids算法是用簇中最靠近中心点的一个真实数据对象来代表该簇，而K-means算法是用计算出来的簇中对象的平均值来代表该簇。算法：K-medoids输入：包含n个数据对象的集合，簇的数目k输出：k个簇步骤：（1）任意选取k个初始中心点(medoids)；（2）repeat（3）按照与medoids最近的原则，将剩余点分配到当前最佳的medoids所代表的类或簇中（4）在每一类或簇中，计算每个样本点与其他点的距离之和，选取距离之和最小的点作为新的medoids（5）Until重复(3)(4)的过程，直到所有的中心点（medoids）不再发生变化，或已达到设定的最大迭代次数

2基础聚类算法划分方法（partitioningmethod）新闻文本聚类首先，新闻文本聚类可以发现与某文档相似的一批文档，帮助知识工作者发现相关知识；其次，文档聚类可以将一类文档聚类成若干个类，提供一种组织文档集合的方法；再次，文档聚类还可以生成分类器以对文档进行分类。聚类分析以相似性为基础，在一个聚类中的模式之间比不在同一聚类中的模式之间具有更多的相似性。2基础聚类算法社交网络聚类划分方法（partitioningmethod）1基础聚类算法层次聚类是一种很直观的算法，通俗理解就是要一层一层地进行聚类，可以从下而上地把小的簇合并聚集，也可以从上而下地将大的簇进行分裂，即包括凝聚型和分裂型层次聚类算法（agglomerative和divisive）。层次方法（hierarchicalmethod）（1）凝聚层次聚类：又叫自底向上方法，其策略是首先将每个对象作为一个簇，然后合并相邻近的簇为越来越大的簇，直到所有的对象都在一个簇中，或者某个终结条件被达到要求。（2）分裂层次聚类：又叫自顶向下方法，其策略与凝聚的层次聚类有些不一样，它首先将所有对象放在一个簇中，然后慢慢地细分为越来越小的簇，直到每个对象自行形成一簇，或者直达满足其他的一个终结条件，例如满足了某个期望的簇数目，又或者两个最近的簇之间的距离达到了某一个阈值。2基础聚类算法凝聚型层次聚类步骤层次方法（hierarchicalmethod）（1）将每个对象看作一个类，计算两两之间的最小距离；（2）repeat（3）将距离最小的两个类合并成一个新类（4）重新计算新类与所有类之间的距离（5）Until重复(3)(4)的过程，重复(2)、(3)，直到所有类最后合并成一类

2基础聚类算法凝聚型层次聚类层次方法（hierarchicalmethod）2基础聚类算法层次方法（hierarchicalmethod）如何判断两个簇(cluster)之间的距离呢？1.最小距离，单链接SingleLinkage两个簇的最近样本决定。2.最大距离，全链接CompleteLinkage两个簇的最远样本决定。3.平均距离，均链接AverageLinkage两个簇所有样本共同决定。方法1和2都容易受极端值的影响，而方法3计算量比较大。1基础聚类算法基于密度方法（density-basedmethod）层次聚类算法和划分式聚类算只能发现凸形的聚类簇，为了弥补这一缺陷，发现各种任意形状的聚类簇，开发出基于密度的聚类算法（Density-BasedMethods）。这类算法认为，在整个样本空间点中，各目标类簇是由一群的稠密样本点组成的，而这些稠密样本点被低密度区域（噪声）分割，而算法的目的就是要过滤低密度区域，发现稠密样本点。2基础聚类算法基于密度方法（density-basedmethod）算法原理：只要邻近区域里的密度（对象的数量）超过了某个阈值，就继续聚类。也即，给定某个簇中的每个数据点（数据对象），在一定范围内必须包含一定数量的其他对象。该算法从数据对象的分布密度出发，把密度足够大的区域连接在一起，因此可以发现任意形状的类。基于密度的方法中三种代表性的算法包括：DBSCANOPTICSDENCLUESTING（StatisticalInformationGrid）算法针对空间数据挖掘的算法，采用多分辨率的方式进行聚类，聚类的质量取决于最底层的粒度。WaveCluster是一个多分辨率的聚类方法，通过小波变换来转换原始的特征空间。其主要思想是，首先量化特征空间，把数据映射到一个多维网格中，然后对网格单元进行小波变换，通过搜索连通分支得到聚类。2基础聚类算法基于网格方法（grid-basedmethod）基于网格的聚类（grid-basedclustering）将对象空间量化为有限数目的单元，形成网格结构，每个单元中存储对象的统计参数，然后在这个量化空间（网格结构）上进行所有的聚类操作。基于网格方法的典型算法有STING算法、WaveCluster算法：2基础聚类算法聚类评估一个聚类算法的优劣可以从以下几个方面来衡量：可伸缩性：好的聚类算法可以处理包含大到几百万个对象的数据集；处理不同类型属性的能力：许多算法是针对基于区间的数值属性而设计的，但是有些应用需要针对其它数据类型（如符号类型、二值类型等）进行处理；发现任意形状的聚类：一个聚类可能是任意形状的，聚类算法不能局限于规则形状的聚类；输入参数的最小化：要求用户输入重要的参数不仅加重了用户的负担，也使聚类的质量难以控制；对输入顺序的不敏感：不能因为有不同的数据提交顺序而使聚类的结果不同；高维性：一个数据集可能包含若干维或属性，一个好的聚类算法不能仅局限于处理二维或三维数据，而需要在高维空间中发现有意义的聚类；基于约束的聚类：在实际应用中要考虑很多约束条件，设计能够满足特定约束条件且具有较好聚类质量的算法也是一项重要的任务；可解释性：聚类的结果应该是可理解的、可解释的，以及可用的。3基于聚类的异常检测基于聚类的异常检测技术通常可以分为两类：

（1）第一类于以下假设：正常数据对象属于数据集合中的簇，而异常点不属于任何簇。基于此假设的异常检测算法包括DBSCAN、ROCK和SNN算法。

（2）第二类基于聚类的异常检测假设正常数据对象靠近它们最接近的聚类中心，基于该假设的算法包括两个步骤：第一步，对于每个数据对象，将它分配到与其最接近的聚类中，而异常点远离它们最接近的聚类中心，使用聚类算法对数据进行聚类；第二步，把与中心的距离作为其异常得分。3基于聚类的异常检测基于K-means异常检测基本思路：通过K均值聚类算法不断地计算各样本点与簇中心之间的距离，直到收敛为止，然后通过构造自定义函数，计算簇内的每个点与簇中心的距离，并判断其是否超过阈值的异常点。基于K-means聚类的异常检测的假设是，如果我们对数据进行聚类，则正常数据将属于聚类，而异常将不属于任何聚类或属于小聚类。4高级聚类方法（1）基于概率模型的聚类1.模糊簇聚类模糊簇聚类方法使用模糊集工具，模糊集S是整体对象集X的一个子集，允许X中的每个对象都具有一个属于S的0到1之间的隶属度，模糊聚类也称为软聚类，允许一个对象属于多个簇，和传统的硬聚类强制每个对象互斥地仅属于一个簇不同。2.基于概率簇的聚类

从统计视角看，由聚类分析形成的簇使用样本数据集推断并且旨在逼近隐藏的类别，可以假定想要发现的隐藏类别是数据空间上的一个需要估计的分布，可以使用概率密度函数或分布函数来表示，这种隐藏的类别称为概率簇。对于一个概率簇C，它的密度函数和数据空间的点o，f(o)是C的一个实例在o上出现概率，假定概率簇符合某种类型的分布，通过观测到的样本数据集学习到分布参数进而识别潜在的类别4高级聚类方法（2）高维数据聚类

在现实生活中，数据的维度属性可以高达几十，几百甚至上万维。高维数据对传统的聚类算法提出了挑战，这是因为传统的距离度量，密度度量，相似性度量均需要针对高维数据的特点做出调整。高维数据聚类的难点在于：1.适用于普通数据集合的聚类算法，在高维数据集合中效率极低。2.由于高维空间的稀疏性以及最近邻特