一種改進的半監(jiān)督k均值算法研究
2019-11-03 13:11吳湘華曹麗君
電腦知識與技術 2019年24期
吳湘華 曹麗君
（湖南城市學院，湖南 益陽 413000）
摘要：初始聚類中心的選擇對k均值聚類算法效率影響比較大，半監(jiān)督k均值算法就是將標記數(shù)據(jù)應用于k均值聚類算法中，標記數(shù)據(jù)雖然具有非常強的導向性，但也可能存在異常的情況，這時候，聚類算法效率會變得很差。本文提出改進的半監(jiān)督k均值算法，先處理異常標記數(shù)據(jù)，并結合一定方法選取的初始聚類中心，得到新的初始聚類中心。改進的算法迭代次數(shù)明顯下降，算法效率明顯提高。
關鍵詞： 初始聚類中心;k均值;半監(jiān)督;標記數(shù)據(jù);迭代次數(shù)
中圖分類號：TP319? ? ? ? 文獻標識碼：A
文章編號：1009-3044（2019）24-0016-02
開放科學（資源服務）標識碼（OSID）：
聚類分析是數(shù)據(jù)挖掘領域一個重要的分支，在國內(nèi)外得到了廣泛的研究與應用。其中，k均值聚類算法[1]是最經(jīng)典的算法之一，該算法一般采取某種方法選取k個初始聚類中心，將每個樣本聚類到距離最短的簇中，并通過不斷迭代，使整體目標函數(shù)達到最優(yōu)。k均值算法具有原理簡單、容易實現(xiàn)、效率高、伸縮性好等優(yōu)點，其缺點主要有k值一般需要人為指定，對初始聚類中心依賴性強，結果有時候會出現(xiàn)局部最優(yōu)等。半監(jiān)督學習是將無監(jiān)督學習和監(jiān)督學習結合起來的一種方法，半監(jiān)督k均值算法[2]就是將少量的標記數(shù)據(jù)應用于k均值聚類過程的算法。
1? 半監(jiān)督k均值及實驗分析
1.1 半監(jiān)督k均值算法描述
聚類分析是將數(shù)據(jù)等對象的集合按照相似的原則分成若干個簇的過程，屬于無監(jiān)督學習。半監(jiān)督聚類分析是則是綜合運用少量標記數(shù)據(jù)[3]和大量未標記數(shù)據(jù)，將少量“昂貴的”標記數(shù)據(jù)和大量“廉價的”未標記數(shù)據(jù)有機地結合在一起，避免了數(shù)據(jù)資源的極大浪費[4];從而從很大程度上避免了無監(jiān)督聚類過程中的盲目性[5]，提高算法的效率，減少運行時間，提升最終簇類的質(zhì)量。半監(jiān)督k均值算法就是在k均值聚類分析過程中引用少量的標記數(shù)據(jù)，從標記數(shù)據(jù)中采用一定的方法選取初始聚類中心，然后再使用k均值迭代算法進行聚類。
1.2 半監(jiān)督k均值算法實驗及分析
對 dataset1數(shù)據(jù)集中的數(shù)據(jù)進行聚類分析，該數(shù)據(jù)集是一組描述有關身高、體重和性別的數(shù)據(jù)集，k值為2，使用傳統(tǒng)k均值聚類時，如果隨機選取初始聚類中心，最小迭代次數(shù)為2，最大迭代次數(shù)為13，平均迭代次數(shù)為6.6。使用半監(jiān)督k均值聚類算法對dataset1數(shù)據(jù)集中所有數(shù)據(jù)進行聚類，實驗如下：
1.2.1 標記數(shù)據(jù)聚類后正常的情況
標記數(shù)據(jù)集為：A={d9，d48}?class1，B={d24，d79}?class2，用
從上表可以得出，在標記數(shù)據(jù)集合中分別隨機選取初始聚類中心的平均迭代次數(shù)3.5。用|A|和|B|分別表示集合A和集合B均值，如果以|A|和|B|分別作為聚類的初始中心，迭代次數(shù)為3。
1.2.2 標記數(shù)據(jù)聚類后異常的情況
標記數(shù)據(jù)集為：A={d9，d48}?class1，B={d24，d1}?class2，從集合A和B中分別隨機選取兩個聚類的初始聚類中心，然后進行半監(jiān)督k均值聚類，分別有4種情形，聚類后，集合A和集合B中的數(shù)據(jù)d1在class1中，集合B中的數(shù)據(jù)d24在class2中，此時出現(xiàn)了標記數(shù)據(jù)聚類后異常的情況。選取不同初始聚類中心時的迭代次數(shù)，如下表1：
從上表可以得出，在標記數(shù)據(jù)集合中分別隨機選取初始聚類中心的平均迭代次數(shù)5.8。用|A|和|B|分別表示集合A和集合B均值，如果以|A|和|B|分別作為聚類的初始中心，迭代次數(shù)為7。
1.2.3 實驗結果分析
聚類后，如果標記數(shù)據(jù)沒有出現(xiàn)在別的簇中，無論是從標記數(shù)據(jù)中隨機選取初始聚類中心，還是使用標記數(shù)據(jù)的均值作為初始聚類中心進行半監(jiān)督k均值聚類，其迭代次數(shù)明顯小于傳統(tǒng)的k均值算法，而且使用均值作為初始聚類中心更加具有優(yōu)勢，因為標記數(shù)據(jù)對聚類具有很強的指導意義。聚類后，當標記數(shù)據(jù)到了別的簇中，不管是采用隨機選取初始聚類中的方法心，還是以標記數(shù)據(jù)的均值作為初始聚類中心，都會帶來很大負面的偏離，導致迭代次數(shù)大大增加，算法效率甚至劣于傳統(tǒng)的k均值算法。
2 半監(jiān)督k均值及實驗分析
2.1 半監(jiān)督k均值算法的改進
為了避免異常標記數(shù)據(jù)給聚類帶來的負面影響，在標記數(shù)據(jù)的指導下，選取合適的初始聚類中心。對半監(jiān)督k均值聚類算法做如下改進：（1）在原始數(shù)據(jù)集中隨機選取若干個數(shù)據(jù)構成數(shù)據(jù)集R，和標記數(shù)據(jù)集M一起構成一個子集N;（2）對子集N進行半監(jiān)督k均值聚類;（3）通過聚類后的簇，找出標記數(shù)據(jù)中有出現(xiàn)異常的數(shù)據(jù)，并在初始標記數(shù)據(jù)集中刪除，得到處理后的標記數(shù)據(jù)集M1;（4）在原始數(shù)據(jù)集中采用某種選擇初始聚類中心的方法（如基于點密度的方法）選取k個初始聚類中心，將這k個點分別置于M1中，得到M2，（5）以M2中各類點的均值作為初始聚類中心，對原始數(shù)據(jù)進行k均值聚類。
2.2 改進的半監(jiān)督k均值算法實驗及分析
對 dataset1數(shù)據(jù)集中的數(shù)據(jù)進行聚類分析，迭代次數(shù)對比如表3：
筆者同時對Glass、Ecoli、Irisdata和Rice等數(shù)據(jù)集進行實驗，發(fā)現(xiàn)改進的半監(jiān)督k均值算法更為有效，在選取初始聚類中心時，比傳統(tǒng)的k均值算法和半監(jiān)督k均值算法具有更強的針對性，引進并處理過后的標記數(shù)據(jù)，大大提高了算法的效率。
3 結束語
改進的半監(jiān)督k均值算法對標記數(shù)據(jù)進行處理，盡可能地避免異常標記數(shù)據(jù)給聚類帶來不良影響，同時考慮k均值聚類算法中確定優(yōu)質(zhì)初始聚類中心的經(jīng)驗，也將其作為標記數(shù)據(jù)，并將優(yōu)質(zhì)初始聚類中心也當作一個標記數(shù)據(jù)，由這兩類數(shù)據(jù)共同確定初始聚類中心，使得選取的初始聚類中心盡可能靠近聚類后的中心，提高算法的效率。
參考文獻：
[1] Agrawal R，et al. Database mining： A performance perspective [A].IEEE Transactions on knowledge and Data Engineering [C].1993， 5（6）： 914-925.
[2] 高瀅，劉大有，齊紅，等.一種半監(jiān)督K均值多關系數(shù)據(jù)聚類算法[J].軟件學報，2008（11）：2814-2821.
[3] Bates Matthew E，Keisler Jeffrey M，ZussblattNiels P， Plourde Kenton J，Wender Ben A，LinkovIgor.Corrigendum： Balancing research and funding using value of information and portfolio tools for nanomaterial risk Classification[J].Nature Nanotechnology，2016，11（4）：395-403.
[4] 劉方.數(shù)據(jù)挖掘中半監(jiān)督K-均值聚類算法的研究與改進碩士論文[D].吉林大學，2010.
[5] Zhi-Yong Li，Jiao-Hong Yi，Gai-GeWang.A New Swarm Intelligence Approach for Clustering Based on Krill Herd with Elitism Strategy[J].Algorithms，2015 ，18（4）：951-964.
【通聯(lián)編輯：朱寶貴】
