迭代直覺模糊K-modes算法

陳育丹，高翠芳，沈莞薔，殷 萍

（江南大學理學院，江蘇無錫 214122）

0 引言

在最近的幾十年，數據科學家在挖掘真實生活數據方面面臨著兩大挑戰(zhàn)：一方面，在現實生活中，只有少量的觀測數據被標注出來；另一方面，由于資源和時間有限，給數據貼上標簽也很昂貴。因此，無監(jiān)督聚類技術在數據挖掘、模式識別、信息檢索等分析應用中發(fā)揮著越來越重要的作用。數值型數據、分類型數據以及混合型數據是統計學中對數據的一般分類。目前關注數值型數據聚類的學者較多，研究成果較為豐碩，但是由于分類型數據的復雜特性，分類型數據聚類的相關研究還不夠深入。首先，由于單個屬性的領域缺乏固有的順序，難以定義相似性概念，從而導致如何度量分類型數據對象之間的相似性成為一個難題。此外，對于數值型數據，類的原型往往由類的每個屬性域中對象的均值組成，可以用來表示類。無論如何，計算分類型數據的平均值是不可行的，這意味著用于聚類數值數據的技術并不能直接適用于分類型數據，因此，對分類型數據聚類算法的研究具有重大意義。

許多文獻報道了對分類型數據聚類算法的研究，其中在K-means 算法的基礎上提出的KM（K-Modes）算法［1］及其模糊版本FKM（Fuzzy KM）算法［2］仍然是目前研究較為廣泛的方法。而FKM 算法利用其具有概率隸屬度值的模糊目標函數來處理聚類的重疊，具有優(yōu)于傳統的硬聚類方法的優(yōu)點。FKM 算法被提出以后，Kim 等［3］提出了一種模糊質心算法，解決了FKM 算法質心表示信息缺失的問題。Bai 等［4］在目標函數中加入類間信息，改進了FKM 算法的目標函數，優(yōu)化了算法的類間分離度。Saha 等［5］對每個類別屬性使用權重因子，提出了一種加權的FKM 算法。白亮等［6］改進了FKM 算法中使用的0-1 度量，提出了一種基于對象對類隸屬度相似性度量的FKM 算法——NDFKM（FKM based on New Dissimilarity）。為了避免初始類中心隨機選擇對聚類效果的影響，一些初始類中心選擇算法相繼被提出［7-10］。也有學者針對簡單匹配相似性度量無法準確挖掘分類型數據的內在相關性，對分類型數據相似性度量展開了研究［11-14］。近年來，受到智能優(yōu)化算法全局搜索能力極佳的啟發(fā)，將智能優(yōu)化算法與分類型數據聚類算法結合起來，提高其全局搜索能力亦吸引了許多學者的目光［15-18］。

雖然近年來分類型數據聚類算法已經取得了長足發(fā)展，但是相較于數值型數據聚類算法［19-23］，現有分類型數據聚類算法在處理聚類過程中的高模糊性以及不確定性等方面仍有欠缺。針對這個問題，Sarkar 等［24］用可信性測度衡量數據對象與類的隸屬關系，提出了一種可信性K-modes 算法。Kuo 等［25］將加權FKM 算法與直覺模糊集融合，吸取了直覺模糊集處理不確定性問題的優(yōu)勢。Goyal 等［26］先將直覺模糊集融入到FKM 算法中，并在目標函數中加入直覺模糊熵最大化每一類中優(yōu)良數據點，提出了一種直覺FKM（Intuitionistic FKM，IFKM）算法；然后將IFKM 算法與遺傳算法的框架結合，擴大了最優(yōu)搜索的范圍。

然而IFKM 算法在度量數據對象之間的相似性時僅使用簡單匹配相似性度量，未能充分挖掘同一類中數據對象的相似度以及屬性特征對數據對象之間相似性的影響；并且，由于在迭代聚類的過程中僅把直覺模糊集作為判別數據類別的一種累加手段，沒有將直覺模糊的思想貫穿于整個迭代過程，而是采用基于類屬頻率的方法確定新的類中心，IFKM 算法未能將直覺模糊在處理不確定性問題上的優(yōu)勢充分發(fā)揮。針對這兩個問題，本文提出了一種迭代IFKM（Iterative IFKM，IIFKM）算法。

