程鈴鈁,楊天鵬,陳黎飛

(1.福建農(nóng)林大學(xué) 金山學(xué)院, 福州 350002; 2. 福建師范大學(xué) 數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院,福州 350117) (*通信作者電子郵箱clf@fafu.edu.cn)

不平衡數(shù)據(jù)的軟子空間聚類算法

程鈴鈁1,楊天鵬2,陳黎飛2*

(1.福建農(nóng)林大學(xué) 金山學(xué)院, 福州 350002; 2. 福建師范大學(xué) 數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院,福州 350117) (*通信作者電子郵箱clf@fafu.edu.cn)

針對受均勻效應(yīng)的影響，當(dāng)前K-means型軟子空間算法不能有效聚類不平衡數(shù)據(jù)的問題，提出一種基于劃分的不平衡數(shù)據(jù)軟子空間聚類新算法。首先，提出一種雙加權(quán)方法，在賦予每個屬性一個特征權(quán)重的同時，賦予每個簇反映其重要性的一個簇類權(quán)重；其次，提出一種混合型數(shù)據(jù)的新距離度量，以平衡不同類型屬性及具有不同符號數(shù)目的類屬型屬性間的差異；第三，定義了基于雙加權(quán)方法的不平衡數(shù)據(jù)子空間聚類目標(biāo)優(yōu)化函數(shù)，給出了優(yōu)化簇類權(quán)重和特征權(quán)重的表達(dá)式。在實(shí)際應(yīng)用數(shù)據(jù)集上進(jìn)行了系列實(shí)驗(yàn)，結(jié)果表明，新算法使用的雙權(quán)重方法能夠?yàn)椴黄胶鈹?shù)據(jù)中的簇類學(xué)習(xí)更準(zhǔn)確的軟子空間；與現(xiàn)有的K-means型軟子空間算法相比，所提算法提高了不平衡數(shù)據(jù)的聚類精度，在其中的生物信息學(xué)數(shù)據(jù)上可以取得近50%的提升幅度。

軟子空間聚類;不平衡數(shù)據(jù);特征權(quán)重;簇類權(quán)重

0 引言

子空間聚類(subspace clustering)是數(shù)據(jù)挖掘諸多應(yīng)用領(lǐng)域中一種重要工具,它根據(jù)數(shù)據(jù)對象相似性進(jìn)行無監(jiān)督數(shù)據(jù)簇類劃分的同時,能夠識別和生成各簇類相關(guān)的特征(或?qū)傩?集合,組成類依賴(cluster-dependent)的子空間[1-2]。例如,聚類由患者各種生理指標(biāo)特征構(gòu)成的醫(yī)學(xué)診斷數(shù)據(jù)時,子空間算法依據(jù)生理指標(biāo)的差異將患者歸類到不同的疾病類型,同時輸出與這些疾病相關(guān)的重要生理指標(biāo)。鑒于這些實(shí)際應(yīng)用數(shù)據(jù)中簇類結(jié)構(gòu)的復(fù)雜性,子空間聚類已成為聚類研究和應(yīng)用中富有挑戰(zhàn)性的任務(wù)之一[1-5]。

根據(jù)子空間搜索策略的差異,現(xiàn)有子空間聚類算法大致可以分為兩種類型[1]:自下而上的和自上而下的方法。前者從一維子空間出發(fā),根據(jù)對象投影到子空間中的密度,迭代地搜索數(shù)據(jù)集中的稠密區(qū)域和它們的最大投影子空間;后者則從全空間出發(fā),為每個候選簇類計算其所在的最優(yōu)子空間[3-6]。本文著重于自上而下的子空間聚類方法,主要原因是該型方法較前者通常具有較低的時間復(fù)雜度且易于實(shí)現(xiàn)。實(shí)際上,當(dāng)前主要的此型算法都是以K-means[7]或K-modes[8-10]為基礎(chǔ)的,其基本思路是在原始算法基礎(chǔ)上增加一個步驟以計算各屬性的特征權(quán)重,由此構(gòu)造出目標(biāo)簇類的軟子空間(soft subspace)[3,5]。

