陳 朋

（上海大學(xué) 管理學(xué)院，上海 200444）

近年來，隨著數(shù)據(jù)挖掘工具的不斷涌現(xiàn)，如何選擇數(shù)據(jù)挖掘工具已成為數(shù)據(jù)挖掘技術(shù)引入的一大難題。Elder Research Inc.(ERI)提供了許多數(shù)據(jù)挖掘系統(tǒng)和工具的性能測(cè)試報(bào)告[1]。

不同的軟件有不同的特點(diǎn)，一方面要關(guān)注它們的性能，同時(shí)也要關(guān)注這些軟件應(yīng)用到數(shù)據(jù)挖掘中時(shí)產(chǎn)生的結(jié)果。下面僅討論在 SPSS（ver.16）和 KNIME(ver.2.1.1)中K-means算法所產(chǎn)生的結(jié)果的特點(diǎn)和差別。

1 K-means算法

K-means[2]算法是一種著名的并且常用的聚類方法。K-means以k為參數(shù)，把n個(gè)對(duì)象分為k個(gè)簇(cluster),以使簇內(nèi)具有較高的相似度，而簇間的相似度較低。相似度的計(jì)算是根據(jù)一個(gè)簇中對(duì)象的平均值(被看作簇的重心)來進(jìn)行的。

K-means算法隨機(jī)地選擇k個(gè)對(duì)象，每個(gè)對(duì)象初始地代表了一個(gè)簇的平均值或中心，根據(jù)其與各個(gè)簇中心的距離，對(duì)剩余的每個(gè)對(duì)象賦給最近的簇,然后重新計(jì)算每個(gè)簇的平均值。這個(gè)過程不斷重復(fù)，直到準(zhǔn)則函數(shù)收斂。通常，采用平方誤差準(zhǔn)則定義如下：

式中，E是數(shù)據(jù)庫中所有對(duì)象的平方誤差的總和，p是空間中的點(diǎn)，表示給定的數(shù)據(jù)對(duì)象，mi是簇Ci的平均值(p和mi都是多維的)。這個(gè)準(zhǔn)則試圖使生成的結(jié)果簇盡可能地緊湊和獨(dú)立。

該算法嘗試找出使平方誤差函數(shù)值最小的k個(gè)劃分。若結(jié)果簇密集，而簇與簇之間的區(qū)別明顯時(shí)，其效果好。對(duì)處理大數(shù)據(jù)集，該算法的可伸縮度和效率相對(duì)較高，因?yàn)樗膹?fù)雜度是O(nkt)，其中，n是所有對(duì)象的數(shù)目，k 是簇的數(shù)目，t是迭代的次數(shù)。 通常，k＜＜n，且 t＜＜n。這個(gè)算法經(jīng)常以局部最優(yōu)結(jié)束。

但是，K-means方法只有在簇的平均值被定義的情況下才能使用,這可能不適用于某些應(yīng)用，例如涉及有分類屬性的數(shù)據(jù)。該方法的一個(gè)缺點(diǎn)是要求用戶必須事先給出k(要生成的簇的數(shù)目)。K-means方法不適用于發(fā)現(xiàn)非凸面形狀的簇。此外，它對(duì)于“噪聲”和孤立點(diǎn)數(shù)據(jù)敏感,少量的該種數(shù)據(jù)能夠?qū)ζ骄诞a(chǎn)生極大的影響。

2 SPSS和KNIME的介紹

SPSS(Statistical Product and Service Solutions)是世界上最早采用圖形菜單驅(qū)動(dòng)界面的統(tǒng)計(jì)軟件，它最突出的特點(diǎn)就是操作界面極為友好，輸出結(jié)果美觀漂亮。它將幾乎所有的功能都以統(tǒng)一、規(guī)范的界面展現(xiàn)出來，使用Windows的窗口方式展示各種管理和分析數(shù)據(jù)方法的功能，使用對(duì)話框展示出各種功能選擇項(xiàng)，用戶只要掌握一定的Windows操作技能，粗通統(tǒng)計(jì)分析原理，就可以使用該軟件為特定的科研工作服務(wù)。SPSS采用類似Excel表格的方式輸入與管理數(shù)據(jù)，數(shù)據(jù)接口較為通用，能方便地從其他數(shù)據(jù)庫中讀取數(shù)據(jù)。其統(tǒng)計(jì)過程包括了常用的、較為成熟的統(tǒng)計(jì)過程，完全可以滿足非統(tǒng)計(jì)專業(yè)人士的工作需要。輸出結(jié)果十分美觀，存儲(chǔ)時(shí)則是專用的SPO格式，可以轉(zhuǎn)存為HTML格式和文本格式。對(duì)于熟悉老版本編程運(yùn)行方式的用戶，SPSS還特別設(shè)計(jì)了語法生成窗口，用戶只需在菜單中選好各個(gè)選項(xiàng)，然后按“粘貼”按鈕就可以自動(dòng)生成標(biāo)準(zhǔn)的SPSS程序，極大地方便了中、高級(jí)用戶。

KNIME(Konstanz Information Miner)[3]數(shù)據(jù)挖掘工具基于Eclipse開發(fā)環(huán)境精心開發(fā)，可以擴(kuò)展使用Weka中的挖掘算法。它采用類似數(shù)據(jù)流（data flow）的方式來建立分析挖掘流程。挖掘流程由一系列功能節(jié)點(diǎn) （node）組成，每個(gè)節(jié)點(diǎn)有輸入/輸出端口（port），用于接收數(shù)據(jù)或模型、導(dǎo)出結(jié)果。節(jié)點(diǎn)之間的連接很方便，直接用鼠標(biāo)拖拽連接端口即可。

