優(yōu)化K-means的不平衡數(shù)據(jù)分類研究

王舒梵

（上海工程技術(shù)大學(xué)數(shù)理與統(tǒng)計(jì)學(xué)院 上海市 201600）

1 緒論

K-means 算法最早由Steinhaus 等人[1]提出，是一種經(jīng)典的基于數(shù)據(jù)分類的聚類算法。該算法簡(jiǎn)單易懂、收斂速度快、執(zhí)行效率高，因此被研究學(xué)者們廣泛使用。但是傳統(tǒng)的K-means 算法不易受聚類數(shù)K 的影響，且對(duì)初始聚類中心的選擇依賴性較大，所以，本文將優(yōu)化K-means 算法實(shí)現(xiàn)不平衡數(shù)據(jù)分類的研究。

優(yōu)化K-means 的不平衡數(shù)據(jù)分類算法，考慮到不平衡數(shù)據(jù)中數(shù)據(jù)不精確、過(guò)擬合、誤差與方差大等問(wèn)題，結(jié)合K-means 算法中不平衡數(shù)據(jù)不易受聚類數(shù)K 的影響，且對(duì)初始聚類中心的選擇依賴性較大等問(wèn)題，本文提出了一種優(yōu)化K-means 算法的不平衡數(shù)據(jù)集分類算法，采用基于最大距離選擇法實(shí)現(xiàn)聚類中心的查找，將不平衡數(shù)據(jù)集劃分為測(cè)試集與訓(xùn)練集，多次調(diào)用優(yōu)化的K-means 算法，得到不平衡數(shù)據(jù)的模型，進(jìn)而得到不平衡數(shù)據(jù)集合的分類結(jié)果；通過(guò)性能分析，確定該算法的聚類準(zhǔn)確性更高且分類結(jié)果更加的精確與穩(wěn)定。

2 關(guān)鍵技術(shù)概述

2.1 不平衡數(shù)據(jù)分類

不平衡數(shù)據(jù)分類的研究，集中于多數(shù)類領(lǐng)域，常見(jiàn)算法主要用以提高不平衡數(shù)據(jù)集的性能，典型有代價(jià)敏感學(xué)習(xí)算法、單類學(xué)習(xí)算法以及集成學(xué)習(xí)算法。

代價(jià)敏感學(xué)習(xí)算法是指通過(guò)構(gòu)建錯(cuò)分代價(jià)最高的類，以總代價(jià)最小為實(shí)現(xiàn)目標(biāo)，實(shí)現(xiàn)不平衡數(shù)據(jù)分類的研究。典型算法有AdaCost[2]算法，該算法在AdaBoost 算法的基礎(chǔ)上通過(guò)代價(jià)敏感學(xué)習(xí)模型，修改權(quán)重值，完成策略的更新，調(diào)節(jié)不平衡數(shù)據(jù)分類，減少代價(jià)之；而MetaCost[3]是在傳統(tǒng)的分類模型上轉(zhuǎn)化代價(jià)敏感模型，采用傳統(tǒng)分類模型訓(xùn)練數(shù)據(jù)集合，對(duì)每個(gè)樣本計(jì)算，以確定不同的類別內(nèi)容，以最小代價(jià)類作為其標(biāo)簽，由修改后的訓(xùn)練集合再次學(xué)習(xí)分類模型；Cao 等[4]采用Stacking 集成方法，提出一種基于特征逆映射的成本敏感型堆疊學(xué)習(xí)（IMCStacking），來(lái)分類不平衡數(shù)據(jù)，解決分類研究中的問(wèn)題。但是，代價(jià)敏感學(xué)習(xí)算法在數(shù)據(jù)搜索的過(guò)程中，消耗大量的時(shí)間空間值，并且僅僅以數(shù)據(jù)集中樣本量大小或者樣本間的比例為誤分類代價(jià)，無(wú)法得到精確地分類效果。

圖1：算法流程圖

圖2：不平衡數(shù)據(jù)分類研究的框架