眾所周知,K-means型算法傾向于輸出大小相同和密度相同的簇類集合,這個現(xiàn)象稱為“均勻效應(yīng)(uniform effect)”[11]。而許多實(shí)際應(yīng)用產(chǎn)生的數(shù)據(jù)通常是不平衡的,例如,在前述的醫(yī)學(xué)診斷數(shù)據(jù)中,正例集(某種疾病患者)往往樣本量較少,反例集對應(yīng)未患該疾病的就診者,樣本量相對較多;此外,正例集和反例集的“密度”(體現(xiàn)集合內(nèi)樣本間的相似性,彼此間越相似,則“密度”越高)通常也有很大的差異,正例集的樣本分布遵循相同的規(guī)律(即疾病模式),具有較高的密度。受均勻效應(yīng)的影響,當(dāng)前的子空間算法并不能有效聚類這樣的不平衡數(shù)據(jù)(imbalanced data)[12-14]。

針對上述問題,本文提出了“雙加權(quán)(bi-weighting)”方法,并以此為基礎(chǔ)定義了稱為BWIC(Bi-Weighting for Imbalanced data Clustering)的不平衡數(shù)據(jù)軟子空間聚類算法。雙加權(quán)方法賦予每個簇反映其重要性的一個權(quán)重,稱為簇權(quán)重(cluster-weight)；同時賦予每個屬性一個特征權(quán)重(feature-weight),衡量屬性與簇類之間的相關(guān)性。另一方面,實(shí)際數(shù)據(jù)通?；旌嫌袛?shù)值型(numeric)和類屬型 (categorical)等不同類型的屬性,而不同類屬型屬性的離散符號數(shù)目也可能差異很大,導(dǎo)致它們對兩種權(quán)重產(chǎn)生“不平衡”的貢獻(xiàn)。為此,本文另提出一種針對混合型數(shù)據(jù)的簇類權(quán)重和特征權(quán)重優(yōu)化計算方法。

1 相關(guān)工作

首先約定后文使用的記號。用DB表示由N個數(shù)據(jù)對象組成的待聚類數(shù)據(jù)集,數(shù)據(jù)對象(樣本)為D維向量x=(x1,x2,…,xD)T或y=(y1,y2,…,yD)T。給定聚類數(shù)K,子空間聚類算法的目的是將N個對象劃分為K個簇的集合C={c1,c2,…,ck,…,cK},同時確定這些簇所在的子空間,通常用特征權(quán)重的集合W表示。這里ck表示第k個簇,其包含的對象數(shù)記為|ck|。

若|ck|(k=1,2,…,K)有較大差異,則稱DB為不平衡數(shù)據(jù)集。不平衡數(shù)據(jù)的聚類分析乃數(shù)據(jù)挖掘領(lǐng)域的一個困難問題[11-14]。現(xiàn)有解決方法大致可分為兩類:數(shù)據(jù)預(yù)處理方法和多代表點(diǎn)方法,前者基于欠采樣或過采樣原理對不平衡數(shù)據(jù)進(jìn)行預(yù)處理,然后再使用傳統(tǒng)算法進(jìn)行聚類[13],后者用多個代表點(diǎn)表示不平衡數(shù)據(jù)中的一個簇,即用多個劃分子集表示其中的簇,再通過凝聚操作將劃分子集合并為“大”簇[14]。由于涉及采樣或凝聚操作,這些方法在實(shí)現(xiàn)子空間聚類方面存在困難。

現(xiàn)有的軟子空間聚類算法大多基于特征局部加權(quán)技術(shù)[1-6],即賦予每個簇ck的每個特征d一個權(quán)重ωkd,其實(shí)質(zhì)是定義特征加權(quán)的對象間距離度量,進(jìn)而在K-means聚類過程中學(xué)習(xí)這種度量,也就是為每個簇ck學(xué)習(xí)得到一個優(yōu)化的權(quán)重向量(ωk1,ωk2,…,ωkD)T。針對不同類型的屬性,已提出多種基于特征加權(quán)的距離度量。對于數(shù)值型屬性,對象x和y間的(平方)距離[3-4]通常定義為:

其中：β≠0為加權(quán)參數(shù)。相應(yīng)地,對于類屬型數(shù)據(jù),通常采用如下定義[5-6]:

(1)

其中：I(·)為指示函數(shù),I(true)=1和I(false)=0。

