1.3.3　聚类分析

聚类分析是将一个数据集依据某种规则分成若干子集的过程，这些子集由相似元素构成。聚类分析是一种典型的无监督学习方法，它在进行分类与预测时无须事先学习数据集的特征，具有更优的智能性。聚类分析在Web资源开发与利用中发挥着重要作用。

当前主流的聚类算法包括以下几类：层次聚类算法、划分聚类算法、基于密度和网格的聚类算法及其他聚类算法。

层次聚类算法利用数据的连接规则，通过层次架构的方式反复将数据分裂或聚合，以便形成一个层次序列的聚类问题的解。典型代表有：Gelbard等人提出的正二进制（Binary-positive）方法[72]，该方法将待聚类数据存储在由0和1组成的二维矩阵中，其中，行表示记录，列表示属性值，1和0分别表示记录是否存在对应的属性值；Kumar等人提出的基于不可分辨粗聚合的层次聚类算法（Rough Clustering of Sequential Data，RCOSD）[73]，该算法适用于挖掘连续数据的特征，可以帮助人们有效地描述潜在Web用户组的特征。此外，基于Quartet树的快速聚类算法[74]及Hungarian聚类算法[75]也具有一定的代表性。层次聚类算法的最大优势在于无须事先给定聚类数量，可以灵活地控制聚类粒度，准确表达聚类簇间关系；主要的不足在于其无法回溯处理已形成的聚类簇。

划分聚类算法需要事先给出聚类数量或聚类中心，为了确保目标函数最优，不断迭代，直至目标函数值收敛时，可得聚类结果。典型代表有：MacQueen提出的K-means算法[76]，该算法试图找到若干个聚类中心，通过最小化每个数据点与其聚类中心之间的距离之和来构建最优化问题；为了提高K-means算法的普适性，Huang提出了面向分类属性数据的K-modes聚类算法[77]；Chaturvedi等人提出面向分类属性数据的非参数聚类方法K-modes-CGC[78]；Sun等人在K-modes算法的基础上提出迭代初始点集求精K-modes算法[79]；Ding等人将统计模式识别中的重要概念——最近邻一致性应用到聚类分析中，提出一致性保留K-means算法[80]；Ruspini将模糊集理论与聚类分析有机结合起来，提出模糊聚类算法（Fuzzy C-means，FCM）。划分聚类算法的优点在于收敛速度快，缺点是需要事先指定聚类数量。

基于密度的聚类算法利用数据密度发现类簇，基于网格的聚类算法通过构造一个网格结构实现模式聚类。上述两类算法适用于空间信息处理，常合并在一起使用。典型代表有：Zhao等人提出的网格密度等值线聚类算法（Grid-based Density Isoline Clustering）[81]；Ma提出的基于移位网格的非参数型聚类算法（Shifting Grid Clustering，SGC）[82]；Pileva等人提出的面向高维数据的网格聚类算法[83]；Micro等人提出的基于密度的自适应聚类方法[84]，该方法适用于移动对象轨迹数据处理。该类方法对处理形状复杂的簇具有明显的优势。其他一些常见的聚类算法有：Tsai等人提出的一种新颖的具有不同偏好的蚁群系统[85]，该系统用以解决数据聚类问题；基于最大θ距离子树的聚类算法、GBR（Graph-based Relaxed Clustering）算法，以及基于dominant集的点对聚类算法。