聚类分析方法

已有的聚类算法多数是为模式识别而设计的，它将目标用其特征来表示，一个目标表达为多维特征空间的一个点，在特征空间中聚类。空间数据库中的聚类是对目标的图形直接聚类。空间目标有点状、线状、面状等多种类型，有时聚类形状复杂，同时数据量庞大，要求算法有较高效率，能够处理任意形状的聚类，并适用于点状、线状、面状等多种目标类型，算法需要的参数能自动确定或用户容易确定。
聚类算法主要分为划分方法（Partitioning Methods）、分层方法（Hierarchical Algorithm）、基于密度的方法、基于表格的方法、基于模型（Model-Based）的聚类方法。划分方法将一个包含n个数据对象的数据库组织成k个划分（k<=n），其中每个划分代表一个簇（Cluster）。K-平均算法随机的把所有对象分配到k个非空的簇中；计算每个簇的平均值，并用该平均值代表相应的簇；将每个对象根据其与各个簇中心的距离，重新分配到它最近的簇中；这一过程迭代下去，直到不再有新的分配发生。K-平均算法的优点是算法相对高效，通常终止于局部最优解；但是只有当平均值有意义的情况下才能使用，对于类别字段不适用，必须事先给定要生成的簇的个数，对“噪声”和异常数据敏感，不能发现非凸形状的数据。PAM（Partitioning Around Medoids，Kaufman & Rousseeuw，1987）算法设定一个中心点的初始集合，然后反复的用非中心点对象来替代中心点对象，以改进聚类的质量。PAM算法在大数据集上效率较低，没有良好的可伸缩性。CLARA（Clustering Large Application，Kaufman & Rousseeuw，1990）算法首先获得数据集的多个采样，然后在每个采样上使用PAM算法，最后返回最好的聚类结果作为输出，其优点是能够处理大数据集，但是效率依赖于采样的大小，如果样本发生偏斜，基于样本的一个好的聚类不一定代表整个数据集合的一个好的聚类。CLARANS（A Clustering Algorithm based on Randomized Search，Ng & Han，1994）算法在搜索的每一步动态的抽取一个样本，聚类过程可以被描述为对一个图的搜索，图中的每个节点是一个潜在的解，即k个中心点的集合；在替换了一个中心点后的结果被称为当前结果的邻居，如果找到了一个局部最优，算法从随即选择的节点开始寻找新的局部最优。
层次算法采用距离作为衡量聚类的标准。该方法不需要指定聚类的个数，但用户可以指定希望得到的簇的数目作为一个结束条件。BIRCH（Balanced Iterative Reducing and Clustering Using Hierarchies）算法首先扫描数据库，建立一个初始存放于内存的CF树，它可以被看作数据的多层压缩，试图保留数据内在的聚类结构，然后采样某个聚类算法对CF树的叶子节点进行聚类。
DBSCAN是一种基于密度的聚类算法，其基本思想是认为在一类中的任一点一定半径的范围内有足够的相邻点，即邻域密度超过某一阈值。该算法需要两个参数：邻域半径Eps和邻域内点数阈值MinPts，参数Eps采用启发式方法交互地确定，在二维数据的试验中将MinPts设为4。算法采用R*-tree方法检索相邻点，对全部数据只需搜索一次即可得到最终结果，因而速度很快。同时它能处理任意形状的聚类，根据阈值MinPts还可以去除噪声；是一种较好的空间数据库聚类算法。然而，在实际的空间数据库中，并不总是存在R*-tree索引结构，R*-tree的构建是十分耗时的，若将该算法用于没有索引结构的空间数据库中，其效率就会大大降低。
通过上面的分析，多数聚类算法不能处理非凸的、复杂的聚类形状，速度较慢，且只能处理点状目标，因此应用于大型空间数据库时受到限制。DBSCAN算法也只能处理点状目标，同时要求具有R*-tree索引结构。