為優(yōu)化上述定義中的特征權(quán)重,通常需要引入約束條件ωk1+ωk2+…+ωkD=1。顯然,在這樣的歸一化約束下,特征權(quán)重分布并不能體現(xiàn)簇類之間的差異,降低了它們在類不平衡數(shù)據(jù)集上的聚類性能。此外,這些方法僅處理單一類型(數(shù)值型或類屬型)的數(shù)據(jù),數(shù)據(jù)集同時包含兩種類型的屬性時,如何平衡不同類型屬性的特征權(quán)重是這些方法需要解決的共同問題之一。為此,本文提出一種“平衡型”的新距離度量,用于不平衡混合型數(shù)據(jù)的聚類任務(wù)。

2 BWIC聚類

本章提出基于雙加權(quán)機(jī)制(含簇類加權(quán)和屬性加權(quán))的不平衡數(shù)據(jù)新聚類算法BWIC,以下首先定義屬性平衡的距離度量。

2.1 屬性平衡的距離度量

與相關(guān)研究一樣,新距離度量也基于“樸素”假設(shè)[2]:數(shù)據(jù)集的每個屬性d是統(tǒng)計獨(dú)立的。若屬性d為數(shù)值型,假設(shè)其數(shù)值均已規(guī)范化到區(qū)間[0,1];為類屬型時,記其符號集合為Sd,并用|Sd|表示其中的符號數(shù)。

通常,基于劃分的聚類算法(如K-means[7])旨在最小化簇內(nèi)對象相對于簇“中心”的平方誤差,它衡量了簇內(nèi)對象分布的分散程度(Scatter,以下簡記為Scat)。對簇ck的數(shù)值型屬性d,其平均分散度可以表示為:

(2)

性質(zhì)1 若屬性d為數(shù)值型且?x∈ck:xd∈[0,1],則

證畢。

式(2)第二行對分散度定義進(jìn)行了變換,其特點(diǎn)是不再依賴于簇“中心”,而根據(jù)樣本對之間的(平方)歐氏距離計算。由于類屬型數(shù)據(jù)的樣本均值沒有意義[5-6,8-10],該變換提供了計算類屬型簇類分散度的一個途徑:替換式(2)的歐氏距離為適用于類屬型屬性的度量,即可導(dǎo)出類屬型簇類分散度的計算式?；谑?1)所示的距離度量方式,類屬型屬性d上ck的分散度變換為:

(3)

其中:

表示符號s∈Sd在ck的屬性d上出現(xiàn)的頻率。式(3)的上下界如性質(zhì)2所示。

性質(zhì)2 若屬性d為類屬型,有

證明 當(dāng)屬性d僅含單一類別時,根據(jù)式(3),Scatnum(ck,d)=0,這是該屬性分散度取得的最小值;相應(yīng)地,當(dāng)屬性d上各符號均勻分布時,Scatnum(ck,d)取得最大值,此時,對任意符號s有fkd(s)=1/|Sd|,代入式(3),分散度計算為(1-1/|Sd|*|Sd|)/2=(|Sd|-1)/|Sd|/2。

證畢。

為平衡同一個簇中不同類型屬性上的分散度,需要將Scatnum(·,·)和Scatcat(·,·)變換到同一數(shù)值區(qū)間。根據(jù)性質(zhì)1和性質(zhì)2,若為Scatcat(·,·)乘上平衡系數(shù)

則可以變換到與Scatnum(·,·)相同的區(qū)間[0,1/4],由此,定義簇ck屬性d上的平均分散度為:

(4)

其中:

(5)

為對象x和y屬性d上的平衡型(平方)距離度量。

2.2 聚類目標(biāo)函數(shù)

為進(jìn)行軟子空間聚類,需要在式(4)基礎(chǔ)上定義特征加權(quán)的簇內(nèi)分散度。如前所述,在現(xiàn)有算法中,每個屬性d與一組特征權(quán)重ω1d,ω2d,…,ωkd,…,ωKd相關(guān)聯(lián),但是,受歸一化條件限制,權(quán)值并不能反映簇類間的差異。為此,針對類不平衡數(shù)據(jù)的特點(diǎn),將這樣的類依賴特征權(quán)重分解為兩個獨(dú)立的子權(quán)重,即

ωkd=hk×wd

(6)

其中：hk是ck的簇權(quán)重,其數(shù)值越大表示該簇相對于其他簇愈重要;wd為屬性d的全局特征權(quán)重。wd的數(shù)值衡量屬性對簇類相關(guān)性程度,滿足約束條件:

(7)