本文的主要工作有以下幾點：

1）定義了一種加權的直覺模糊隸屬度相似性度量；

2）提出了IIFKM 算法，該算法在聚類過程中將直覺模糊隸屬度矩陣作為迭代信息貫穿于整個聚類過程，使得算法中的模糊思想得到充分體現。

1 FKM算法

FKM 算法［2］是通過搜索式（1）中目標函數的局部極小值對特征向量進行聚類：

F的最小化是基于對U（隸屬度矩陣）和Z的適當選擇，采用式（2）～（3）進行隸屬度以及類中心的迭代：

其中：uli為第i個數據xi=(xi1，xi2，…，xim)對第l個類的概率隸屬度；α為模糊因子，一般來說α>1；zl=(zl1，zl2，…，zlm)為第l個Modes（類中心）。D(xi，zl)為第i個數據與第l個Mode之間的相異性度量，采用漢明距離度量對象之間的距離：

其中：nj為第j(1≤j≤m)維屬性Aj的不同屬性值的數目，為第j(1≤j≤m)維屬性Aj的第t個屬性值。

2 IFKM算法

文獻［26］中提出的IFKM 算法旨在將直覺模糊集與直覺模糊熵融合到FKM 算法的框架中，以提高聚類性能。該算法首先將猶豫度加入到模糊隸屬度中，得到直覺模糊隸屬度值；然后在每一次迭代中根據直覺模糊隸屬度判別數據對象所處類別，選擇屬性類別頻率較高的數據對象作為新的集群中心，最后將直覺模糊熵加入目標函數中，最大化每一類優(yōu)良數據點。

定義1設Y為一個論域，M是Y上的一個直覺模糊集（Intuitionistic Fuzzy Set，IFS），則M可表示為：

其中：Y是一個論域；uM(y)→[0，1]為直覺模糊集M的隸屬函數；vM(y)→[0，1]為直覺模糊集M的非隸屬函數，表示元素y對M的“支持程度”與“反對程度”，且對任意的y∈Y，都有0≤uM(y)+vM(y)≤1 成立。

進一步，稱πM(y)=1-uM(y)-vM(y)為直覺模糊集M中元素y的猶豫度。顯然，0≤πM(y)≤1，且如果πM(y)=0，則IFS 為模糊集；反之，如果πM(y)=1，則IFS 為完全直覺集。

直覺模糊補被用來構造IFS。建立直覺模糊補的常用方法有兩種：Yager 生成函數和Sugeno 生成函數。根據Yager 的生成函數［27］，得到的IFS 為：

其中：β∈(0，∞)為非隸屬度和猶豫度的控制參數。那么，猶豫度可以計算為：

考慮Sugeno 的生成函數［28］，IFS 和猶豫度可表示為：

定義2設uM(y)、vM(y)、πM(y)為論域Y={y1，y2，…，yn}中元素的隸屬度、非隸屬度和猶豫度，M是Y上的一個直覺模糊集（IFS），則直覺模糊集M上的直覺模糊熵（Intuitionistic Fuzzy Entropy，IFE）定義為：

其中：πM(y)=1-uM(y)-vM(y)。

IFKM 算法源自直覺模糊集［29］。模糊集依賴于分級的隸屬度值，直覺模糊集依賴于隸屬度和非隸屬度值，從而導致與域內每個元素相關聯的猶豫值。在該算法中，猶豫值作為新參數在IFKM 算法的概念中加入了直觀的隸屬度。這個程度導致了一個對象在一個特定值的特定集群中的成員關系的不確定性。IFKM 算法的步驟如下：

步驟1 為k個集群分配初始集群中心或模式，令t=0。

步驟2 利用式（4）計算數據對象xi與類中心zl之間的距離矩陣D(t)。

步驟3 生成模糊劃分矩陣或隸屬度矩陣U(t)，如式（2）所示。

步驟4 利用式（9）計算猶豫度矩陣：

步驟5

1）計算直覺模糊隸屬度矩陣U*(t)：

2）將xi分到第l個類如果。

步驟6 選擇類別屬性相對頻率較高的xi作為新的代表，即集群中心或模式；

