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

王穎 吳觀茂

摘?要：提出一種引入全局算法的小批量K-means.算法應(yīng)用全局搜索算法，解決在大數(shù)據(jù)情況下運(yùn)算耗時(shí)問題和傳統(tǒng)K-means對(duì)初始中心點(diǎn)敏感的問題.實(shí)驗(yàn)結(jié)果表明，該方法在獲得最佳結(jié)果的前提下可以節(jié)省大量的計(jì)算時(shí)間.

關(guān)鍵詞：數(shù)據(jù)挖掘;全局搜索;K-means算法;小批量

[中圖分類號(hào)]TP301.6?[文獻(xiàn)標(biāo)志碼]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

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

1?改進(jìn)Mini?Batch?K-means算法

Mini?Batch?K-means算法[14]使用小批量樣本做傳統(tǒng)的K-means，每次訓(xùn)練算法提取不同的數(shù)據(jù)子集，避免樣本量太大時(shí)的計(jì)算難題，目標(biāo)函數(shù)也能得到優(yōu)化.算法步驟：第一步，從數(shù)據(jù)集中隨機(jī)提取一些數(shù)據(jù)以形成小批量并將它們分配到最近的質(zhì)心;第二步，重新計(jì)算每批小數(shù)據(jù)的質(zhì)心，直到質(zhì)心穩(wěn)定或達(dá)到指定的迭代次數(shù)，停止計(jì)算.

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

參考文獻(xiàn)

[1]蔡春華，趙杰，宋麗.?基于隨機(jī)投影的隱私保護(hù)分布式聚類算法研究[J].牡丹江師范學(xué)院學(xué)報(bào)：自然科學(xué)版，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

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

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