数据挖掘 第七章 聚类算法总结.pdf

数据挖掘第七章聚类算法总结 本文总结了数据挖掘中常用的聚类算法，包括K-Means算法、PAM算法、CLARA算法、CLARANS算法、层次聚类算法、BIRCH算法和Chameleon算法等。这些算法的思想、优点、缺点和应用场景都进行了详细的解释。 一、K-Means算法 K-Means算法是一种常用的聚类算法。算法思想是指定cluster数目为k，然后随机划分数据到k个子集，计算每个子集的“中心”数据，并将每个数据所属类别调整到最近的“中心”所代表的cluster。该算法的优点是简单、实现简单，运行时间复杂度较低。但是，算法也存在一些不足之处，如易陷入局部最优解、中心计算时如何处理标称数据、需要预置k值，对噪声数据/孤立点敏感，非凸cluster的识别能力弱。 二、PAM算法 PAM算法是一种改进的K-Means算法。算法思想是随机选择k个种子为中心点，将数据点划归到最近中心点/种子代表的cluster。然后，对所有（种子，非种子）对，尝试交换它们，检查是否能提高聚类质量。该算法的优点是可以用一些启发式方法选择交换的种子和非种子，但是也存在一些不足之处，如易陷入局部最优。 三、CLARA算法和CLARANS算法 CLARA算法和CLARANS算法是针对大规模数据集的改进算法。CLARA算法对数据集中的数据进行采样，在采样得到的子集上寻找中心点，执行PAM算法。CLARANS算法执行PAM算法，但是没有搜索所有可能的实施交换的对，仅仅执行L次（种子，非种子）对的交换。 四、层次聚类算法 层次聚类算法是一种常用的聚类算法。该算法的思想是将数据集分层，形成一棵树状图（Dendrogram）。AGNES算法和DIANA算法是两种常用的层次聚类算法。AGNES算法是自底向上，找两个簇，它们中最相似两个数据的距离最小，则合并这两个簇。DIANA算法是自顶向下，找一个簇，簇中最近两个数据的距离在所有簇中最大，分裂该簇。 五、BIRCH算法 BIRCH算法是一种针对大规模数据集的改进算法。该算法的思想是利用统计信息表示一个簇，避免存储簇中所有数据。算法步骤是扫描数据集，逐步构建一棵包括了簇统计信息/特征的树（聚类特征向量CF，包含聚类的特征，计算简单），非叶结点是统计信息；一个叶节点是一个簇，不同的数据归入不同簇若某个簇的数据太多，距离太大，考虑分裂该簇（及其父节点）。该算法的优点是时间复杂度O(n)，只需要装入一次数据集，适用于大型数据集。 六、Chameleon算法 Chameleon算法是一种使用动态建模的多阶段层次聚类算法。该算法的核心思想是两个cluster之间连边很多，且距离近，则合并之。算法步骤是从数据集开始，每个数据视为n-D空间中的一个点；计算每个点的k个最近邻（构建KNN图），然后连接，并且每个连边都对应一个cluster。