這種“雙加權(quán)”方法繼承了全局特征加權(quán)[4]和局部特征技術(shù)[3,5-6]的優(yōu)點(diǎn)：一方面,根據(jù)式(6),每個屬性d依然可以獲得K個局部特征權(quán)重ω1d,ω2d,…,ωKd,從效果上看,這等同于局部加權(quán)技術(shù)；另一方面,對于每個屬性d本身,它事實(shí)上只與單個權(quán)重wd相關(guān)聯(lián),這與全局加權(quán)方法的輸出是一致的,因而可用于全局特征選擇。根據(jù)上述定義,子空間聚類算法應(yīng)最小化以下目標(biāo)優(yōu)化函數(shù):

其中:W={wd|d=1,2,…,D}為待優(yōu)化的特征權(quán)重集合。由于簇權(quán)重與特征權(quán)重?zé)o關(guān),這里hk(k=1,2,…,K)并不是模型的參數(shù),而是通過式(8)估計:

(8)

根據(jù)式(8),若簇內(nèi)對象彼此之間很相似(從而其簇內(nèi)對象分布的平均分散度很小),則該簇將獲得較大的權(quán)重,起到抵消K-means型算法聚類不平衡數(shù)據(jù)集時“均勻效應(yīng)”的作用。

由于包含了特征權(quán)重W,J0(C,W)并不是一個凸函數(shù)。為此,借鑒文獻(xiàn)[15]方法,引入平滑函數(shù)wlnw使目標(biāo)函數(shù)更容易優(yōu)化。這樣,BWIC算法的目標(biāo)優(yōu)化函數(shù)變?yōu)?

這里使用了參數(shù)γ≠0控制函數(shù)的凸度。理想地,γ的取值應(yīng)使得聚類結(jié)果具有最高的質(zhì)量。常用聚類有效性內(nèi)部指標(biāo)來衡量聚類結(jié)果質(zhì)量,然而,現(xiàn)有指標(biāo)大多僅作用于數(shù)值型數(shù)據(jù)[16]。注意到式(5)定義了混合型屬性的對象間距離度量,一些基于對象間距離的指標(biāo),如著名的Silhouette指標(biāo)[17],可以容易地擴(kuò)展成為混合型數(shù)據(jù)聚類的指標(biāo)。具體地,定義指標(biāo)為:

(9)

2.3 聚類算法

給定數(shù)據(jù)集DB和K,BWIC算法需求解2.2節(jié)定義的帶約束的非線性優(yōu)化問題。應(yīng)用拉格朗日乘子法引入式(7)的約束條件,算法需最小的目標(biāo)函數(shù)轉(zhuǎn)換為:

(10)

第二個迭代步驟將W視為常數(shù),求令J取得最小值的C,這可以通過將每個對象x重新劃分到與其最相似的簇k來實(shí)現(xiàn):

(11)

基于上述優(yōu)化方法的聚類算法描述如下。

算法1 聚類算法BWIC。

輸入 數(shù)據(jù)集DB及聚類數(shù)K、參數(shù)γ。

輸出 簇集合C及權(quán)重集合H={h1,h2,…,hK}、特征權(quán)重集合W。

Begin

生成數(shù)據(jù)集初始劃分C,并初始化W中的每個屬性權(quán)重為1/D。

Repeat

根據(jù)式(8)計算各簇權(quán)重hk,k=1,2,…,K;

固定C,根據(jù)式(10)更新屬性權(quán)重W;

固定W,根據(jù)式(11)將每個對象x到劃分至最相似的簇,生成新的C。

UntilJ(C,W)的變化小于10-6

End

與現(xiàn)有K-means型軟子空間聚類算法[4,6]不同,BWIC沒有使用簇“中心”概念,是一種劃分算法。算法在步驟1生成初始劃分[3,5],首先隨機(jī)選擇K個對象為種子,然后根據(jù)式(5)計算每個對象與種子之間的距離,將所有對象劃分到最近的種子,以此組成數(shù)據(jù)集的初始劃分。在算法結(jié)構(gòu)上,BWIC與K-means型聚類算法相同,時間復(fù)雜度為O(T),其中T是算法執(zhí)行的迭代次數(shù)。

3 實(shí)驗(yàn)與分析

本章評估BWIC在一些實(shí)際不平衡數(shù)據(jù)集上的聚類性能,并與若干現(xiàn)有算法作比較。