步驟7 重復步驟2）～6），直到|U*(t)-U*(t-1)|≤ε為止。

IFKM 算法的目標函數包含兩項：1）常規(guī)直覺模糊集的改進目標函數；2）直覺模糊熵。可用公式表示為：

3 本文算法

本文所提IIFKM 算法使用FKM 算法的范式聚類分類數據。在本文算法中，將n個分類對象聚類成k個簇的目標是找到U和Z使目標函數F?(U，Z)取得極小值。接下來本文將從相似性度量、類中心更新方式以及算法的具體步驟等方面詳細論述本文所提IIFKM 算法。

3.1 加權的直覺模糊隸屬度相似性度量

在分類型數據聚類算法中，相似性度量是一個特別重要的因素。一個好的相似性度量可以更好地刻畫數據對象之間的相似程度，從而使得聚類算法取得更加理想的聚類效果。對于分類型數據聚類算法的相似性度量來說，簡單匹配是一種常見的方法，許多分類型數據聚類算法都采用了簡單匹配的思想［30-32］；然而，簡單的匹配往往導致簇內相似性［33］較弱，忽略了分類值之間隱藏的相似性［34］。白亮等［6］基于對象對類的模糊隸屬度提出了一種適用于FKM 算法的相似性度量，強化了類內相似性；但是相似性度量沒有刻畫聚類中不同屬性的重要程度。本文以文獻［6］中提出的相似性度量為原型，進一步考慮不同維度屬性的貢獻程度，并融合了直覺模糊隸屬度定義了一種加權的直覺模糊隸屬度相似性度量。

3.1.1 屬性權重的計算

從信息論的角度來看，一個屬性的重要性可以看作是數據集對該屬性的不均勻程度。此外，在文獻［35］中有描述，如果一個屬性的信息含量高，那么該屬性的數據集的不同質性也高。在文獻［36］中，屬性A的重要性通過它在每個屬性值上的平均熵來量化，每個屬性的權重可以如式（12）計算：

3.1.2 加權的直覺模糊隸屬度相似性度量

定義3加權直覺模糊隸屬度相似性度量：設對象集X={x1，x2，…，xn}，屬性集A={A1，A2，…，Am}，類中心Z={z1，z2，…，zk}，xi∈X(1≤i≤n)，zl∈Z(1≤l≤k)。xi和zl分別被A描述為xi=(xi1，xi2，…，xim)和zl=(zl1，zl2，…，zlm)。本文定義的加權直覺模糊隸屬度相似性度量（距離公式）為：

加權的直覺模糊隸屬度相似性度量將數據對象對類的直覺模糊隸屬程度以及屬性權重作為衡量數據對象之間相似性的標準，強化了類內相似性與屬性貢獻度的同時，也與本文提出的IIFKM 算法更加契合。

3.2 隸屬度及類中心更新規(guī)則

本文算法在構造直覺模糊集時并未如IFKM 算法一樣選用Sugeno 的生成函數，而是采用了文獻［27］中使用的Yager生成函數。故而本文算法的目標函數為：

直覺模糊集構造方式的改變并未影響算法對數據對象隸屬度的判斷，故而本文算法的直覺模糊隸屬度更新方式除猶豫度計算方法改為式（7）外，其他與IFKM 算法一致。

定理1IFKM 算法類中心更新規(guī)則：設對象集X={x1，x2，…，xn}，屬性集A={A1，A2，…，Am}，DOM(Aj)=，其中nj為屬性aj中不同屬性值的數量(1≤j≤m)，類中心Z={z1，z2，…，zk}，xi∈X(1≤i≤n)，zl∈Z(1≤l≤k)。xi和zl分別被A描述為xi=(xi1，xi2，…，xim)和zl=(zl1，zl2，…，zlm)。則目標函數F*(U，Z)=取得最小值，當且僅當zlj=∈DOM(Aj)(1≤j≤m)，其中：

由于每個屬性特征的權重wj以及每個數據對象對固定類的直覺模糊隸屬度都是固定的，即固定，故當最大時ψ(i，j)取得最小值。

3.3 IIFKM算法的具體步驟

