K_means聚類(lèi)算法研究

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

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

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

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

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

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

8、.由這幾種類(lèi)型中的一種或幾種組合成實(shí)際的數(shù)據(jù)對(duì)象的類(lèi)型.另外,在信息檢索中的文本聚類(lèi),數(shù)據(jù)對(duì)象包含了大量的文字符號(hào),一般用非傳統(tǒng)度量的方式,采用非度量相異度進(jìn)行聚類(lèi)分析.本文中數(shù)據(jù)對(duì)象屬于傳統(tǒng)可度量變量,是包含幾種類(lèi)型的混合類(lèi)型的變量,把不同類(lèi)型的變量放在同一個(gè)相異度矩陣中.假設(shè)數(shù)據(jù)集合中包含p 個(gè)混合類(lèi)型的變量,對(duì)象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ù)對(duì)象i 或j 沒(méi)有變量f 的值,或值為0,且變量f 是非對(duì)稱(chēng)二元變量,則 (f ij的值為

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

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

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

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

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

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