3.1 數(shù)據(jù)集和實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)使用了六個常用的UCI數(shù)據(jù)集,如表1所示。其中的Heart(心臟疾病數(shù)據(jù))、Credit(澳大利亞信用卡數(shù)據(jù))和Hypothyroid(甲狀腺功能低下者數(shù)據(jù))是混合了數(shù)值型和類屬型屬性的數(shù)據(jù),剩下的三個數(shù)據(jù)集僅包含類屬型屬性,用于驗(yàn)證各種算法聚類復(fù)雜類型數(shù)據(jù)的性能。數(shù)據(jù)中的所有數(shù)值型屬性都預(yù)先作了[0,1]規(guī)范化處理。

這些數(shù)據(jù)包含的樣本都具有“不平衡”的特點(diǎn),例如,Splice數(shù)據(jù)集中的每個對象是60個核苷酸序列(位點(diǎn)編號從-30到+30),分為EI、IE和Neither三組,對象數(shù)分別為767、768和1 655;Hypothyroid數(shù)據(jù)也分為三組，分別用Normal、Hyperfunction和Subnormal表示,最大的組包含3 488個樣本,最小的只有93個對象;Soybean數(shù)據(jù)中有三組包含10個樣本,但第四組有17個樣本,用D1～D4表示。其他三個數(shù)據(jù)集中的各組樣本數(shù)盡管比較接近,但具有明顯的“負(fù)例”和“正例”區(qū)別,其中,Heart數(shù)據(jù)集分為“Absence(無心臟疾病)”和“Presence(有心臟疾病)”,Mushroom分為“Edible(可食用蘑菇)”和“Poisonous(有毒蘑菇)”,而Credit中的樣本可歸為“Rejected(被拒絕的申請者)”和“Approved(通過申請者)”兩類。

表1 實(shí)驗(yàn)使用的實(shí)際數(shù)據(jù)集

為評價類不平衡數(shù)據(jù)集的聚類性能,使用了兩種常用于分類任務(wù)性能評價的外部準(zhǔn)則:MacroF1和MicroF1,前者著重結(jié)果中稀有類的評價,而后者反映普通類的劃分結(jié)果質(zhì)量。二者都基于F1度量,對于簇k,其定義[2]為:

其中:πk是數(shù)據(jù)集中與ck對應(yīng)的真實(shí)類別；Pr(πk,ck)=Mk/|ck|表示πk的劃分精度(precision)；Re(πk,ck)=Mk/|πk|為召回率(recall)，Mk是Ck和πk中共現(xiàn)的對象數(shù)。MacroF1和MicroF1的數(shù)值越大,表明算法的聚類性能越好。

3.2 聚類結(jié)果

為分析BWIC算法輸出的聚類結(jié)果質(zhì)量與參數(shù)γ之間的關(guān)系,設(shè)置區(qū)間[-8,8]內(nèi)不同的γ值(取增量0.5,但不包括0),調(diào)用BWIC算法聚類每個數(shù)據(jù)集各20次,分別根據(jù)式(9)計算反映結(jié)果質(zhì)量的Silhouette值,再計算平均的Silhouette值,如圖1所示。由圖1可知,每個數(shù)據(jù)集上對應(yīng)最高聚類質(zhì)量的參數(shù)值分別是γ=-2(Heart)、-3.5(Mushroom)、-4(Credit)、4.5(Splice)、8(Hypothyroid)和4.5(Soybean)。圖1還顯示,在類分布(指樣本數(shù))較為平衡的數(shù)據(jù)集上,隨γ的變化,BWIC算法的性能較為魯棒;在Hypothyroid和Soybean這兩個類樣本數(shù)差異較大的數(shù)據(jù)集上,BWIC的性能受γ值影響較大,但隨著γ值的增長,聚類質(zhì)量趨于穩(wěn)定。

圖1 六個數(shù)據(jù)集上BWIC算法參數(shù)與聚類質(zhì)量間的關(guān)系

表2匯總了六個數(shù)據(jù)集上不同算法的平均聚類結(jié)果。在這組實(shí)驗(yàn)中,每種算法聚類各數(shù)據(jù)集100次,計算平均MacroF1和MicroF1指標(biāo)值,并以“平均值±1標(biāo)準(zhǔn)差”的形式報告。BWIC算法的參數(shù)取圖1顯示的對應(yīng)最大Silhouette的γ值。為公平比較,所有算法使用了相同的初始聚類中心(對于BWIC,初始中心用于生成初始的數(shù)據(jù)集劃分,見算法1)。每個數(shù)據(jù)集上最高的評價指標(biāo)值使用了粗體字標(biāo)注。

