一種改進的距離度量的聚類算法

李健森，白萬民

（西安工業大學 陜西 西安 710000）

K均值聚類算法作為快速聚類法[1]（又稱動態聚類法）中最常用的一種，由于在計算速度上具有無可比擬的優勢，常被作為大樣本聚類分析的首選方案。其基本原理為:人為地或按照某種標準選擇初始凝聚點；依據樣品點到各初始凝聚點的歐氏距離，將樣品劃分到與其距離最近的類中，形成初始分類；再對初始分類進行修正，直到分類比較合理，不必再修正為止。而實際應用中度量分類對象的接近和相似程度并不一樣，文中定義了一種新的聚類算法的距離度量用作分類的數量指標，從而可以定量地進行分類，應用新的距離度量之后，數據點的權重不再只為1或0，而是由系數來確定，這就將硬劃分轉化為軟劃分，提高了算法的執行效率。

1 問題提出

為了度量分類對象之間的接近與相似程度，需要定義一些分類統計量，用作分類的數量指標，從而可以定量地進行分類。常用的分類統計量有距離和相似系數，它們的定義與聚類分析的類型有關。

距離是聚類分析中常用的分類統計量。要對數據對象進行聚類，一般要計算各個數據對象之間的距離（相異度）。聚類分析中距離測度的選擇一般有歐氏距離、馬氏距離、絕對距離等等。但最常用的距離度量方法是歐幾里得距離，其定義如下：

設兩個P維向量x分別表示兩個對象，它們的歐氏距離[2]為：

傳統的K均值聚類分析，不考慮對象中每個變量在聚類過程中體現作用的不同，而是統一看待，用這樣計算的距離來表示兩個對象的相似度并不確切。對象間的距離[3]表示的是對象的相近程度，而相似不僅依賴于對象間的相近程度，還依賴于對象內在的性質，即對象中每個變量的重要性是不同的。

2 解決方法

新的度量空間

其中β是一個正的常數，從這個距離函數[4]可以發現，d（x，y）是一個關于‖x-y‖的單調遞增函數，即 d（x，y）會隨著的增大而增大。下面證明d（x，y）是一個度量，即證明該度量是否滿足度量的3個條件[5]：

1）d（x，y）＞0，?x≠y，d（x，x）=0

2）d（x，y）=d（y，x）

3）d（x，y）≤d（x，z）+d（z，y）

證明：

1）因為β是一個正的常數，而‖x-y‖為一個正數，從而1-exp（-β‖x-y‖2）＞0，故 d（x，y）＞0

2） 因為 1-exp（-β‖x-y‖2）=1-exp（-β‖y-x‖2），故d（x，y）=d（y，x）

故 d（x，y）≤d（x，z）+d（z，y），因此 d（x，y）為一個度量

眾所周知，若要使得一個點的權重更具魯棒性[6]，則需滿足異常點或噪聲點的權重較小，而數據集中的緊實點的權重則應較大。這個新度量恰恰可以滿足這個要求。

應用新的距離度量得到改進的K-means算法的目標函數。

應用新的距離度量得到改進的K-means算法的中心更新公式

新的中心更新公式與經典的聚類分析算法中心更新公式的區別在于權重[7]，對于傳統的K-means均值算法，每個數據點的權重或為0或為1，故傳統的K-means均值算法也稱為硬K-means算法（Hard K-Means）。應用新的距離度量之后，數據點的權重不再只為1或0，而是由系數 exp（-β‖xj-wj‖2）來確定，這就將硬劃分轉化為軟劃分。軟劃分[8]是改進聚類算法的一種強有效的方法。

3 算法實現

輸入:初始簇k和推薦池T

輸出:推薦池的中心集合CenterSet

1）k=「k/2]；//起始時取「k/2]值作為 K-means 算法的初始k值

2）將評分項為0的各項以某一均值（或者設定的值）θ代替；//避免出現大規模稀疏矩陣[9]而影響推薦質量

CenterSet=k-means（T，k，CenterSet）；//進行聚類操作得到k個中心，找到一個新中心

4 算法流程圖

圖1 算法流程圖Fig.1 Schematic diagram of the algorithm

5 實驗測試

我們實現了K均值算法和改進的算法，并通過實驗對兩個算法進行了對比，實驗環境采用c/s結構，服務器計算機cpu為酷睿i5，內存為4 G，數據庫為SQL Server2008，實現的編程語言為Java，選用Myeclipse作為集成開發環境。

實驗選取了一個真實的超市交易數據庫的一部分數據，對不同數目的數據分別執行2種算法，得到執行時間結果如圖2所示。

其中橫坐標為實驗數據條目數，縱坐標為執行時間。

從圖2中可以看出，改進的算法大大加快了算法的收斂速度，因此明顯縮短了算法的執行時間。

6 結 論

圖2 測試結果圖Fig.2 Results chart of the test system

文中在傳統的K均值算法的基礎上改進了距離算法，提出了一種新的距離度量代替歐式距離，避免了傳統K均值算法各個數據點的權重只能為0或為1的缺陷，應用新的距離度量之后，數據點的權重不再只為1或0，而是由系數來確定，這就將硬劃分轉化為軟劃分，提高了算法執行效率，從而能更好地在實際應用中進行聚類分析，最后通過實驗驗證了應用新的距離度量比傳統K均值算法在算法上效率確實有了一定的提高。

[1]趙立平.電了商務概論[M].上海:復旦大學出版社，2000.

[2]朱明.數據挖掘[M].北京：中國科學技術大學出版社，2002.

[3]夏惠芬，董衛民.基于關聯規則的Web挖掘技術研究[J].現代電子技術，2011（16）:101-102.

XIA Hui-fen，DONG Wei-min.Based on association rules Web mining technology[J].Modern Electronic Technology，2011（16）:101-102.

[4]喬智勇，劉志鏡.Web數據挖掘系統的設計及實現研究[J].計算機工程與設計，2002（7）:86-88.

QIAO Zhi-yong，LIU Zhi-jing.Web data mining system design and implementation of research[J].Computer Engineering and Design，2002（7）:86-88.

[5]高陽.中國數據挖掘研究進展[J].南京大學學報：自然科學版，2011（4）:155-158.

GAO Yang.Chinese data mining research progress[J].Journal of Nanjing University：Natural Science，2011（4）:155-158.

[6]丁金龍.基于Web數據挖掘技術下的個性化信息服務[J].現代情報，2010（3）:122-123.

DING Jin-long.Based on Web data mining technology，personalized information services[J].Modern Information，2010（3）:122-123.

[7]Martin Gaedke，Klaus Turowski.Integrating Web-based ecommerce applications with business application systems[J].Netnomics，2000:98-100.

[8]Schafer J B，Konstan J A，Riedl J.E-Commerce recommendation applications[J].Data Mining and Knowledge Discovery，2001:32-35.

[9]Ordonez C，Ezquerra N，Santana C A.Constraining and summarizing association rules in medical data[J].Knowledge and Information Systems，2005:76-78.