算法概论（聚类）

聚类分析基础

概述

概念

聚类是将数据对象的集合分成相似的对象类的过程。使得同一个簇（或类）中的对象之间具有较高的相似性，而不同簇中的对象具有较高的相异性。 #### 表示形式 聚类分析(clustering analysis)就是根据某种相似性度量标准，将一个没有类别标号的数据集S直接拆分成若干个子集Ci (i=1,2, …,k; m≤n)，并使每个子集内部数据对象之间相似度很高，而不同子集的对象之间不相似或相似度很低。 每个子集Ci称为一个簇，所有簇构成的集合C={C1 ,C2, …,Ck}称为数据集S的一个聚类。 ### 数学定义 称C为S由s(X,Y)生成的一个划分聚类(partitional clustering)，简称C为S的划分聚类，或称为互斥(exclusive)的聚类。

簇的形状

类球状的簇

一般是聚类算法使用距离函数所产生的簇 #### 非球状的簇 非球状的簇，通常由基于密度或基于原型的聚类算法获得的簇。

簇间关系

明显分离的簇

簇中每个数据对象到同簇中其它对象的 距离，比到不同簇中任意对象的距离更近; 显分离的簇不必是球形的，也可以是其它任意的形状。 #### 基于原型的簇 所谓原型其实就是簇中最具代表性的点。对连续属性的数据，簇的原型通常就是质心，即簇中所有点的平均值。 当数据包括分类属性时，簇的原型通常是中心点，即簇中最有代表性的点。 对于许多数据类型，原型可以视为最 靠近中心的点，因此，通常把基于原型的 簇看作基于中心的簇(center-based cluster), 右图就是一个基于中心的簇的例子。 #### 基于连片的簇(contiguity-based cluster) 簇中两个相邻对象的距离都在指定 的阈值之内即将其归为同一个簇。 当簇的形状不规则或缠绕，且数据 集没有噪声时，用这种方式来定义簇会 收到很好的聚类效果。如果存在噪声，其聚类效果就不一定理想。图中的哑铃状簇，就是由线状 (噪声)连接两个球状簇形成的一个簇。 #### 基于密度的簇(density-based cluster) 基于密度的簇由对象间相对稠密的区域组成，且其周围是低密度的区域。一般通过指定簇中任何一个对象周围区域内最少点数(即密度)来实现。 #### 基于概念的簇 即具有某种“共同性质”的数 据对象集合。比如，离相同的质 心或中心点最近，或组成三角形、 梯形，或圆环状(重叠聚类)等。 ### 簇的距离 数据集S的一个聚类C={C1,C2,…,Ck}的质量，包括每个簇Ci的质量和C的总体质量。前者用簇内距离来刻画，后者用簇间距离来衡量。 #### 簇内距离 #### 簇间距离

相似性测度公式

距离相似性度量

通常相似度与距离成反比，在确定好距离函数后，可设计相似度函数如下： ### 密度相似性度量 ### 连通性相似性度量 数据集用图表示，图中结点是对象，而边代表对象之间的联系，这种情况下可以使用连通性相似性，将簇定义为图的连通分支，即图中互相连通但不与组外对象连通的对象组。 　　也就是说，在同一连通分支中的对象之间的相似性度量大于不同连通分支之间对象的相似性度量。 ### 概念相似性度量 若聚类方法是基于对象具有的概念，则需要采用概念相似性度量，共同性质（比如最近邻）越多的对象越相似。簇定义为有某种共同性质的对象的集合。 ## k-means ### 算法描述 k-means算法也称k-平均算法，它采用距离作为相异度的评价指标，以簇内差异函数w(C)作为聚类质量的优化目标函数，即将所有数据对象到它的簇中心点的距离平方和作为目标函数，算法寻找最优聚类的策略是使目标函数达到最小值(簇中心不变化等价于w(C)达最小)。 ### 算法的优缺点 #### 算法的优点 * k-平均算法简单、经典，常作为其它聚类算法的参照或被改进。 * k-平均算法以k个簇的误差平方和最小为目标，当聚类的每个簇是密集的，且簇与簇之间区别明显时，其聚类效果较好。 * k-平均算法处理大数据集高效，且具较好的可伸缩性，其计算复杂性为O(nkt)，n是数据对象个数，k为簇个数，t是迭代次数。 (2) 算法的缺点 * k-平均算法对初始中心点的选择比较敏感。对同一个数据集，如果初始中心选择不同，其聚类结果也可能不一样。 * k-平均算法对参数k是比较敏感的，即使是同一个数据集，如果k选择不同，其聚类结果可能完全不一样。 * k-平均算法以簇内对象的平均值作为簇中心来计算簇内误差，在连续属性的数据集上很容易实现，但在具有离散属性的数据集上却不能适用。

离群点(Outlier-异常点-噪音)

离群点的产生

数据来源于欺诈、入侵、疾病爆发、不寻常的实验结果等引起的异常。

比如，某人话费平均200元左右，某月突然增加到数千元；某人的信用卡通常每月消费5000元左右，而某个月消费超过3万等。 这类离群点在数据挖掘中通常都是相对有趣的，应用的重点之一。 #### 数据变量固有变化引起，反映了数据分布的自然特征 如气候变化、顾客新的购买模式、基因突变等。也是有趣的重点领域之一。 #### 数据测量和收集误差，主要是由于人为错误、测量设备故障或存在噪音。 例如，一个学生某门课程的成绩为100，可能是由于程序设置默认值引起的；一个公司的高层管理人员的工资明显高于普通员工的工资看上去像是一个离群点，但却是合理的数据。 ### 离群点挖掘问题 #### 定义离群点 由于离群点与实际问题密切相关，明确定义什么样的数据是离群点或异常数据，是离群点挖掘的前提和首要任务，一般需要结合领域专家的经验知识，才能对离群点给出恰当的描述或定义。 #### 挖掘离群点 离群点被明确定义之后，用什么算法有效地识别或挖掘出所定义的离群点则是离群点挖掘的关键任务。离群点挖掘算法通常从数据能够体现的规律角度为用户提供可疑的离群点数据，以便引起用户的注意。 #### 理解离群点 对挖掘结果的合理解释、理解并指导实际应用是离群点挖掘的目标。由于离群点产生的机制是不确定的，离群点挖掘算法检测出来的“离群点”是否真正对应实际的异常行为，不可能由离群点挖掘算法来说明和解释，而只能由行业或领域专家来理解和解释说明。

离群点的相对性

全局或局部的离群点

一个数据对象相对于它的局部近邻对象可能是离群的，但相对于整个数据集却不是离群的。如身高1.9米的同学在我校数学专业1班就是一个离群点，但在包括姚明等职业球员在内的全国人民中就不是了。 #### 离群点的数量 离群点的数量虽是未知的，但正常点的数量应该远远超过离群点的数量，即离群点的数量在大数据集中所占的比例应该是较低的，一般认为离群点数应该低于5%甚至低于1%。 #### 点的离群因子 不能用“是”与“否”来报告对象是否为离群点，而应以对象的偏离程度，即离群因子(Outlier Factor)或离群值得分(Outlier Score)来刻画一个数据偏离群体的程度，然后将离群因子高于某个阈值的对象过滤出来，提供给决策者或领域专家理解和解释，并在实际工作中应用。

判断离群点的方法

基于距离的方法

基于相对密度的方法

聚类算法的评价

一个好的聚类算法产生高质量的簇，即高的簇内相似度和低的簇间相似度。 ### 内部质量评价准则 ### 外部质量评价准则