聚類分析是數據挖掘領域中一種非常有用的技術，它用于從大量數據中尋找隱含的數據分布模式，主要有分割法、層次法、密度法、網格法和模型法等。該文主要討論數據挖掘中一種基于密度和網格的聚類分析算法及其在客戶關系管理中的應用。該算法具有較高的聚類效率而且容易實現，可以發現任意形狀的聚類，時間復雜度低，聚類精度高，適用于數據的批量更新。該文還提出增量式聚類技術，它不僅能夠利用前期聚類的結果，充分提高聚類分析的效率，而且可以降低維護知識庫所帶來的巨大開銷。實驗證明了算法的有效性。
關 鍵 詞 聚類分析; 客戶關系管理; 數據挖掘; 密度; 網格

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，當某單元格中點的個數大于該閾值時，就稱該單元格是密集的，聚類也就是所有相鄰近的密集單元格的集合。