表2結(jié)果表明,BWIC算法在六個數(shù)據(jù)集上都取得了最好的聚類結(jié)果。由于使用了局部特征加權(quán)技術(shù)[6],WKM算法表現(xiàn)出比傳統(tǒng)的KM算法更高的性能。表2也顯示,WKP算法的性能多數(shù)情況勝過MKP,其部分原因在于WKP使用了(全局)特征加權(quán)技術(shù)[4],可以在聚類過程中識別各屬性對簇類的重要性,進(jìn)行子空間聚類。相對而言,由于在特征加權(quán)基礎(chǔ)上增加了簇類權(quán)重的識別功能,BWIC算法的聚類結(jié)果顯得更為準(zhǔn)確,尤其在樣本分布顯著不平衡的Splice和Hypothyroid數(shù)據(jù)集上,例如,在Splice數(shù)據(jù)集上,BWIC算法的平均MacroF1指標(biāo)和MicroF1指標(biāo)都超出對比算法近50%。

3.3 權(quán)重計算結(jié)果

為檢驗(yàn)BWIC算法“雙加權(quán)”方法的性能,表3列出了BWIC算法從每個數(shù)據(jù)集學(xué)習(xí)得到的簇類權(quán)重。如表3所示,輸出的權(quán)重值與簇的重要性相關(guān),例如,在聚類Splice數(shù)據(jù)時(其目的是識別外顯子exon和內(nèi)含子intron之間的邊界[5]),標(biāo)識為Neither的簇因不含exon或intron,BWIC算法賦予該簇比其他兩類(EI、IE)明顯小的權(quán)重;在Credit數(shù)據(jù)上,也與類似的結(jié)果,與遭拒絕信用卡申請者(負(fù)例)的簇Rejected相比,含正例的簇Approved的權(quán)重顯得更大。

表2 六個數(shù)據(jù)集上不同算法聚類性能比較

表3 BWIC算法學(xué)習(xí)的簇類權(quán)重

除簇類權(quán)重之外,BWIC算法還學(xué)習(xí)每個屬性的特征權(quán)重,表示簇類所在的軟子空間。下面選擇算法在Splice和Hypothyroid數(shù)據(jù)集上的聚類結(jié)果作進(jìn)一步分析,原因在于它們包含了較多的屬性(Splice)或具有樣本分布顯著不平衡的特點(diǎn)(Hypothyroid),具有代表性。圖2～3顯示了BWIC算法在從這兩個數(shù)據(jù)集學(xué)習(xí)到的特征權(quán)重的分布情況,并與WKP算法的結(jié)果作相比。由于WKM算法輸出類依賴的(而不是BWIC和WKP算法全局的[4])特征加權(quán)結(jié)果[6],圖2～3未包括WKM的結(jié)果。為便于比較,圖中所示的權(quán)重均規(guī)范化到區(qū)間[0,1]。

從對應(yīng)于Splice數(shù)據(jù)集的圖2可以看出,BWIC和WKP都賦予對應(yīng)氨基酸位點(diǎn)-2～+2的屬性較大的權(quán)重,這些位點(diǎn)正好是該數(shù)據(jù)集DNA序列上“donor(供體)”和“acceptor(受體)”所處的位置[5]。但是,BWIC產(chǎn)生的特征權(quán)重分布更為平滑,例如,位點(diǎn)+6～+30上的特征權(quán)重并沒有顯著變化(實(shí)際上權(quán)重接近0),這與WKP的結(jié)果構(gòu)成了鮮明的對比。這是由于BWIC算法計算的特征權(quán)重與簇類本身的權(quán)重有關(guān)(見式(10)),其中Neither簇的樣本占比超過50%,且具有較小的權(quán)重(參見表3),削弱了這些樣本對特征權(quán)重的影響,因而BWIC可以得到平滑分布的特征加權(quán)結(jié)果。

