邱 洋

（上海电子信息职业技术学院计算机应用系 201411）

1 引言

聚类分析也称群分析或者点群分析，是研究多要素事物分类问题的数量方法。与数据挖掘中的分类不同，它是在预先不知道目标数据库具体分类的情况下，希望将所有的纪录组成不同的类，并实现以某种度量为标准的相似性在同类间最小化，而在不同类间最大化。

优秀的聚类分析方法要求良好的伸缩性，能处理不同字段类型、异常数据和高维数据。能发现任意形状的聚类，同时应满足输入参数对领域知识的弱依赖性、结果对输入记录顺序的无关性、结果可解释性和可用性好，等等。这些都是传统的单一聚类手段所不能达到的。

2 基于网格和密度的聚类算法

2.1 聚类基于的数据类型

聚类算法通常是基于如图1的“数据矩阵(data matrix，或称为对象与变量结构)”和“相异度矩阵（dissimilarity matrix，或称为对象－对象结构）”这两种具有代表性的数据结构。如果数据以数据矩阵的形式出现，那么在聚类之前通常要将它转换为相异度矩阵。

图1 数据矩阵和相异度矩阵的表示形式

相异度矩阵把对象间的相似度量化为距离函数d(i,j)。通常的计算公式有：欧几里得距离、曼哈顿距离。它们具有一些共性：d(i,j)≥ 0，d(i,i)= 0，d(i,j)=d(j,i)，d(i,j)≤ d(i,h)+d(h,j)。而明氏距离则是两者的通式：

其中，i=(xi1,xi2…,xip)和 j=(xj1,xj2…,xjp)是两个 p维的数据对象，q是一个正整数。当q＝1时为曼哈顿距离；q＝2时为欧氏距离。并且为不同的变量赋予不同的权重。在实际计算距离时，只能凭主观确定各个变量的权重，不同的权重对计算结果影响较大。……