KNIME中每個(gè)節(jié)點(diǎn)都帶有交通信號(hào)燈，用于指示該節(jié)點(diǎn)的狀態(tài)(未連接、未配置、缺乏輸入數(shù)據(jù)時(shí)為紅燈,準(zhǔn)備執(zhí)行為黃燈,執(zhí)行完畢后為綠燈)。KNIME的特色功能HiLite允許用戶在節(jié)點(diǎn)結(jié)果中標(biāo)記感興趣的記錄，并進(jìn)一步展開后續(xù)探索。

3 兩類數(shù)據(jù)集的聚類結(jié)果

3.1 大樣本數(shù)據(jù)集的聚類分析

鳶尾花數(shù)據(jù)集[4]被公認(rèn)為最著名的用于數(shù)據(jù)挖掘的數(shù)據(jù)集，它包含3種植物種類，每種各有 50個(gè)樣本，所以樣本總數(shù)為150。它有花萼長(zhǎng) (sepallength)、花萼寬(sepalwidth)、花瓣長(zhǎng)(petallength)、花瓣寬(petalwidth)4 個(gè)屬性,且都是數(shù)值屬性。為了使實(shí)驗(yàn)結(jié)果更明顯，添加屬性class用以顯示鳶尾花所處的類，數(shù)據(jù)庫內(nèi)的三個(gè)品種分別是 Iris-versicolor、Iris-setosa 和 Iris-virginicia。

設(shè)置k=3，在SPSS中K-means的運(yùn)算結(jié)果如表1所示，KNIME中K-means的運(yùn)算結(jié)果如圖1所示。

表1 SPSS中K-means運(yùn)算結(jié)果(k=3)

由于兩個(gè)工具得到的聚類序號(hào)不具有一一對(duì)應(yīng)關(guān)系，為了比較兩種結(jié)果需要對(duì)類號(hào)進(jìn)行統(tǒng)一。根據(jù)鳶尾花數(shù)據(jù)集的屬性class可以完成這項(xiàng)工作，得到統(tǒng)一后的結(jié)果如表2所示。

圖1 KNIME中K-means運(yùn)算的結(jié)果(k=3)

表2 進(jìn)行統(tǒng)一后的聚類結(jié)果

3.2 小樣本數(shù)據(jù)集的聚類分析

實(shí)驗(yàn)所采用的小樣本數(shù)據(jù)集如表3所示，當(dāng)k分別設(shè)置為2和3時(shí)，使用KNIME的運(yùn)算結(jié)果如圖2所示，使用SPSS的運(yùn)算結(jié)果如表4和表5所示。

表3 數(shù)據(jù)準(zhǔn)備

通過以上結(jié)果可以得出這樣的結(jié)論：當(dāng)K-means聚類方法用于大樣本數(shù)據(jù)集的時(shí)候，無論是從聚類的最終中心距離，還是每個(gè)聚類內(nèi)所有樣本的數(shù)目，SPSS和KNIME產(chǎn)生的聚類幾乎是一致的，即排除K-means算法本身的一些缺陷以外，不同的分析工具不會(huì)對(duì)聚類結(jié)果產(chǎn)生顯著的影響。

表4 SPSS中K-means運(yùn)算的結(jié)果(k=2)

表5 SPSS中K-means運(yùn)算的結(jié)果(k=3)

當(dāng)K-means聚類方法用于大樣本數(shù)據(jù)集的時(shí)候，本文只是選取了在k值分別是2和3兩種情況下的結(jié)果，可以看出k值從2變?yōu)?時(shí)，兩種工具得出的最終結(jié)果存在較大的差異，這是因?yàn)樗惴ㄩ_始時(shí)隨機(jī)地選擇k個(gè)對(duì)象，兩種工具選取的樣本將會(huì)有所不同，加之樣本總數(shù)的限制，最終導(dǎo)致了聚類結(jié)果的差別。

數(shù)據(jù)挖掘的工具還有很多，如何進(jìn)行數(shù)據(jù)集的選取是目前存在的問題，為了得到更加完善和具有普通意義的結(jié)論，需要關(guān)注這些問題。

[1]ABBOTT D W,MATKOVSKY I P.An evaluation of high-end data mining tools for fraud detection[R].IEEE International Conference on Systems.1998,12:12-14.

[2]HAN Jia Wei，KAMBER M著.數(shù)據(jù)挖掘概念與技術(shù)[M].范明，孟小峰,譯.北京：機(jī)械工業(yè)出版社，2004.

[3]BERTHOLD M R,CEBRON N.Knime:the konstanz information miner[R].http://www.knime.org,2007,9.

[4]FISHER R A.Iris plants database[DB].http://archive.ics.uci.edu/ml/datasets/Iris，1988,7.

[5]黃穎,李偉.EM算法與 K-Means算法比較[J].計(jì)算機(jī)與現(xiàn)代化，2007(9):12-14.

[6]LI Tao Ying,CHEN Yan.An effective algorithm to solve optimal k value of K-means algorithm[S].International symposium on distributed computing and applications to business，2006.

[7]JIANG Sheng Yi,LI Qing Hua.An enhanced K-means clustering algorithm[J].Computer Engineer&Science，2006.

[8]袁方,周志永,宋鑫.初始聚類中心優(yōu)化的 K-means算法[J].計(jì)算機(jī)工程,2007,2(33).

[9]張雪英.國外先進(jìn)數(shù)據(jù)挖掘工具的比較分析[J].計(jì)算機(jī)工程,2003,9(29).