單類學(xué)習(xí)算法通過(guò)分類與訓(xùn)練單個(gè)類別的樣本集合，完成不平衡數(shù)據(jù)的分類研究，在不平衡數(shù)據(jù)集合中，通過(guò)只訓(xùn)練多數(shù)類樣本能夠得到一個(gè)模型，進(jìn)而從測(cè)試樣本中識(shí)別出多數(shù)類，典型的單類學(xué)習(xí)算法有單類支持向量機(jī)（One-Class SVM）、支持向量數(shù)據(jù)描述（Support Vector Data Description，SVDD）以及其他的改進(jìn)算法等[5-7]。Sarah 等[8]針對(duì)于高維度空間數(shù)據(jù)分類低效率的問(wèn)題，提出了一種混合模型，即訓(xùn)練無(wú)監(jiān)督的DBN，以提取不平衡數(shù)據(jù)的通用特征值，通過(guò)這些數(shù)值訓(xùn)練與分類單類支持向量機(jī)，該模型具有可伸縮性和較高的計(jì)算效率。但是，因?yàn)閱晤悓W(xué)習(xí)算法通常只能對(duì)單一類別的樣本值進(jìn)行訓(xùn)練而只能在一定程度上減少時(shí)間開(kāi)銷，進(jìn)而只適用于少數(shù)類樣本，容易導(dǎo)致過(guò)擬合等問(wèn)題。

圖3：性能對(duì)比

集成學(xué)習(xí)算法通過(guò)組合多個(gè)個(gè)體學(xué)習(xí)器來(lái)完成學(xué)習(xí)模型的構(gòu)建，能夠獲取比單一學(xué)習(xí)器更加優(yōu)越的模型效果。典型算法有Bagging、Boosting、Stacking 等[9-11]是集成學(xué)習(xí)中典型的三類方法，其中，Bagging 中訓(xùn)練子集相互獨(dú)立，能夠有效降低個(gè)體分類器的方差，減少了泛化誤差，且分類器并行的生成能夠提高運(yùn)行效率;但是，該算法只適合小數(shù)據(jù)集。Boosting 算法是一種將弱學(xué)習(xí)器轉(zhuǎn)換成強(qiáng)學(xué)習(xí)器的迭代方法，但是，該算法在提高個(gè)體學(xué)習(xí)器效果的同時(shí)會(huì)產(chǎn)生過(guò)擬合問(wèn)題，且各個(gè)體學(xué)習(xí)器順序生成會(huì)導(dǎo)致訓(xùn)練效率相對(duì)較差。Stacking 算法通過(guò)對(duì)多個(gè)個(gè)體學(xué)習(xí)器的訓(xùn)練與分類，將輸出值作為輸入完成學(xué)習(xí)模型的訓(xùn)練，得到最終的輸出，該算法減少了模型的泛化誤差，但容易過(guò)擬合。

考慮到上述問(wèn)題，本文將采用K-means 算法來(lái)實(shí)現(xiàn)不平衡數(shù)據(jù)集分類的研究。

2.2 K-means技術(shù)

將K-means 算法應(yīng)用于不平衡數(shù)據(jù)集分類中，能夠避免傳統(tǒng)不平衡數(shù)據(jù)分類中存在的數(shù)據(jù)不精確、過(guò)擬合、誤差與方差大等問(wèn)題。不平衡數(shù)據(jù)分類算法需要對(duì)訓(xùn)練集學(xué)習(xí)后，通過(guò)對(duì)未知數(shù)據(jù)的分類而得到數(shù)據(jù)集合的預(yù)測(cè)值，K-means[12]聚類算法是一種無(wú)監(jiān)督學(xué)習(xí)框架，旨在將數(shù)據(jù)中屬性相似的示例集中在一起，而不需要對(duì)訓(xùn)練集進(jìn)行精確地學(xué)習(xí)。該算法是將給定的數(shù)據(jù)集劃分為K 個(gè)類別主要步驟如下：

（1）從數(shù)據(jù)集X 隨機(jī)選取K 個(gè)對(duì)象，作為K 個(gè)類別的初始聚類中心

（2）分別計(jì)算數(shù)據(jù)集合中每個(gè)元素同聚類中心的歐式距離，依據(jù)最近鄰原則，將不同的元素劃分到相應(yīng)類別；

（3）求解每個(gè)類別中元素的均值，并且作為新的聚類中心，重復(fù)上述步驟；

（4）指導(dǎo)聚類中心不再變化，停止循環(huán)。

其中，歐式距離是指兩個(gè)樣本值在歐式空間中的直線距離，xi與xj 在m 維空間中，歐式距離的計(jì)算公式如下：

3 基于優(yōu)化K-means的不平衡數(shù)據(jù)分類算法

3.1 優(yōu)化的K-means算法

針對(duì)于傳統(tǒng)K-means 算法中不平衡數(shù)據(jù)不易受聚類數(shù)K 的影響，且對(duì)初始聚類中心的選擇依賴性較大等問(wèn)題，本文提出基于最大距離選擇法實(shí)現(xiàn)聚類中心的查找。首先，輸入不平衡數(shù)據(jù)與聚類數(shù)目K，求解歐式距離，不斷尋找最值，采用趨近法尋找聚類中心，結(jié)合數(shù)據(jù)的收斂程度，最終確定不平衡數(shù)據(jù)集合中的聚類中心。找到多個(gè)不同的聚類中心后，即確定了不平衡數(shù)據(jù)集合不同類別的中心數(shù)據(jù)，將趨近與不同聚類中心的數(shù)據(jù)自動(dòng)話費(fèi)為一個(gè)區(qū)間，完成不平衡數(shù)據(jù)的分類處理。

