数据挖掘（四）聚类

4、聚类
 聚类分析提供由个别数据对象到数据对象所指派到簇的抽象。此外，一些聚类技术使用簇原型（即代表簇中其他对象的数据对象）来刻画簇的特征。聚类分析是研究发现最具有代表性的簇原型的技术。回归和PCA的时间复杂度都是O(m2)。注意：簇的定义是不精确的，而最好的定义依赖于数据的特征和期望的结果。聚类分析与其他将数据对象分组的技术有关。监督学习（也叫监督分类或分类）：使用一个由类标号已知的对象开发的模型，对新的、无标记的对象赋予一个类标号。非监督学习（也叫非监督分类或聚类）。在数据挖掘中，不附加任何条件使用术语分类时，通常是指监督分类。尽管术语分割和划分有时也作聚类的同义词，但是这些术语通常用来表示传统的聚类分析之外的方法。
 
4.1 聚类类型
 不同的聚类类型：层次的（嵌套的）与划分的（非嵌套的），互斥的，重叠的与模糊的，完全的与部分的。划分聚类：简单地将数据对象划分成不重叠的子集（簇），使得每个数据对象恰在一个子集中。层次聚类：允许簇具有子簇，层次聚类是嵌套簇的集簇，组织成一棵树。层次聚类可以看作划分聚类的序列，划分聚类可以通过取序列的任意成员得到，即通过在一个特定层剪断层次树得到。互斥聚类：每个对象都指派到单个簇。重叠的或非互斥的聚类用来反映一个对象同时属于多个组（类）这一事实。模糊聚类：每个对象以一个0（绝对不属于）和1（绝对属于）之间的录属权值属于每个簇。完全聚类：将每一个（全部的对象）指派到一个簇，而部分聚类是有些对象没有被聚类。
 不同的簇类型：明显分离的：不同组中的任意两点之间的距离都大于组内任意两点之间的距离。明显分离的簇不必是球形的，可以具有任意形状。基于原型的：簇是对象的集合，其中每个对象到定义该簇的原型的距离比到其他簇的原型的距离更近（或更加相似）。对于具有连续属性的数据，簇的原型通常是质心，即簇中所有点的平均值。这种簇倾向于呈球状。基于原型的聚类技术创建数据对象的单层划分。基于图的：如果数据用图表示，其中节点是对象，而边代表对象之间的联系，则簇可以定义为连通分支，即互相连通但不与组外对象连通的对象组。当簇不规则或缠绕时，簇的这种定义是有用的。但是，当数据具有噪声时就可能出现问题。也存在其他类型的基于图的簇。一种方法是定义簇为团，即图中相互之间完全连接的节点的集合。基于密度的：簇是对象的稠密区域，被低密度的区域环绕。当簇不规则或互相盘绕，并且有噪声和离群点时，常常使用基于密度的簇定义。共同性质的（概念簇）：把簇定义为有某种共同性质的对象的集合。发现这样的簇的过程称作概念聚类。
 
4.2 K均值
 K均值是基于原型的、划分的聚类技术。它试图发现用户指定个数（K）的簇（由质心代表）。
 K均值聚类用于n维连续空间中的对象。K中心点使用中心点定义原型，其中中心点是一组点中最有代表性的点。K中心点聚类可以用于广泛的数据，因为它只需要对象之间的邻近性度量。尽管质心几乎从来不对应实际的数据点，但是根据定义，中心点必须是一个实际的数据点。K均值的算法步骤：首先选择K个初始质心，其中K是用户指定的参数，即所期望的簇的个数。每个点指派到最近的质心，而指派到一个质心的点集为一个簇。然后，根据指派到簇的点，更新每个簇的质心。重复指派和更新步骤，直到簇不发生变化，或等价的，直到质心不发生变化。算法流程如下：
 
<div style="text-align:center">
<img alt="" src="">
</div> 为了将点指派到最近的质心，我们需要邻近性度量来量化所考虑的数据的“最近”概念，通常，对欧式空间中的点使用欧几里得距离，对文档用余弦相似性。第四步“重新计算每个簇的质心”，因为质心可能随数据邻近性度量和聚类目标不同而改变。聚类的目标通常用一个目标函数表示，该函数依赖于点之间，或点到簇的质心的邻近性；如：最小化每个点到最近质心的距离的平方。然而，关键点是：一旦我们选定了邻近性度量和目标函数&#xf