本文算法雖然融入了直覺模糊集與直覺模糊熵的思想并將其貫穿于整個迭代過程中，但是算法的思路與FKM 算法一樣，都是通過迭代隸屬度矩陣以及類中心來使目標函數達到極小值，故而算法的基本流程與FKM 算法并無太大區(qū)別。算法的具體步驟如下：

步驟1 隨機選取數據集X中的k個樣本作為初始類中心：Z(0)=(z1(0)，z2(0)，…，zk(0))。

步驟2 利用式（2）、（4）計算所有樣本xi(1≤i≤n)對初始類中心Z(0)的初始隸屬度矩陣U(1)；t=1。

步驟3 利用U(t)及式（7）計算數據集X中樣本xi(1≤i≤n)對每個類中心的猶豫度πl(wèi)i(t)，從而根據式（10）得到直覺模糊隸屬度矩陣U*(t)。

步驟4 根據式（16）計算k個新的類中心Z(t)=(z1(t)，z2(t)，…，zk(t))。

步驟5 根據新的類中心Z(t)更新加權的直覺模糊隸屬度度量矩陣D*(t)，從而由D*(t)得到新的隸屬度矩陣U(t+1)。

步驟6 重復步驟3）～5），直到|F*(t)-F*(t-1)|≤ε為止(1≤t≤T)，T為最大迭代次數。

4 實驗與結果分析

4.1 實驗數據集

本文從UCI 數據庫中選取了Lung-cancer、Zoo、Dermatology、Breast-cancer、Mushroom 共5 個常用的真實數據集進行分析，其中，在Breast-cancer 和Lung-cancer 中對缺失屬性值的樣本進行刪除。5 個數據集的簡略描述如表1所示。

表1 數據集描述Tab.1 Description of datasets

4.2 聚類性能評估指標

本文選取了3 個常用的聚類性能評估指標來分析算法的聚類質量：分類正確率AC（accuracy）、分類精度PR（precision）和召回率RE（recall）［37］。這三個指標是利用真實類標簽來評價每個給定數據集的聚類結果的外部標準，AC是對聚類整體正確率的評價；PR是精確性的度量，表示被分為正例的示例中實際為正例的比例；RE是覆蓋面的度量，度量有多少個正例被分為正例。如果聚類結果接近真實的類分布，則這些評價指標的值是高的。AC、PR、RE的定義如下：

其中：ai是正確分配給類Ci的數據對象的數量；bi表示錯誤地分配給類Ci的數據對象的數量；ci為類Ci錯誤拒絕的數據對象的數量；n為整個數據集中全部數據對象的數量；k為數據集中包含的類的數量。

4.3 非隸屬度和猶豫度的控制參數調試

對于直覺模糊聚類算法，需要適當設置非隸屬度和猶豫度的控制參數。在數值型數據的直覺模糊C均值算法中，Chaira［20］將非隸屬度和猶豫度的控制參數設置為0.85。文獻［26］中的分類型數據IFKM 算法的猶豫度控制參數λ設置為2。但是由于本文算法的直覺模糊集構造與文獻［26］不一致，猶豫度的計算方式也不同，所以本文算法的猶豫度控制參數需要重新調試。經過實驗分析，本文提出的分類型數據的加權直覺模糊聚類算法在β=0.85 時表現不佳，且當β>2.5 時，聚類效果亦不理想；進一步，與文獻［20］中β<0.5 時聚類效果失真類似，本文算法在β<0.8 時，出現類中心重合的現象。故在接下來的實驗分析中，將模糊因子α設置為1.1［2］，且分別取β為0.85、0.95、1.05、1.85、2.0、2.5 驗證本文算法的性能。這里將IIFKM 對各數據集分別執(zhí)行100次并求出AC、PR、RE的均值記錄至表2 中。從表2 可看出，IIFKM 算法的聚類效果受猶豫度的控制參數β影響，在本文的5 個數據集中，Lung-cancer、Zoo 和Breast-cancer 數據集的β取值為0.95 時聚類效果最優(yōu)，Dermatology 和Mushroom 數據集的β取值為2.0 聚類效果最優(yōu)。

表2 IIFKM算法在不同β值時的AC、PR、RETab.2 AC，PR，RE of IIFKM algorithm with different values of β

