聚类算法学习笔记.docx

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