聚类算法学习笔记.doc

聚类的定义聚类是一个将数据集划分为若干个子集的过程,并使得同一集合内的数据对象具有较高的相似度,而不同集合中的数据对象则是不相同的,相似或不相似的度量是基于数据对象描述属性的聚类值来确定的,通常就是利用各个聚类间的距离来进行描述的。聚类分析的基本指导思想是最大程度地实现类中对象相似度最大,类间对象相似度最小。聚类与分类不同,在分类模型中,存在样本数据,这些数据的类标号是已知的,分类的目的是从训练样本集中提取出分类的规则,用于对其他标号未知的对象进行类标识。在聚类中,预先不知道目标数据的有关类的信息,需要以某种度量为标准将所有的数据对象划分到各个簇中。因此,聚类分析又称为无监督的学习。聚类主要包括以下几个过程:(1)数据准备:包括特征标准化和降维。(2)特征选择、提出:从最初的特征中选择是有效的特征,并将其存储于向量中。(3)特征提取:通过对所选择的特征进行转换,形成新的突出特征。(4)聚类(或分组):首先选择合适特征类型的某种距离函数(或构造新的距离函数)进行接近程度的度量,然后执行聚类或分组。聚类结果评估:指对聚类结果进行评估。评估主要有3种:外部有效性评估、内部有效性评估和相关性测试评估。聚类算法的要求(1)可扩展性。许多聚类算法在小数据集(少于200个数据对象)时可以工作很好;但一个大数据库可能会包含数以百万的对象。利用采样方法进行聚类分析可能得到一个有偏差的结果,这时就需要可扩展的聚类分析算法。(2)处理不同类型属性的能力。许多算法是针对基于区间的数值属性而设计的。但是有些应用需要对实类型数据。如:二值类型、符号类型、顺序类型,或这些数据类型的组合。(3)发现任意形状的聚类。许多聚类算法是根据欧氏距离和Manhattan距离来进行聚类的。基于这类距离的聚类方法一般只能发现具有类似大小和密度的圆形或球状聚类。而实际一个聚类是可以具有任意形状的,因此设计能够发现任意开关类集的聚类算法是非常重要的。(4)需要(由用户)决定的输入参数最少。许多聚类算法需要用户输入聚类分析中所需要的一些参数(如:期望所获得聚类的个数)。而聚类结果通常都与输入参数密切相关;而这些参数常常也很难决定,特别是包含高维对象的数据集。这不仅构成了用户的负担,也使得聚类质量难以控制。(5)处理噪声数据的能力。大多数现实世界的数据库均包含异常数据、不明数据、数据丢失和噪声数据,有些聚类算法对这样的数据非常敏感并会导致获得质量较差的数据。(6)对输入记录顺序不敏感。一些聚类算法对输入数据的顺序敏感,也就是不同的数据输入顺序会导致获得非常不同的结果。因此设计对输入数据顺序不敏感的聚类算法也是非常重要的。(7)高维问题。一个数据库或一个数据仓库或许包含若干维属性。许多聚类算法在处理低维数据时(仅包含二到三个维)时表现很好,然而设计对高维空间中的数据对象,特别是对高维空间稀疏和怪异分布的的数据对象,能进行较好聚类分析的聚类算法已成为聚类研究中的一项挑战。(8)基于约束的聚类。现实世界中的应用可能需要在各种约束之下进行聚类分析。假设需要在一个城市中确定一些新加油站的位置,就需要考虑诸如:城市中的河流、调整路,以及每个区域的客户需求等约束情况下居民住地的聚类分析。设计能够发现满足特定约束条件且具有较好聚类质量的聚类算法也是一个重要聚类研究任务。(9)可解释性和可用性。用户往往希望聚类结果是可理