BWIC和WKP算法在Hypothyroid數(shù)據(jù)集上得到的特征權(quán)重分布也有明顯差異,如圖3所示。最明顯的區(qū)別在于:BWIC算法賦予第10個和第15個屬性(圖3中的a10和a15)最高的權(quán)重,而在WKP算法的結(jié)果中,最高者對應(yīng)a15和a17。為檢驗(yàn)BWIC算法輸出結(jié)果的合理性,生成了兩個約簡數(shù)據(jù)集,分別包含屬性子集A{a10,a15}和A{a15,a17},這里A表示原始屬性集合。表4顯示3種混合型數(shù)據(jù)聚類算法BWIC、WKP和MKP在兩個約簡數(shù)據(jù)集上的聚類性能指標(biāo)值,表中的符號↓表示指標(biāo)值下降的情況。如表4所示,與屬性集A{a15,a17}上的聚類結(jié)果相比，三種算法在屬性集A{a10,a15}上聚類的結(jié)果中，MacroF1和MicroF1兩個指標(biāo)值都出現(xiàn)了不同程度的下降。這個結(jié)果表明,BWIC算法的“雙加權(quán)”機(jī)制在進(jìn)行不平衡數(shù)據(jù)子空間聚類時,可以比對比算法獲得更為準(zhǔn)確的特征加權(quán)結(jié)果。

表4 兩個約簡Hypothyroid數(shù)據(jù)集上不同算法聚類性能對比

4 結(jié)語

本文提出一種不平衡數(shù)據(jù)的子空間聚類新算法BWIC。與現(xiàn)有的軟子空間聚類方法相比,新算法基于“雙加權(quán)”機(jī)制,在優(yōu)化每個屬性特征權(quán)重的同時,也優(yōu)化每個簇表示其重要性的簇類權(quán)重,二者相輔相成,為類不平衡數(shù)據(jù)中的簇類學(xué)習(xí)最優(yōu)的投影子空間。另提出了一種平衡混合型屬性及具有不同符號數(shù)目的類屬型屬性的新距離度量,以不同屬性上樣本分布的分散度為依據(jù),給出了屬性間相異性的平衡因子。在六個常用的實(shí)際數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果表明,相對于現(xiàn)有的子空間聚類算法,本文算法在不平衡數(shù)據(jù)集上的聚類結(jié)果質(zhì)量得到較為明顯的改善。

后續(xù)研究工作將著重于以下兩個方面:將提出的新距離度量運(yùn)用到有監(jiān)督分類應(yīng)用中,開展子空間最近鄰分類等研究;探討聚類有效性內(nèi)部準(zhǔn)則研究,提供不平衡數(shù)據(jù)集最佳聚類數(shù)目估計等問題的解決方案。

References)

[1] DENG Z, CHOI K-S, JIANG Y, et al. A survey on soft subspace clustering [J]. Information Sciences, 2016, 348: 84-106.

[2] AGGRAWAL C C. Data Mining: the Textbook[M]. Berlin: Springer, 2015.

[3] 陳黎飛, 郭躬德, 姜青山, 自適應(yīng)的軟子空間聚類算法[J]. 軟件學(xué)報, 2010, 21(10): 2513-2523. (CHEN L F, GUO G D, JIANG Q S. An adaptive algorithm for soft subspace clustering[J]. Journal of Software, 2010, 21(10): 2513-2523.)

