K_means聚類算法研究

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

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

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

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

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

6、式(1所示.1z i f =x i f -m fs f.(1其中,z i f 為標準度量值,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ù)對象矩陣無法直接應用于聚類分析,所以使用聚類算法之前將數(shù)據(jù)對象矩陣轉換為相異度矩陣,轉換算法根據(jù)數(shù)據(jù)對象間的相異度構造相異度矩陣,相異度矩陣如下所示.0 d (2,10 d (n,1d (n,2.其中,d (i,j 為數(shù)據(jù)對象之間的距離,即相異度,一般為非負值,兩個對象越相似,值越接近0,否則值越大.2.2 相異度計算具體應用聚類分析解決實際問題時,數(shù)據(jù)對象的各變量類型不唯一,常見的有區(qū)間標度變量、二元變量、分類變量、序數(shù)變量和比例標度變量4

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

9、0,否則為1.d (f ij 的值為變量f 對i 和j 之間的相異度的貢獻,其計算方法取決于數(shù)據(jù)對象的變量類型.如果變量f 是區(qū)間標度變量,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ū)間標度變量,計算

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

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

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

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

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

15、26:10-12.6Jiawei Han,M icheline Kamber.數(shù)據(jù)挖掘概念與技術M.范明,孟小峰,譯.北京:機械工業(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