K_means聚類算法研究

1、第30卷第1期Vol 30 No 1長春師范學(xué)院學(xué)報(自然科學(xué)版Journal of Changchun Normal Universi ty(Natural Science2011年2月Feb.2011K-means 聚類算法研究孫 庚1,馮艷紅1,郭顯久1,張春平2(1.大連海洋大學(xué)信息工程學(xué)院,遼寧大連 116023;2.黑龍江工程學(xué)院土木與建筑工程學(xué)院,黑龍江哈爾濱 150050摘 要K-means 算法作為聚類分析算法,已被廣泛地應(yīng)用到諸多領(lǐng)域。本文研究了K-means 算法的基本原理,并將其應(yīng)用到高校學(xué)生入學(xué)信息分析中。高考學(xué)生入學(xué)的相關(guān)信息包含了大量重要的學(xué)習(xí)及其他方面的信息,對

2、這些數(shù)據(jù)信息進(jìn)行分析和研究,有助于教師對不同類別的學(xué)生進(jìn)行不同方式的教學(xué),做到因材施教。首先對學(xué)生的入學(xué)信息數(shù)據(jù)進(jìn)行預(yù)處理,然后使用K-means 算法,對學(xué)生信息進(jìn)行分類評價;最后利用所獲得的分類結(jié)果指導(dǎo)學(xué)生在大學(xué)期間的學(xué)習(xí)方向以及教師對學(xué)生的培養(yǎng)工作。關(guān)鍵詞聚類;K-means;學(xué)生信息中圖分類號TP27 文獻(xiàn)標(biāo)識碼A 文章編號1008-178X(201101-0001-04收稿日期2010-11-01作者簡介孫 庚(1979-,男,黑龍江齊齊哈爾人,大連海洋大學(xué)信息工程學(xué)院講師,碩士,從事計算機(jī)應(yīng)用研究。0 前言聚類是將物理或抽象對象的幾何分成相似的對象類或簇的過程.使同一個簇中的對象之

3、間具有很高的相似度,不同簇中的對象高度相異.聚類分析已廣泛地用于很多領(lǐng)域,例如在經(jīng)濟(jì)學(xué)的市場研究中幫助市場分析人員根據(jù)客戶的購買模式發(fā)現(xiàn)不同的客戶群,在生物學(xué)中根據(jù)基因或其他特性推導(dǎo)動物或植物的分類,聚類分析中的離群點檢測可用于商業(yè)領(lǐng)域的信用卡欺詐檢測和監(jiān)控電子商務(wù),聚類分析還可以用于WEB 文檔的分類等其他應(yīng)用領(lǐng)域1.在不同的應(yīng)用領(lǐng)域和不同的學(xué)科中,很多聚類技術(shù)都得到了發(fā)展.常用的聚類方法有:劃分發(fā)方法、層次方法、基于密度的方法、基于網(wǎng)格的方法以及基于模型的方法2.作為數(shù)據(jù)挖掘的主要任務(wù)之一的聚類分析方法,應(yīng)具有可伸縮性、處理不同類型屬性、發(fā)現(xiàn)任意形狀的簇、處理帶噪聲的數(shù)據(jù)、處理高維數(shù)據(jù)和處

4、理基于約束的聚類的能力3.本文主要研究劃分方法中的K-means 聚類方法,并改進(jìn)算法將其應(yīng)用到實際領(lǐng)域.高校學(xué)生的入學(xué)信息承載了學(xué)生大量的重要的學(xué)習(xí)和其他方面的信息,給高等教育提供了信息幫助,做到因材施教,有的放矢,有利于培養(yǎng)多方面的人才.學(xué)生入學(xué)信息包括了學(xué)生此前的全部學(xué)習(xí)經(jīng)歷、獎懲經(jīng)歷、興趣愛好、身體狀況、個人閱歷、參加的社會活動、所在地域等多方面的信息,通過充分地利用這些信息資源,深層次地挖掘每個學(xué)生的獨立特性,進(jìn)行分類,對不同類別進(jìn)行分析,并采取恰當(dāng)?shù)慕虒W(xué)、教育和培養(yǎng)方案,以達(dá)到更好地培養(yǎng)人才的目的.1 數(shù)據(jù)預(yù)處理1.1 學(xué)生入學(xué)信息分析及處理作為數(shù)據(jù)挖掘的主要技術(shù)之一,聚類分析成為

5、一種常用的分析數(shù)據(jù)的方法.主要處理大量的相關(guān)或不相關(guān)數(shù)據(jù)信息,以數(shù)據(jù)為研究對象.因此,我們應(yīng)先分析學(xué)生信息.信息取自學(xué)生檔案,信息內(nèi)容零散、復(fù)雜,需要先進(jìn)行整理,并對信息進(jìn)行基本的處理,形成學(xué)生信息數(shù)據(jù)庫,作為聚類分析的數(shù)據(jù)對象集.對缺失數(shù)據(jù)進(jìn)行處理,采用忽略該條信息、人工填寫、用均值填充等方法來處理.為盡量減少對聚類結(jié)果的影響,本文運用屬性的均值填充方法處理缺失數(shù)據(jù).接下來進(jìn)行數(shù)據(jù)的標(biāo)準(zhǔn)化.由于數(shù)據(jù)對象包含不同的數(shù)據(jù)類型,不同的數(shù)據(jù)類型的度量方式和度量范圍不同,對聚類結(jié)果有影響,所以為避免這種情況,在聚類分析之前對數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理.計算標(biāo)準(zhǔn)度量值,給定數(shù)據(jù)對象的變量f ,標(biāo)準(zhǔn)化處理方法如公

6、式(1所示.1z i f =x i f -m fs f.(1其中,z i f 為標(biāo)準(zhǔn)度量值,x i f 為變量f 的第i 個度量值,m f 為變量f 的均值,s f 為均值絕對值偏差,如公式(2所示.s f =1n(|x 1f -m f |+|x 2f -m f |+ +|x n f -m f |.(21.2 確定距離度量d (i,j =(x i 1-x j 12+(x i 2-x j 22+ +(x in -x jn 2.(3其中i =(x i 1,x i 2, ,x in ,i =(x i 1,x i 2, ,x in ,為任意兩個數(shù)據(jù)對象.2 相異度分析2.1 數(shù)據(jù)對象 數(shù)據(jù)對象在聚類分

7、析中一般用數(shù)據(jù)矩陣表示,矩陣如下所示.x 11 x 1f x 1p x n 1x n fx n p.矩陣中有n 個數(shù)據(jù)對象,每個數(shù)據(jù)對象有p 個變量.數(shù)據(jù)對象矩陣無法直接應(yīng)用于聚類分析,所以使用聚類算法之前將數(shù)據(jù)對象矩陣轉(zhuǎn)換為相異度矩陣,轉(zhuǎn)換算法根據(jù)數(shù)據(jù)對象間的相異度構(gòu)造相異度矩陣,相異度矩陣如下所示.0 d (2,10 d (n,1d (n,2.其中,d (i,j 為數(shù)據(jù)對象之間的距離,即相異度,一般為非負(fù)值,兩個對象越相似,值越接近0,否則值越大.2.2 相異度計算具體應(yīng)用聚類分析解決實際問題時,數(shù)據(jù)對象的各變量類型不唯一,常見的有區(qū)間標(biāo)度變量、二元變量、分類變量、序數(shù)變量和比例標(biāo)度變量4

8、.由這幾種類型中的一種或幾種組合成實際的數(shù)據(jù)對象的類型.另外,在信息檢索中的文本聚類,數(shù)據(jù)對象包含了大量的文字符號,一般用非傳統(tǒng)度量的方式,采用非度量相異度進(jìn)行聚類分析.本文中數(shù)據(jù)對象屬于傳統(tǒng)可度量變量,是包含幾種類型的混合類型的變量,把不同類型的變量放在同一個相異度矩陣中.假設(shè)數(shù)據(jù)集合中包含p 個混合類型的變量,對象i 和j 之間的相異度d (i,j 定義如公式(4所示.d (i,j = pf =1 (f i j d (f i jp f =1 (f i j.(4其中, (f i j 的值為0或1,當(dāng)數(shù)據(jù)對象i 或j 沒有變量f 的值,或值為0,且變量f 是非對稱二元變量,則 (f ij的值為

9、0,否則為1.d (f ij 的值為變量f 對i 和j 之間的相異度的貢獻(xiàn),其計算方法取決于數(shù)據(jù)對象的變量類型.如果變量f 是區(qū)間標(biāo)度變量,d (f i j 的值如公式(5所示.d (f i j =|x i f -x jf |max h x hf -min h x h f.(5其中,h 遍歷f 的所有非缺失對象.如果f 是二元或分類變量,d (f ij 的值如公式(6所示.d (f i j =0,x i f =x jf ;1,x i f x jf .(62如果f 是序數(shù)變量,計算秩r ij ,映射為z i j =r ij -1M f -1,M f為類別總數(shù),將z i j 作為區(qū)間標(biāo)度變量,計算

10、相異度d (f i j .如果f 是比例標(biāo)度變量,可采用如下三種方法計算相異度.方法一:采用與處理區(qū)間標(biāo)度變量相同的方法計算相異度,該方法產(chǎn)生的結(jié)果不準(zhǔn)確,因為刻度可能扭曲.方法二:對比例標(biāo)度變量進(jìn)行對數(shù)變換,將變量f 的值x i f 變換為y i j =log (x i f ,把y ij 作為區(qū)間標(biāo)度變量,計算相異度d ij .方法三:將變量f 當(dāng)作連續(xù)的序數(shù)數(shù)據(jù),計算r ij 和z i j ,將z ij 作為區(qū)間標(biāo)度變量,計算相異度d (f i j .在本文的應(yīng)用中,從學(xué)生入學(xué)信息數(shù)據(jù)庫中抽取部分樣本作為實驗數(shù)據(jù),進(jìn)行研究,抽取的數(shù)據(jù)如表1所示,只列出3條記錄,實際實驗樣本為1000名學(xué)生

11、的記錄.表1 學(xué)生信息數(shù)據(jù)樣例id 科別性別高考總分政治面貌身高愛好特長1理工男563黨員178文學(xué)類2文史女459團(tuán)員162智力類3管理男468其他181體育類3.1 基本K-means 聚類的算法描述輸入:k :簇的數(shù)目D:數(shù)據(jù)對象的集合輸出:k 個簇的集合算法:( 從D 中隨機(jī)選取k 個數(shù)據(jù)對象作為簇的初始中心;( 根據(jù)簇中數(shù)據(jù)對象的均值,將每個數(shù)據(jù)對象重新分配到距離最近的簇;( 重新計算每個新簇中的對象的均值;( 如果準(zhǔn)則函數(shù)收斂,則結(jié)束聚類分析,否則回到第二步.其中,準(zhǔn)則函數(shù)一般采用平方誤差準(zhǔn)則,如公式(7所示.E = ki =1 p Ci|p -m i |2.(7其中,E 為所有數(shù)

12、據(jù)對象的平方誤差和,p 為給定對象,m i 是簇C i 的均值.用平方誤差準(zhǔn)則使生成的k 個類盡可能地緊湊和獨立.4 算法實現(xiàn)根據(jù)3.1的算法描述,并對計算機(jī)專業(yè)學(xué)生信息數(shù)據(jù)庫系統(tǒng)的學(xué)生數(shù)據(jù)進(jìn)行規(guī)范化,取樣150條記錄,借助于Matlab 軟件,假設(shè)分為兩類,聚類結(jié)果如圖1所示.其中,三角符號和正方形符號各代表一類學(xué)生.從圖1中看到,得到了較好的聚類結(jié)果.將聚類結(jié)果應(yīng)用到實際中,可以對不同類別的學(xué)生進(jìn)行不同方式的教育教學(xué).3 圖1 學(xué)生信息聚類結(jié)果5 結(jié)論聚類分析現(xiàn)已成為一個跨學(xué)科交叉的領(lǐng)域,被廣泛應(yīng)用于很多領(lǐng)域.在高校教育方面,聚類分析可以幫助教師發(fā)現(xiàn)學(xué)生中不同的特征組,采取因材施教的方法授

13、課.本文主要是利用了聚類分析中的K-means聚類算法對學(xué)生的入學(xué)信息進(jìn)行分析,實現(xiàn)對學(xué)生的分組教學(xué).由于K-means算法采用最小化平方誤差函數(shù)作為評價函數(shù),所以當(dāng)聚類的結(jié)果簇是緊湊的,并且不存在離群點時,聚類效果很好.其計算復(fù)雜度是O(nkt,n為數(shù)據(jù)對象總數(shù)量,k是聚類的類別數(shù),t是迭代的次數(shù),從其時間復(fù)雜度上看,當(dāng)處理大量數(shù)據(jù)時,其伸縮度和效率較好.但是,當(dāng)存在離群點時,由于這些點對均值有很大的影響,導(dǎo)致聚類結(jié)果不準(zhǔn)確;K-means聚類算法必須事先給出聚類的數(shù)目,即k的值;另外,只有均值可計算才行得通,對于某些應(yīng)用,包含有分類屬性,若無確切的均值定義,該方法無法實施.K-means算

14、法還可能出現(xiàn)終止于局部最優(yōu)解的問題,有待進(jìn)一步解決.參考文獻(xiàn)1李路.基于二叉樹算法實現(xiàn)Linux網(wǎng)絡(luò)Socket流量控制與計費的設(shè)計J.沈陽大學(xué)學(xué)報,2008(1:4-6.2孫可,劉杰,王學(xué)穎.K均值聚類算法初始質(zhì)心選擇的改進(jìn)J.沈陽師范大學(xué)學(xué)報:自然科學(xué)版,2009(4:448-450.3逄玉俊,柳明,李元.K均值聚類分析在過程改進(jìn)中的應(yīng)用J.華中科技大學(xué)學(xué)報:自然科學(xué)版,2009(S1:245-247.4司永勝,劉剛,高瑞.基于K-均值聚類的綠色蘋果識別技術(shù)J.農(nóng)業(yè)機(jī)械學(xué)報,2009(S1:100-104.5羅洎,王瑩.基于K-均值聚類的中國存貨景氣指數(shù)設(shè)計研究J.經(jīng)濟(jì)研究導(dǎo)刊,2009(

15、26:10-12.6Jiawei Han,M icheline Kamber.數(shù)據(jù)挖掘概念與技術(shù)M.范明,孟小峰,譯.北京:機(jī)械工業(yè)出版社,2006:256-266.Research on K-means Clustering AlgorithmSUN Geng1,FENG Yan-hong1,GUO Xian-jiu1,Z HANG Chun-ping2(1.School of Information Engineering,Dalian Ocean University,Dalian116023,China;2.School of Civil and Building Engineerin

16、g,Heilongjiang Institute of Technology,Harbin150050,China Abstract:As a kind of clustering analysis algorithm,K-means algorithm has widely been applied to various fields.In this paper,we research the basic principle of this algorithm and apply it to information analysis of senior school students.The

17、 in formation about senior school students entrance includes much important information about t study and other aspects.Ana lyzing and researching these data and information are helpful for universities to carry out c ollege education and realize indi vidualized instruction.Firstly,we preprocess the inf