[4] HUANG J Z, NG M K, RONG H, LI Z. Automated variable weighting ink-means type clustering [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(5): 657-668.

[5] CHEN L, WANG S, WANG K, et al. Soft subspace clustering of categorical data with probabilistic distance[J]. Pattern Recognition, 2016, 51 (C): 322-332.

[6] CAO F, JIANG J, LI D, et al. A weightingk-modes algorithm for subspace clustering of categorical data [J]. Neurocomputing, 2013, 108: 23-30.

[7] MACQUEEN J. Some methods for classification and analysis of multivariate observation[C]// Proceedings of the 5th Berkley Symposium on Mathematical Statistics and Probability. Berkeley: University of California Press, 1967: 281-297.

[8] HUANG Z, NG M. A note onk-modes clustering[J]. Journal of Classification, 2003, 20(2): 257-261.

[9] 李仁侃, 葉東毅. 粗糙K-Modes聚類算法[J]. 計算機(jī)應(yīng)用, 2011, 31(1): 97-100. (LI R K, YE D Y. RoughK-modes clustering algorithm[J]. Journal of Computer Applications, 2011, 31(1): 97-100.)

[10] 梁吉業(yè), 白亮, 曹付元. 基于新的距離度量的K-Modes聚類算法[J]. 計算機(jī)研究與發(fā)展, 2010, 47(10): 1749-1755. (LIANG J Y, BAI L, CAO F Y.K-Modes clustering algorithm based on a new distance measure[J]. Journal of Computer Research and Development, 2010, 47(10): 1749-1755.)

[11] ZHOU K, YANG S. Exploring the uniform effect of FCM clustering: a data distribution perspective [J]. Knowledge-Based Systems, 2016, 96 (C): 76-83.

[12] HE H, GARCIA E A. Learning from imbalanced data[J]. IEEE Transactions on Knowledge and Data Engineering, 2009, 21(9): 1263-1284.

[13] KUMAR N S, RAO K N, GOVARDHAN A, et al. UndersampledK-means approach for handling imbalanced distributed data[J]. Progress in Artificial Intelligence, 2014, 3(1): 29-38.

[14] LIANG J, BAI L, DANG C, et al. Thek-means-type algorithms versus imbalanced data distributions[J]. IEEE Transactions on Fuzzy Systems, 2012, 20(4): 728-745.

[15] DE AMORIM R C. A survey on feature weighting basedk-means algorithms [J]. Journal of Classification, 2016, 33(2): 210-242.

[16] LIANG J, ZHAO X, LI D, et al. Determining the number of clusters using information entropy for mixed data[J]. Pattern Recognition, 2012, 45(6): 2251-2265.

[17] ROUSSEEUW P J, Silhouettes: a graphical aid to the interpretation and validation of cluster analysis[J]. Computational and Applied Mathematics, 1987, 20: 53-65.

[18] YANG Y, WEBB G I, Proportionalk-interval discretization for naive-Bayes classifiers[C]// Proceedings of the 12th European Conference on Machine Learning. Berlin: Springer, 2001: 564-575.

Softsubspaceclusteringalgorithmforimbalanceddata

CHENG Lingfang1, YANG Tianpeng2, CHEN Lifei2*

(1.JinshanCollege,FujianAgricultureandForestryUniversity,FuzhouFujian350002,China;2.SchoolofMathematicsandComputerScience,FujianNormalUniversity,FuzhouFujian350117,China)

Aiming at the problem that the currentK-means-type soft-subspace algorithms cannot effectively cluster imbalanced data due to uniform effect, a new partition-based algorithm was proposed for soft subspace clustering on imbalanced data. First, a bi-weighting method was proposed, where each attribute was assigned a feature-weight and each cluster was assigned a cluster-weight to measure its importance for clustering. Second, in order to make a trade-off between attributes with different types or those categorical attributes having various numbers of categories, a new distance measurement was then proposed for mixed-type data. Third, an objective function was defined for the subspace clustering algorithm on imbalanced data based on the bi-weighting method, and the expressions for optimizing both the cluster-weights and feature-weights were derived. A series of experiments were conducted on some real-world data sets and the results demonstrated that the bi-weighting method used in the new algorithm can learn more accurate soft-subspace for the clusters hidden in the imbalanced data. Compared with the existingK-means-type soft-subspace clustering algorithms, the proposed algorithm yields higher clustering accuracy on imbalanced data, achieving about 50% improvements on the bioinformatic data used in the experiments.

soft subspace clustering; imbalanced data; feature weight; cluster weight

2017- 05- 15;

2017- 07- 10。

國家自然科學(xué)基金資助項(xiàng)目(61672157);福建省自然科學(xué)基金資助項(xiàng)目(2015J01238)。

程鈴鈁(1983—),女,山東滕州人,講師,碩士,主要研究方向:機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘; 楊天鵬(1991—),男,湖北十堰人,碩士研究生,主要研究方向:數(shù)據(jù)挖掘; 陳黎飛(1972—),男,福建長樂人,教授,博士,主要研究方向:統(tǒng)計機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、模式識別。

1001- 9081(2017)10- 2952- 06

10.11772/j.issn.1001- 9081.2017.10.2952

TP274.2

A

This work is partially supported by the National Natural Science Foundation of China (61672157), the Natural Science Foundation of Fujian Province (2015J01238).

CHENGLingfang, born in 1983, M. S., lecturer. Her research interests include machine learning, data mining.

YANGTianpeng, born in 1991, M. S. candidate. His research interests include data mining.

CHENLifei, born in 1972, Ph. D., professor. His research interests include statistical machine learning, data mining, pattern recognition.