核心算法流程，如圖1所示。

3.2 基于優(yōu)化K-means算法的不平衡數(shù)據(jù)分類

表1：實(shí)驗(yàn)配置

表2：運(yùn)行時(shí)間對(duì)比（單位：ms）

不平衡數(shù)據(jù)集合能夠劃分為訓(xùn)練集合與測(cè)試集量部分，其中，訓(xùn)練集同意訓(xùn)練分類模型，測(cè)試集用以測(cè)試模型的性能。因?yàn)橛?xùn)練集為不平衡數(shù)據(jù)集合，因此需要優(yōu)化的K-means 算法來(lái)降低不平衡性，之后，通過(guò)測(cè)試集完成對(duì)數(shù)據(jù)集的測(cè)試與分類處理，得到不平衡數(shù)據(jù)的分類處理結(jié)果。整體框架，如圖2所示。

通過(guò)多次使用優(yōu)化的K-means 算法實(shí)現(xiàn)多個(gè)訓(xùn)練集與多個(gè)測(cè)試集，最終得到分類模型，進(jìn)而得到不平衡數(shù)據(jù)集合的分類結(jié)果。

4 性能分析

為了驗(yàn)證本文算法的性能，采用隨機(jī)生成的人工數(shù)據(jù)集，代替不平衡數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)與測(cè)試。實(shí)驗(yàn)配置如表1所示。

隨機(jī)選取1000 條數(shù)據(jù)代替不平衡數(shù)據(jù)集合，每條數(shù)據(jù)屬性假設(shè)有兩個(gè)，通過(guò)對(duì)比傳統(tǒng)K-means 的不平衡數(shù)據(jù)分類算法與本文算法，來(lái)驗(yàn)證本文算法的聚類準(zhǔn)確性更高且分類結(jié)果更加的精確與穩(wěn)定。對(duì)比結(jié)果，如圖3所示。

由圖可知，圖（a）中傳統(tǒng)K-means 算法的聚類結(jié)果較為集中，并且出現(xiàn)了離群點(diǎn)的問(wèn)題；而本文算法則沒(méi)有離群點(diǎn)作為聚類中心的問(wèn)題，進(jìn)而保證了聚類的準(zhǔn)確性，為分類結(jié)果的精確性與穩(wěn)定性奠定了理論基礎(chǔ)。

針對(duì)于結(jié)果的精確度與穩(wěn)定性，本文采用優(yōu)化的K-means 算法來(lái)反復(fù)迭代訓(xùn)練集與測(cè)試集，進(jìn)而得到更加精確與穩(wěn)定的測(cè)試結(jié)果。而針對(duì)于時(shí)間復(fù)雜度，時(shí)間換取精確度的方法來(lái)完善。通過(guò)文獻(xiàn)資料的查閱得知，傳統(tǒng)K-means 下不平衡數(shù)據(jù)分類的時(shí)間復(fù)雜度為其中，n 為聚類樣本個(gè)數(shù)，k 為類別數(shù)量，T 為聚類中心的迭代次數(shù)。而本文算法的時(shí)間復(fù)雜度，計(jì)算結(jié)果為其中t 為本文算法的迭代次數(shù)。當(dāng)即時(shí)，本文算法消耗的時(shí)間小于傳統(tǒng)K-means 算法用于不平衡數(shù)據(jù)分類的時(shí)間，而由于n 為聚類樣本個(gè)數(shù)可知，恒成立。以A、B、C 表示分類結(jié)果為例，算法的運(yùn)行時(shí)間，如表2所示。由表可知，本文算法的運(yùn)行時(shí)間短于傳統(tǒng)的K-means 算法。因此，本文算法在具有更精確與穩(wěn)定的分類結(jié)果的同時(shí)，消耗更短的時(shí)間。

綜上所述，在不平衡數(shù)據(jù)分類研究領(lǐng)域，本文算法優(yōu)于傳統(tǒng)的K-means 算法。

5 總結(jié)

本文在不平衡數(shù)據(jù)分類的基礎(chǔ)上，采用優(yōu)化的K-means 算法，來(lái)解決數(shù)據(jù)分類不精確、過(guò)擬合等問(wèn)題，最后通過(guò)性能分析，確定了算法的良好可用性。