引入全局算法的小批量K-Means

王穎 吳觀茂

摘?要：提出一種引入全局算法的小批量K-means.算法應用全局搜索算法，解決在大數據情況下運算耗時問題和傳統K-means對初始中心點敏感的問題.實驗結果表明，該方法在獲得最佳結果的前提下可以節省大量的計算時間.

關鍵詞：數據挖掘;全局搜索;K-means算法;小批量

[中圖分類號]TP301.6?[文獻標志碼]A

Mini?Batch?K-Means?with?Global?Algorithm

WANG?Ying，WU?Guanmao

（Department?of?Computer?Science?and?Engineering，Anhui?University?of?Scienceand?Technology，Huainan??232001，China）

Abstract：A?small?batch?K-means?with?global?algorithm?is?proposed?Global?search?algorithm?is?applied?to?solve?the?problem?of?time-consuming?operation?in?the?case?of?big?data?and?the?sensitivity?of?traditional?K-means?to?the?initial?center?point.The?experimental?results?show?that?this?method?can?save?a?lot?of?calculation?time?on?the?premise?of?obtaining?the?best?results.

Key?words：data?mining;global?search;K-means?algorithm;mini?batch

數據挖掘是透過數據表面發現掩藏的規律性.聚類算法是通過目標函數優化的數據集X={?x1，x2…xn?}，C={c1，c2…cn}，目標函數就是最小化每個簇的平方誤差之和（SSE），SSE=（C）=∑ki=1∑x∈cidis（x，mean（ci））2.N個對象劃分為k個非空集合的方式可以由第二種斯特林數給出：φ（N，K）=1K！∑（-1）K-iKiiN，可以近似為KNK！.完全枚舉出所有可能的聚類以確定全局最小SSE（C）在計算上顯然是不可行的，所以誕生了很多方法求上述問題的近似解.K-means算法因為簡單易行性被廣泛應用，但因利用歐氏距離平方、異常點和噪聲容易影響聚類結果，很容易陷入局部最小[1]，不同的初始中心點會產生不同的聚類結果，具有很大的不穩定性，為此研究人員提出了一系列初始化中心點的方法.Likas，Vlassis，Verbeek[2]提出一種通過全局搜索所有數據來動態添加聚類中心的方法，每個階段添加一個新的聚類中心點，不依賴初始參數.Arthur，?Vassilvitskii[3]提出一種基于簡單概率播種技術的初始化過程，先選擇一個數據點作為初始中心點，然后計算每個數據到該中心點的距離，從而計算每個其他數據點被選為下一個中心點的概率.Bahman[4]等人給出更簡明的方案，每次不用遍歷全部樣本而只需遍歷O（k）個樣本，5次重復取樣即可.MarcoCapó[5]等人提出了一種有效逼近K-means的聚類方法，通過分區，在數量較少的子集上遞歸的應用K-means的加權版本.Shyr-Shen[6]等人提出兩種算法tri-level?K-means和bi-layer?K-means算法，類似多次分區運用K-means算法，解決K-means對初始點敏感問題.筆者提出一種更加準確和快速優化K-means的算法，在Mini?Batch?K-means的早期階段引入全局算法，提高聚類效率，保證聚類的準確性.

1?改進Mini?Batch?K-means算法

Mini?Batch?K-means算法[14]使用小批量樣本做傳統的K-means，每次訓練算法提取不同的數據子集，避免樣本量太大時的計算難題，目標函數也能得到優化.算法步驟：第一步，從數據集中隨機提取一些數據以形成小批量并將它們分配到最近的質心;第二步，重新計算每批小數據的質心，直到質心穩定或達到指定的迭代次數，停止計算.

改進Mini?Batch?K-means中最后將多組結果取平均值作為最終結果的方式，將每次的結果再次聚類.現在假設隨機抽樣J次，每次得到K個中心點，最后得到J*K個中心點，將這些J*K個中心點重新聚類的結果作為最終結果.本文讓J=4，K=3，即隨機取樣4次，每次計算出3個中心點，最后將這12個中心點重新聚類成3個最終中心點.簡單圖示見圖1.從圖1能很直觀的看出改進后的Mini?Batch?K-means與之前的區別，即使前期離群點會造成影響，最后再次聚類會將該影響降到最低.

參考文獻

[1]蔡春華，趙杰，宋麗.?基于隨機投影的隱私保護分布式聚類算法研究[J].牡丹江師范學院學報：自然科學版，2014（3）：1-3.

[2]A.Likas，N.A.Vlassis，J.J.Verbeek.The?global?K-means?clustering?algorithm[J].Pattern?Recognit，2003，36（2）：451-461.

[3]D.Arthur，S.Vassilvitskii，K-means++：the?advantages?of?careful?seeding[C].Proceedings?of?the?Eighteenth?Annual?ACM-SIAM?Symposium?on?Discrete?Algorithms，New?Orleans，Louisiana，USA，January?7-9，2007.

[4]Bahman?Bahmani，Benjamin?Mosesey，Andrea?Vattani，Ravi?Kumar，Sergei?Vassilvitskii.Scalable?K-means++[J].Proceedings?of?the?SLDB?Endowment，2012，2（5）：622-633.

[5]AritzPéreza，Jose?A.Lozanoab.An?efficient?approximation?to?the?K-means?clustering?for?massive?data[J].Knowledge-Based?Systems，2017，2（1）：56-69.

[6]Shyr-Shen?Yua，Shao-Wei?Chua，Chuin-Mu?Wangb，Yung-Kuan?Chanc，Ting-Cheng?Changd.Two?improved?K-means?algorithms[J].Applied?Soft?Computing，2018，68（13）：744-755.

[7]A.Likas，N.A.Vlassis，J.J.Verbeek.The?global?K-means?clustering?algorithm[J].Pattern?Recognit，2003，36（2）?：451-461.

編輯：琳莉

收稿日期：2019-12-10

基金項目：安徽省自然科學基金面上項目（1908085MF189）;安徽高校拔尖人才培育項目（gxbjZD15）

作者簡介：王穎（1995-），女，安徽池州人.碩士，主要從事數據挖掘研究;吳觀茂（1971-），男，安徽淮南人.教授，主要從事數據庫和數據挖掘研究.