不平衡數據的軟子空間聚類算法

程鈴鈁,楊天鵬,陳黎飛

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

不平衡數據的軟子空間聚類算法

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

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

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

軟子空間聚類;不平衡數據;特征權重;簇類權重

0 引言

子空間聚類(subspace clustering)是數據挖掘諸多應用領域中一種重要工具,它根據數據對象相似性進行無監督數據簇類劃分的同時,能夠識別和生成各簇類相關的特征(或屬性)集合,組成類依賴(cluster-dependent)的子空間[1-2]。例如,聚類由患者各種生理指標特征構成的醫學診斷數據時,子空間算法依據生理指標的差異將患者歸類到不同的疾病類型,同時輸出與這些疾病相關的重要生理指標。鑒于這些實際應用數據中簇類結構的復雜性,子空間聚類已成為聚類研究和應用中富有挑戰性的任務之一[1-5]。

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

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

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

1 相關工作

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

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

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

其中：β≠0為加權參數。相應地,對于類屬型數據,通常采用如下定義[5-6]:

(1)

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

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

2 BWIC聚類

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

2.1 屬性平衡的距離度量

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

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

(2)

性質1 若屬性d為數值型且?x∈ck:xd∈[0,1],則

證畢。

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

(3)

其中:

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

性質2 若屬性d為類屬型,有

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

證畢。

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

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

(4)

其中:

(5)

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

2.2 聚類目標函數

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

ωkd=hk×wd

(6)

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

(7)

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

其中:W={wd|d=1,2,…,D}為待優化的特征權重集合。由于簇權重與特征權重無關,這里hk(k=1,2,…,K)并不是模型的參數,而是通過式(8)估計:

(8)

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

由于包含了特征權重W,J0(C,W)并不是一個凸函數。為此,借鑒文獻[15]方法,引入平滑函數wlnw使目標函數更容易優化。這樣,BWIC算法的目標優化函數變為:

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

(9)

2.3 聚類算法

給定數據集DB和K,BWIC算法需求解2.2節定義的帶約束的非線性優化問題。應用拉格朗日乘子法引入式(7)的約束條件,算法需最小的目標函數轉換為:

(10)

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

(11)

基于上述優化方法的聚類算法描述如下。

算法1 聚類算法BWIC。

輸入 數據集DB及聚類數K、參數γ。

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

Begin

生成數據集初始劃分C,并初始化W中的每個屬性權重為1/D。

Repeat

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

固定C,根據式(10)更新屬性權重W;

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

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

End

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

3 實驗與分析

本章評估BWIC在一些實際不平衡數據集上的聚類性能,并與若干現有算法作比較。

3.1 數據集和實驗設置

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

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

表1 實驗使用的實際數據集

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

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

3.2 聚類結果

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

圖1 六個數據集上BWIC算法參數與聚類質量間的關系

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

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

3.3 權重計算結果

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

表2 六個數據集上不同算法聚類性能比較

表3 BWIC算法學習的簇類權重

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

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

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

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

4 結語

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

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

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] 陳黎飛, 郭躬德, 姜青山, 自適應的軟子空間聚類算法[J]. 軟件學報, 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]. 計算機應用, 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] 梁吉業, 白亮, 曹付元. 基于新的距離度量的K-Modes聚類算法[J]. 計算機研究與發展, 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。

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

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

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.