网格和密度的聚类算法在CRM中的应用

聚类分析是数据挖掘领域中一种非常有用的技术，它用于从大量数据中寻找隐含的数据分布模式，主要有分割法、层次法、密度法、网格法和模型法等。该文主要讨论数据挖掘中一种基于密度和网格的聚类分析算法及其在客户关系管理中的应用。该算法具有较高的聚类效率而且容易实现，可以发现任意形状的聚类，时间复杂度低，聚类精度高，适用于数据的批量更新。该文还提出增量式聚类技术，它不仅能够利用前期聚类的结果，充分提高聚类分析的效率，而且可以降低维护知识库所带来的巨大开销。实验证明了算法的有效性。
关 键 词 聚类分析; 客户关系管理; 数据挖掘; 密度; 网格

Clustering analysis is a very useful tool in the domain of data mining for searching distributing mode from a great deal of data. Its main algorithms are partition-based algorithm, hierarchy-based algorithm, density-based algorithm, grid-based algorithm, and model-based algorithm. The paper mainly discusses a clustering algorithm based on density and grid in data mining, which has high clustering efficiency and low time complexity. It is efficient and effective for multi-density and uniformity density data sets with noise and suitable for batch update. After that an incremental clustering technique is presented. This technique not only makes best use of the former clustering results and improves the efficiency of clustering analysis, but also brings to the reduction of enormous expenditure on knowledge base maintenance. At last an application of the algorithm in Customer Relationship Management (CRM) is gien.
Key words clustering analysis; customer relationship management; data mining; density; grid

聚类分析是数据挖掘领域研究的重要课题[1]，其基本思想是：按照数据的相似性和差异性，将数据划分为若干组，同组的数据尽量相似，不同组的数据尽量相异[2-3]。迄今为止，人们已经提出了许多聚类算法，主要有分割法、层次法、密度法、网格法和模型法等[4-6]。基于网格和密度的聚类算法由于易于增量实现和高维数据挖掘而被广泛地应用于聚类算法中。基于网格的方法在聚类过程中将网格中的点作为一个整体处理，而不是考虑单元中的每一个点，基于这一特性，该方法在所有的聚类方法中效率最高。其优点是聚类的结果与输入数据的顺序无关，算法的时间复杂度是数据点个数的线性函数，速度快、可扩展性好，能识别不同形状的聚类。
本文给出一种基于密度和网格的聚类算法，它是一个基于密度的算法，既保留了基于网格算法运行速度快的特点，又通过细化技术弥补了该类算法精度不好的弱点。
1 算法分析
在基于密度的算法中，一个聚类就是一个比周围区域有更高数据点密度的区域[7]。为识别数据点的密度，将数据空间进行划分并找出每个单元中数据点的数目。为使计算点的密度的方法简单一些，将数据空间分割成网格状，把数据空间中的每一维划分成相同的区间数，每一个单元具有相同的“体积”[8-9]。单元中点的密度的计算可以转换成简单的点计数，然后把落到某个单元中的点的个数作为该单元的密度。这时可以指定一个阈值r，当某单元格中点的个数大于该阈值时，就称该单元格是密集的，聚类也就是所有相邻近的密集单元格的集合。