一種改進(jìn)的距離度量的聚類算法

李健森，白萬(wàn)民

（西安工業(yè)大學(xué) 陜西 西安 710000）

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

1 問(wèn)題提出

為了度量分類對(duì)象之間的接近與相似程度，需要定義一些分類統(tǒng)計(jì)量，用作分類的數(shù)量指標(biāo)，從而可以定量地進(jìn)行分類。常用的分類統(tǒng)計(jì)量有距離和相似系數(shù)，它們的定義與聚類分析的類型有關(guān)。

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

設(shè)兩個(gè)P維向量x分別表示兩個(gè)對(duì)象，它們的歐氏距離[2]為：

傳統(tǒng)的K均值聚類分析，不考慮對(duì)象中每個(gè)變量在聚類過(guò)程中體現(xiàn)作用的不同，而是統(tǒng)一看待，用這樣計(jì)算的距離來(lái)表示兩個(gè)對(duì)象的相似度并不確切。對(duì)象間的距離[3]表示的是對(duì)象的相近程度，而相似不僅依賴于對(duì)象間的相近程度，還依賴于對(duì)象內(nèi)在的性質(zhì)，即對(duì)象中每個(gè)變量的重要性是不同的。

2 解決方法

新的度量空間

其中β是一個(gè)正的常數(shù)，從這個(gè)距離函數(shù)[4]可以發(fā)現(xiàn)，d（x，y）是一個(gè)關(guān)于‖x-y‖的單調(diào)遞增函數(shù)，即 d（x，y）會(huì)隨著的增大而增大。下面證明d（x，y）是一個(gè)度量，即證明該度量是否滿足度量的3個(gè)條件[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）因?yàn)棣率且粋€(gè)正的常數(shù)，而‖x-y‖為一個(gè)正數(shù)，從而1-exp（-β‖x-y‖2）＞0，故 d（x，y）＞0

2） 因?yàn)?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）為一個(gè)度量

眾所周知，若要使得一個(gè)點(diǎn)的權(quán)重更具魯棒性[6]，則需滿足異常點(diǎn)或噪聲點(diǎn)的權(quán)重較小，而數(shù)據(jù)集中的緊實(shí)點(diǎn)的權(quán)重則應(yīng)較大。這個(gè)新度量恰恰可以滿足這個(gè)要求。

應(yīng)用新的距離度量得到改進(jìn)的K-means算法的目標(biāo)函數(shù)。

應(yīng)用新的距離度量得到改進(jìn)的K-means算法的中心更新公式

新的中心更新公式與經(jīng)典的聚類分析算法中心更新公式的區(qū)別在于權(quán)重[7]，對(duì)于傳統(tǒng)的K-means均值算法，每個(gè)數(shù)據(jù)點(diǎn)的權(quán)重或?yàn)?或?yàn)?，故傳統(tǒng)的K-means均值算法也稱為硬K-means算法（Hard K-Means）。應(yīng)用新的距離度量之后，數(shù)據(jù)點(diǎn)的權(quán)重不再只為1或0，而是由系數(shù) exp（-β‖xj-wj‖2）來(lái)確定，這就將硬劃分轉(zhuǎn)化為軟劃分。軟劃分[8]是改進(jìn)聚類算法的一種強(qiáng)有效的方法。

3 算法實(shí)現(xiàn)

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

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

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

2）將評(píng)分項(xiàng)為0的各項(xiàng)以某一均值（或者設(shè)定的值）θ代替；//避免出現(xiàn)大規(guī)模稀疏矩陣[9]而影響推薦質(zhì)量

CenterSet=k-means（T，k，CenterSet）；//進(jìn)行聚類操作得到k個(gè)中心，找到一個(gè)新中心

4 算法流程圖

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

5 實(shí)驗(yàn)測(cè)試

我們實(shí)現(xiàn)了K均值算法和改進(jìn)的算法，并通過(guò)實(shí)驗(yàn)對(duì)兩個(gè)算法進(jìn)行了對(duì)比，實(shí)驗(yàn)環(huán)境采用c/s結(jié)構(gòu)，服務(wù)器計(jì)算機(jī)cpu為酷睿i5，內(nèi)存為4 G，數(shù)據(jù)庫(kù)為SQL Server2008，實(shí)現(xiàn)的編程語(yǔ)言為Java，選用Myeclipse作為集成開(kāi)發(fā)環(huán)境。

實(shí)驗(yàn)選取了一個(gè)真實(shí)的超市交易數(shù)據(jù)庫(kù)的一部分?jǐn)?shù)據(jù)，對(duì)不同數(shù)目的數(shù)據(jù)分別執(zhí)行2種算法，得到執(zhí)行時(shí)間結(jié)果如圖2所示。

其中橫坐標(biāo)為實(shí)驗(yàn)數(shù)據(jù)條目數(shù)，縱坐標(biāo)為執(zhí)行時(shí)間。

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

6 結(jié) 論

圖2 測(cè)試結(jié)果圖Fig.2 Results chart of the test system

文中在傳統(tǒng)的K均值算法的基礎(chǔ)上改進(jìn)了距離算法，提出了一種新的距離度量代替歐式距離，避免了傳統(tǒng)K均值算法各個(gè)數(shù)據(jù)點(diǎn)的權(quán)重只能為0或?yàn)?的缺陷，應(yīng)用新的距離度量之后，數(shù)據(jù)點(diǎn)的權(quán)重不再只為1或0，而是由系數(shù)來(lái)確定，這就將硬劃分轉(zhuǎn)化為軟劃分，提高了算法執(zhí)行效率，從而能更好地在實(shí)際應(yīng)用中進(jìn)行聚類分析，最后通過(guò)實(shí)驗(yàn)驗(yàn)證了應(yīng)用新的距離度量比傳統(tǒng)K均值算法在算法上效率確實(shí)有了一定的提高。

[1]趙立平.電了商務(wù)概論[M].上海:復(fù)旦大學(xué)出版社，2000.

[2]朱明.數(shù)據(jù)挖掘[M].北京：中國(guó)科學(xué)技術(shù)大學(xué)出版社，2002.

[3]夏惠芬，董衛(wèi)民.基于關(guān)聯(lián)規(guī)則的Web挖掘技術(shù)研究[J].現(xiàn)代電子技術(shù)，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數(shù)據(jù)挖掘系統(tǒng)的設(shè)計(jì)及實(shí)現(xiàn)研究[J].計(jì)算機(jī)工程與設(shè)計(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]高陽(yáng).中國(guó)數(shù)據(jù)挖掘研究進(jìn)展[J].南京大學(xué)學(xué)報(bào)：自然科學(xué)版，2011（4）:155-158.

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

[6]丁金龍.基于Web數(shù)據(jù)挖掘技術(shù)下的個(gè)性化信息服務(wù)[J].現(xiàn)代情報(bào)，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.