数据挖掘——传统聚类算法基础知识笔记

聚类分析是数据挖掘应用的技术之一，可以看作一种数据分析方法，也可以作为数据挖掘技术的预处理。聚类算法属于无监督学习的范畴，不需要人为事先确定好聚类的类别，所以常常被用来对未知类别的数据（如电力日负荷曲线）进行划分。聚类算法通过一定的计算，把数据集划分为不同的簇，旨在使同一簇内的数据相似性最高，簇与簇之间差距最大。

1.聚类算法的分类

常见的聚类算法可分为以下几类：
(1) 划分法：即通过不断地迭代，使具有相似特征的数据划分为一类，具有不同特征的数据划分为另一类，直至满足迭代终止条件，划分结束。每个分组内都有对象，且每个对象只能在一个分组内。
(2) 层次法：将数据集内的对象分解或合并，最终形成的结构具有层次结构的树。其过程是将所有的数据放在一个簇里，通过某种策略将这个簇分成越来越小的分组，使同一分组内的数据离散度越来越小，直到分组满足终止条件或称为一个单独的簇。
(3) 基于密度的聚类：基于密度方法的聚类分析认为最终形成的聚类结果是由一个聚集在一起的样本点组成，这些数据对象分布紧凑，称之为高密度区，处于这些簇间隙的数据对象分布相对零散，称之为低密度区。算法旨在将数据分布分散的区域与数据分布集中的区域分散开，从而找到聚类目标。
(4) 基于网格方法的聚类：将数据集分成若干个数据单元，以数据单元为最小单位进行聚类。此方法只需关心网格数，不需要关心数据集内对象本身。
(5) 基于模型的方法聚类：与数学模型结合，为每个聚类目标寻找一个合适的数学模型，通过数学模型，将数据聚类。数学模型一般选择基于概率密度分布的函数或者选择体现相关性的函数。

2.聚类相似性计算

数据在存储时，会有各种不同的存储形式，在聚类分析时需要通过某种方法来表示数据结构，以便于对数据进行处理。常见的表示方法就是矩阵，如:数据集内共有n个对象，每个对象具有m个数字属性，则可用n×m的矩阵来表示。

聚类结果依赖于相似度的度量方式，常用的相似度度量有两类：
(1) 使用距离公式度量
1)欧几里得公式（欧式距离）

2)曼哈顿公式

3)马氏距离

(2)使用相似性系数度量
1)夹角余弦

2)Jacard系数
Jacard系数通常用来表示集合与集合之间的相似性，公式如下，Ti表示一个集合。

3.经典聚类方法

目前为止，没有一种方法能够解决所有的聚类问题，因此，了解不同问题的数据特点，选择不同的聚类算法事关重要。几种常用的经典聚类算法如下：
(1) k-means(k均值聚类) 算法
k-means算法的基本思想是从数据集中随机选取k个数据，作为初始聚类中心，然后根据相似性度量方式计算其他数据对象与初始聚类中心的距离或者其他相似性的度量，然后将其他对象分配到与初始聚类中心最相近的一个分组里。所有数据分配完成后，重新计算每个分组的聚类中心（即该分组中所有数据对象的均值），再进行下一轮迭代，直到满足某种终止条件，聚类结束。
k-means实现简单，算法运算速度快，适合大量数据分类，需要事先给定需要划分的类别数k，类别数k会影响最后的结果。
(2)DBSCAN(Density-Based Spatial Clustering of Applications with Noise)算法
DBSCAN算法作为一种典型的基于密度的聚类算法，其基本思想是，首先对整个数据集进行扫描，找到任意一个核心点。所谓核心点就是在该数据对象的领域内，包含的样本点的个数大于或者等于一个给定的下限值。从该核心点出发，找到与该核心点密度相连的所有数据点，然后用这些数据点对核心点进行扩充。通过遍历核心点领域内的所有核心点，找到所有与核心点密度相连的点，直到不能再扩充为止。在对所有的数据对象进行扫描后，再次进行扫面，找到那些没有被聚类的核心点，重复执行上面的工作，直到所有核心点都被归类后结束。在达到聚类终止条件后，独立存在的没被聚类成簇的数据就是噪声数据。
通过以上过程，可以看出DBSCAN算法可以去除明显的噪声数据。

4.小结

简单介绍了数据挖掘中聚类分析的基本概念和常用聚类算法的分类、算法思想。
声明：以上内容为在学习过程中的记录，非原创。