改進的k_平均聚類算法研究

1、 200 改進的 k-平均聚類算法研究孫士保 1,2,秦克云 1(1. 西南交通大學智能控制開發(fā)中心,成都 610031; 2. 河南科技大學電子信息工程學院,洛陽 471003摘 要:聚類算法的好壞直接影響聚類的效果。該文討論了經(jīng)典的 k-平均聚類算法,說明了它存在不能很好地處理符號數(shù)據(jù)和對噪聲與孤 立點數(shù)據(jù)敏感等不足,提出了一種基于加權改進的 k-平均聚類算法,克服了 k-平均聚類算法的缺點,并從理論上分析了該算法的復雜度。 實驗證明,用該方法實現(xiàn)的數(shù)據(jù)聚類與傳統(tǒng)的基于平均值的方法相比較,能有效提高數(shù)據(jù)聚類效果。 關鍵詞:聚類算法; k-平均;權;聚類數(shù)據(jù)挖掘Research on Mod

2、ified k-means Data Cluster AlgorithmSUN Shibao1,2, QIN Keyun1(1. Intelligent Control Development Center, Southwest Jiaotong University, Chengdu 610031;2. Electronic Information Engineering College, Henan University of Science and Technology, Luoyang 471003【 Abstract 】 The method of data clustering w

3、ill influence the effect of clustering directly. The algorithm of k-means is discussed, the shortagesof this algorithm such as it can not deal with symbolic data and it is sensitive for data of isolation point and noise are demonstrated. A modified k-meansclustering algorithm based on weights is put

4、 forward, it changes the shortcomings of k-means. Its complexity is analyzed from theoretical. Theexperiments show that, compared with traditional method based on means, the modified data clustering algorithm can improve the efficiency of dataclustering.【 Key words】 cluster algorithm; k-means; weigh

5、ts; cluster data mining計 算 機 工 程 Computer Engineering第 33卷 第 13期Vol.33 No.13 2007年 7月July 2007·人工智能及識別技術 ·文章編號:1000 3428(200713 0200 02文獻標識碼:A中圖分類號:TP183聚類是將物理或抽象對象的集合分組成為由類似的對象組成的多個類的過程。它的目的是使得屬于同一類別的個體 之間的相似度盡可能大,而不同類別的個體之間的相似度盡 可能小。在機器學習領域,聚類是無指導學習的一個例子。 聚類分析是知識發(fā)現(xiàn)的重要方法,在圖像識別、信息檢索、 數(shù)據(jù)挖掘、

6、統(tǒng)計學、機器學習、空間數(shù)據(jù)庫、生物學以及市 場營銷等領域有著廣泛的應用 14。目前常用的聚類算法包括:以 k-平均算法 (k-Means5和 k-中心點算法 (k-Medoid6為代表的劃分法;以 AGNES 6和 DIANA 6為代表的層次聚類算法; 以 DBSCAN 7和 OPTICS 8為代表的基于密度的方法;以 STING 9為代表的基于網(wǎng)格的 方法;以 COBWEB 2和 SOM 10為代表的基于模型的方法; 以順序地比較一個集合中的對象 11和 OLAP 數(shù)據(jù)立方體 12為代表的基于孤立點的分析方法。這些方法中的大部分聚類 算法都是面向數(shù)值屬性,而針對符號屬性的比較少 1,2?，F(xiàn)有

7、 許多改進的算法,如基于數(shù)據(jù)場改進的 PAM 聚類算法 13, 基于 Rough 集的層次聚類算法 14。對于文獻 13中基于數(shù)據(jù) 場改進的 PAM 聚類算法是一種較好的劃分聚類算法, 但在處 理數(shù)據(jù)場勢函數(shù)時的計算開銷很大,很難應用到大型數(shù)據(jù)集 中去;另外,它對數(shù)值屬性效果較好,對符號屬性基本上不 能實現(xiàn)。本文給出一種基于加權改進的 k-平均聚類算法,這 種新的劃分聚類算法,不僅可以處理數(shù)值屬性,而且可以處 理符號屬性, 另外, 當被挖掘的數(shù)據(jù)中存在孤立點數(shù)據(jù)和 “噪 聲”時,這種算法的處理效果也非常好。1 k-平均算法的分析k-平均 (k-Means算法是一種基于劃分方法的聚類算法, 它是

8、最早提出的較為經(jīng)典的聚類算法之一。 1.1 k-平均算法k-平均算法的主要思想是試圖對 n 個對象給出 k 個劃分 (k n ,其中每個劃分代表一個簇。首先,隨機地選擇 k 個對 象,每個對象初始地代表一個簇的平均值或中心。對剩余的 每個對象, 根據(jù)其與各個簇中心的距離, 將它賦給最近的簇。 然后重新計算每個簇的平均值,對數(shù)據(jù)庫中的每個對象與每 個簇的平均值相比較,把對象賦給最相似的某個簇。這個過 程不斷重復,直到簇中的對象都是“相似的” ,而不同簇中的 對象都是 “相異的” , 即準則函數(shù)收斂使平方誤差函數(shù)值最小。 1.2 k-平均算法的優(yōu)缺點用 k-平均算法來聚類時,當結(jié)果簇是密集的,而簇

9、與簇 之間區(qū)別明顯時,它的效果較好。對處理大數(shù)據(jù)集,該算法 是相對可伸縮的和高效率的,因為它的復雜度是 O (nkt ,其 中, n 是所有對象的數(shù)目, k 是簇的數(shù)目, t 是迭代的次數(shù)。 通常 k «n 且 t «n 。這個算法經(jīng)常以局部最優(yōu)結(jié)束。但是, k-平均方法只有在簇的平均值被定義的情況下才能使用。這對 于處理符號屬性的數(shù)據(jù)不適用,它還要求用戶必須事先給出 k (要生成的簇的數(shù)目 值。另外,對于“噪聲”和孤立點數(shù)據(jù) 是敏感的,少量的該類數(shù)據(jù)能夠?qū)ζ骄诞a(chǎn)生極大的影響。 1.3 k-平均算法的過程算法:k-平均。劃分的 k-平均算法基于簇中對象的平 均值。輸入:簇

10、的數(shù)目 k 和包含 n 個對象的數(shù)據(jù)庫?；痦椖?國家自然科學基金資助項目 (60474022作者簡介:孫士保 (1970- ,男,講師、博士研究生,主研方向:智 能信息處理;秦克云,博士、教授、博士生導師 收稿日期:2006-07-10 E-mail :sunshibao 201輸出:k 個簇,使平方誤差準則最小。 方法:(1任意選擇 k 個對象作為初始的簇中心; (2repeat ;(3根據(jù)簇中對象的平均值, 將每個對象 (重新 賦給最類似的簇; (4更新簇的平均值,即計算每個簇中對象的平均值; (5until 不再發(fā)生變化。2 基于加權改進的 k-平均算法2.1 權的產(chǎn)生在含有 n 個數(shù)

11、據(jù)對象的數(shù)據(jù)庫中,每個數(shù)據(jù)對象對于知 識發(fā)現(xiàn)來說作用是不同的,為了區(qū)分這些相異之處,給每個 數(shù)據(jù)對象賦予一個定量的值 j w 即權。 =n j jjj w w w 1,其中=ni j i j x x d n w 1, (1, , (j i x x d 為 i x 與 j x 之間的相異度, 通常 它是一個非負的數(shù)值,當 i x 與 j x 之間越相似或接近,其值越 接近 0, 反之就越大, 0 , (=i i x x d 。 相異度有多種計算方法 2, 不同的方法會有不同的聚類效果,這里采用常用的距離作為 度量方式。權重越小,說明越相似或越接近;權重越大,說 明差異性越大或越遠。對于比較密集的

12、數(shù)據(jù)點,它們距中心 點的距離相近,權重是比較接近的,很容易聚類在一簇。而 對于一個穩(wěn)定的系統(tǒng)來說 “噪聲” 和孤立點的數(shù)目不會太多, 如果太多這個系統(tǒng)就沒法使用,在本算法中“噪聲”和孤立 點的權重稍大,為了消除“噪聲”和孤立點數(shù)據(jù)的影響,采 用加權平均的方式來解決。當與別的數(shù)據(jù)點一起經(jīng)加權平均 后對整體影響遠小于直接采用平均的方法。因此,這種權重 的計算方法還是比較合理的。2.2 基于加權改進的 k-平均算法 (k-WMeans該算法的基本思想是對簇中每個對象計算加權平均值, 將數(shù)據(jù)庫中的每個對象 (重新 賦給最類似的簇,反復進行這 種操作,直到準則函數(shù)收斂即使平方誤差的總和達到滿意的 程度。

13、這顯然是針對數(shù)值屬性數(shù)據(jù),而符號屬性數(shù)據(jù)直接對 簇中對象求權平均值,然后再對數(shù)據(jù)庫中的每個對象重新調(diào) 整。每一簇的加權平均值的計算方法是:=ti i i j p w t AWM 11, 其中 1(k j AWM j 表示簇 j C 的加權平均值 (或權平均值 ; t 是簇 j C 中對象的個數(shù),不同的簇 t 值不同; i p 是空間中的點, 表示給定的簇 j C 中 t 個數(shù)據(jù)對象之一; i w 是簇 j C 中數(shù)據(jù)對象 的權重。準則函數(shù) (平方誤差總和 21|ijk i j j p C E p AWM =,其中 i p 取簇 j C 中的每一個數(shù)據(jù)。k-WMeans 算法:基于簇中對象的加權

14、平均值或權平 均值。輸入:簇的數(shù)目 k 和包含 n 個對象的數(shù)據(jù)庫。 輸出:k 個簇,使平方誤差總和 E 最小。 方法:(1任意選擇 k 個對象作為初始的簇中心; (2repeat;(3根據(jù)簇中對象的加權平均值 (或權平均值 , 將每個對象 (重新 賦給最類似的簇;(4更新簇的加權平均值 (或權平均值 ,即計算每個簇中對象的 加權平均值 (或權平均值 ;(5until不再發(fā)生變化。3 與經(jīng)典的 k-平均算法的比較本算法與經(jīng)典的 k-平均聚類算法 5相比,就是把經(jīng)典算 法中的平均值變成了這里的加權平均值或權平均值,在計算 加權平均值或權平均值時會增加一些時間開銷,但它的處理 能力卻大大增強。它不

15、僅能處理數(shù)值屬性數(shù)據(jù),還可以處理 符號屬性數(shù)據(jù),對“噪聲”和孤立點數(shù)據(jù)不怎么敏感,少量 的該類數(shù)據(jù)不會對加權平均值 (或權平均值 產(chǎn)生大的影響。 該算法的復雜度和經(jīng)典算法是一致的,也是 O(nkt,其中, n 是所有對象的數(shù)目, k 是簇的數(shù)目, t 是迭代的次數(shù)。因此當 k«n且 t«n時對處理大數(shù)據(jù)集是可伸縮的和高效率的。另外, 該算法和經(jīng)典算法一樣都需要事先估計簇的個數(shù) k ,如想得 到最優(yōu)解時必須試探不同的 k 值。4 實驗結(jié)果本文采用 UCI 15提供的機器學習數(shù)據(jù)庫中的部分數(shù)據(jù)對 k-WMeans 算法和 k-Means 算法進行了測試。對于數(shù)值屬性 數(shù)據(jù)采用

16、iris, thyroid-disease和 glass 3組數(shù)據(jù)集;符號屬性 數(shù)據(jù)采用 balloon, soybean 和 zoo 3組數(shù)據(jù)集,按 k-WMeans 算法和 k-Means 算法分別對它們進行聚類。在表 1中給出了 聚類的結(jié)果。其中,第 1列是數(shù)據(jù)集的名稱;第 2、 3、 4列 分別給出了數(shù)據(jù)集的樣品個數(shù),決策值的個數(shù),以及條件屬 性的個數(shù);第 5列和第 6列是 k-WMeans 算法和 k-Means 算 法在數(shù)據(jù)集上對數(shù)據(jù)進行分類的精確度。表 1 k-WMeans算法和 k-Means 算法在 UCI 數(shù)據(jù)集上的比較DataSet #Instance#Concept#A

17、ttribute k-WMeans Accuracy/%k-MeansAccuracy/%Iris 150 3 4 93.1 89.6 Thyroid-disease 215 3 5 95.2 94.3 Glass 214 7 9 88.7 82.6 Balloon 20 2 4 88.0 0 Soybean 47 4 35 97.3 0 Zoo 101 7 16 95.7 0由表 1可以看出 k-WMeans 對數(shù)據(jù)的聚類結(jié)果總體上優(yōu) 于 k-Means ,同時它又能較好地聚類符號屬性數(shù)據(jù)。5 結(jié)束語引進加權方法對現(xiàn)有的 k-Means 算法進行了嘗試性的改 進,使其減小了孤立點和“噪聲”的

18、影響,實驗證明了這種 基于加權改進的 k-平均聚類算法的有效性。而且這種基于加 權的 k-平均算法能夠處理符號屬性數(shù)據(jù),是傳統(tǒng)的 k-平均算 法所不能達到的。它可以運用到較大的數(shù)據(jù)庫中去,但它能 否運用到特大型復雜的數(shù)據(jù)庫中進行聚類數(shù)據(jù)挖掘還有待進 一步的研究。參考文獻1 史忠植 . 知識發(fā)現(xiàn) M. 北京 : 清華大學出版社 , 2002.2 Han Jiawei, Kamber M. Data Mining: Concepts and TechniquesM. San Francisco: Morgan Kaufmann Publishers, 2000.3 Grabmeier J, Rud

19、olph A. Techniques of Cluster Algorithms in Data MiningJ. Data Mining and Knowledge Discovery, 2002, 6(4: 303. 4 Jain A K, Murty M N, Flynn P J. Data Clustering: A ReviewJ. ACM Computing Surveys, 1999, 31(3: 264-323.5 MacQueen J. Some Methods for Classification and Analysis of Multivariate Observati

20、onsC/Proc. of the 5th Berkeley Symp. on Math. Statist. 1967: 281-297.6 Kaufman J, Rousseeuw P J. Finding Groups in Data: An Introduction to Cluster AnalysisM. New York: John Wiley & Sons, 1990. 7 Ester M, Kriegel H P, Sander J, et al. A Density-based Algorithm for Discovering Clusters in Large S

21、patial DatabasesC/Proc. of 1996 Intl. Conf. on Knowledge Discovery and Data Mining, Portland, OR. 1996-08: 226-231.(下轉(zhuǎn)第 209頁 209 圖 3 lena原圖 圖 4 星球表面 圖 5 對圖 3處理后的結(jié)果 =0.64圖 6 對圖 3處理后的結(jié)果 = 1.64圖 7 對圖 3處理后的結(jié)果 =1.84圖 8 對圖 4處理后的結(jié)果 =0.84圖 9 對圖 4處理后的結(jié)果 =1.64圖 10 對圖 4處理后的結(jié)果 =1.843 結(jié)論圖 11是利用 photoshop7.0對圖 3生

22、成的一幅魚眼圖像, 對比圖 5圖 7、圖 11可以看出,魚眼圖像在表達整體聯(lián)系 方面的確具有較好的效果,但其缺點也是很顯然的。 圖 11 由圖 3生成的魚眼圖像而由本文方法生成的圖像序列 (圖 5圖 7 不僅對用戶感 興趣的焦點圖像給予詳細的刻畫,同時對焦點圖像之間的聯(lián) 系作出合適的表達,這種表達是以適合人們的記憶特點為基 礎的。將本文方法的相關程序在 VC+6.0環(huán)境下運行,也獲 得了成功。程序代碼沒有進行優(yōu)化,以上圖像序列的生成時 間分別為 0.22s 和 0.26s ,優(yōu)化后的結(jié)果能夠滿足用戶實時性 瀏覽的要求。實驗表明,本方法顯示的圖像序列效果是良 好的。參考文獻1 Johnson B

23、, Shneiderman B. Treemaps: A Space-filling Approach to the Visualization of Hierarchical Information StructuresC/Proc. ofthe 2nd Intl. IEEE Visualization Conf. 1991-10.2 Zhang X, Furnas G W. MCVEs: Using Cross Scale Collaboration to Support User Interaction with Multiscal StructuresJ. Teleopera- tor

24、s and Virtual Environments, 2005, 14(1: 31-46.3 Roberston G G, Mackinlay J D, Card S K. Cone Trees: Animated 3D Visualizations of Hierarchical InformationC/Proc. of ACM Conference on Human Factors in Computing Systems. 1991: 189. 4 Ziegler J, Kunz C, Botsch V. Matrix Browser Visualizing and Explorin

25、g Large Networked Information SpacesC/Proc. of Extended Abstracts of the International Conference on Computer Human Interaction. 2002: 602-603.5 Ham F V. Using Multi-level Call Matrices in Large ProjectsC/Proc. of IEEE Symp. Information Visualization Conference. 2003: 227-232. 6 Furnas G F. Generali

26、sed Fisheye ViewsC/ Proc. of CHI86 Human Factors in Computing Systems. 1986: 16-23.7 Schaffer D, Zao Z, Greenberg S, et al. Navigating Hierarchically Clustered Networks Through Fisheye and Full-zoom MethodsJ. Transaction on Computer Human Interaction, 1996, 3(2: 162-188. 8賈云得 , 呂宏靜 , 劉萬春 . 魚眼變形立體圖像恢

27、復稠密深度圖的方 法 J. 計算機學報 , 2000, 23(12: 1232-1234.9 Wijk J J V, Nuij W A A. Smooth and Efficient Zooming and PanningC/Proc. of IEEE Symp. Information Visualization Conference. 2003: 15-22.10 Igarashi T. Hinckley K. Speed-dependent Automatic Zooming forBrowsing Large DocumentsC/Proceedings of ACM Symposiu

28、m of User Interface Software and Technology. 2002: 139-148. 11 Bederson B B, Meyer J, Good L. Jazz: An Extensible Zoomable User Interface Graphics Tookit in JavaC/Proc. of the ACM Symp. on User Interface Software. 2000: 171-180.12 Bederson B B. Photo Mesa: A Zommable Image Browser UsingQuantum Treem

29、aps and BubblemapsC/Proceedings of Sym- posium of User Interface Software and Technology. 2001: 71-80. . 13楊立志 , 顧耀林 . 一種基于有理二次樣條曲線的圖像放大方法 J.計算機應用 , 2006, 26(5: 1061-1063.(上接第 2018 Ankerst M, Breuning M, Kriegel H P, et al. OPTICS: Ordering Points to Identify the Clustering StructureC/Proc. of 1999 ACM-SIGMOD Intl. Conf. on Management of Data, Philadelphi