4.4 聚類性能分析

各算法通過Matlab2018a 編程運行，對KM［1］、FKM［2］、IFKM［26］、NDFKM［6］和本文IIFKM 算法進行分析，求出聚類性能指標AC、PR和RE。算法參數設置為：FKM 和IIFKM 的閾值ε參照文獻［24］以及具體實驗設置為0.000 01，同時將最大迭代次數T設置為100，算法的模糊因子α按文獻［2］推薦的設置為1.1，非隸屬度和猶豫度的控制參數β，從表2 所示的實驗結果可知，β=0.95，2.0 時本文算法取得較好聚類結果。為了使聚類結果最優(yōu)，Lung-cancer、Zoo 和Breast-cancer數據集的β取值0.95，Dermatology 和Mushroom 數據集的β取值2.0。由于上述五種算法均受初始類中心的影響較大，每次運行的結果都可能因其初始類中心的不同而有差異。為了避免隨機性，在5 個數據集上，各算法分別運行100 次后，再比較最終結果的平均值。

從表3 可以看出，IIFKM 算法的聚類效果在整體上是優(yōu)于其他4 種算法的。除了Zoo 數據集，IIFKM 算法在Lungcancer、Dermatology、Breast-cancer 數據集上均表現良好。在AC和RE這兩個指標上，相較于IFKM 算法，有7%～11%的提高；相較于NDFKM 算法，也有2%～6% 的提高。這說明IIFKM 算法在正確聚類和聚類查準上表現優(yōu)異。并且除了在Zoo 數據集上，IIFKM 算法的PR值略低于IFKM 算法外，在其他數據集中IIFKM 算法的PR值均有一定提升，說明算法在每一類中的查準能力也是有保證的。此外由圖1 可以看出，本文算法的準確聚類能力是穩(wěn)定的，除了在Zoo 數據集上聚類的穩(wěn)定性略差于其他算法，在其他4 個數據集中的穩(wěn)定性均優(yōu)于其他算法，尤其是在Dermatology 數據集中，在表現出優(yōu)秀的穩(wěn)定性的同時聚類準確率及其上限均高于KM、FKM、IFKM 和NDFKM 算法。

表3 五種算法的實驗結果Tab.3 Experimental results of five algorithms

圖1 各算法在5個數據集上的AC箱型圖Fig.1 AC box plots of each algorithms on 5 datasets

為了進一步驗證本文提出的IIFKM 算法框架的有效性，將本文算法中相似性度量換成和IFKM 算法中一樣的簡單匹配相似性度量，在Matlab2018a 中與IFKM 算法作對比實驗后將實驗結果記錄于表4。為了避免隨機性，在實驗過程中，在每個數據集上對算法執(zhí)行100 次后取平均聚類結果。從表4 所示的實驗結果可知，本文所提IIFKM 算法框架在簡單匹配相似性度量（IIFKM0）下，比IFKM 算法的聚類效果更好。這表明本文算法將直覺模糊隸屬度作為聚類過程的迭代信息是正確、有效的。

表4 IFKM算法和IIFKM0算法的實驗結果對比Tab.4 Comparison of experimental results of IFKM algorithm and IIFKM0 algorithm

5 結語

本文算法將直覺模糊隸屬度矩陣作為迭代信息貫穿于整個聚類中，充分發(fā)揮了直覺模糊集在聚類過程中處理不確定性問題的優(yōu)勢。由于IFKM 算法在度量相似性時采用漢明距離，不足以清晰度量對象之間的相似程度，本文定義了一種加權的基于對象對類的直覺模糊隸屬度相似性度量。通過與K-modes、FKM 以及IFKM 等算法的實驗對比，實驗結果表明本文算法在聚類準確率、類純度以及召回率等方面均有提升。不過，由于本文算法的初始類中心是隨機選取的，如果初始類中心選取了離群點，算法效果比較糟糕，后續(xù)可加入優(yōu)質初始類中心選擇算法進一步提升算法性能；并且，本文雖然對猶豫度控制參數β進行了初步調試，但是如何給出一個比較明確的參數選擇指南，本文還未有定論，后續(xù)會對此進行進一步研究。