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

（江南大學(xué)理學(xué)院，江蘇無錫 214122）

0 引言

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

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

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

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

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

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

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

1 FKM算法

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

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

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

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

2 IFKM算法

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

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

其中：Y是一個論域；uM(y)→[0，1]為直覺模糊集M的隸屬函數(shù)；vM(y)→[0，1]為直覺模糊集M的非隸屬函數(shù)，表示元素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 為完全直覺集。

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

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

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

定義2設(shè)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］。模糊集依賴于分級的隸屬度值，直覺模糊集依賴于隸屬度和非隸屬度值，從而導(dǎo)致與域內(nèi)每個元素相關(guān)聯(lián)的猶豫值。在該算法中，猶豫值作為新參數(shù)在IFKM 算法的概念中加入了直觀的隸屬度。這個程度導(dǎo)致了一個對象在一個特定值的特定集群中的成員關(guān)系的不確定性。IFKM 算法的步驟如下：

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

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

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

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

步驟5

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

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

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

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

IFKM 算法的目標(biāo)函數(shù)包含兩項：1）常規(guī)直覺模糊集的改進目標(biāo)函數(shù)；2）直覺模糊熵?？捎霉奖硎緸椋?/p>

3 本文算法

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

3.1 加權(quán)的直覺模糊隸屬度相似性度量

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

3.1.1 屬性權(quán)重的計算

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

3.1.2 加權(quán)的直覺模糊隸屬度相似性度量

定義3加權(quán)直覺模糊隸屬度相似性度量：設(shè)對象集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)。本文定義的加權(quán)直覺模糊隸屬度相似性度量（距離公式）為：

加權(quán)的直覺模糊隸屬度相似性度量將數(shù)據(jù)對象對類的直覺模糊隸屬程度以及屬性權(quán)重作為衡量數(shù)據(jù)對象之間相似性的標(biāo)準(zhǔn)，強化了類內(nèi)相似性與屬性貢獻(xiàn)度的同時，也與本文提出的IIFKM 算法更加契合。

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

本文算法在構(gòu)造直覺模糊集時并未如IFKM 算法一樣選用Sugeno 的生成函數(shù)，而是采用了文獻(xiàn)［27］中使用的Yager生成函數(shù)。故而本文算法的目標(biāo)函數(shù)為：

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

定理1IFKM 算法類中心更新規(guī)則：設(shè)對象集X={x1，x2，…，xn}，屬性集A={A1，A2，…，Am}，DOM(Aj)=，其中nj為屬性aj中不同屬性值的數(shù)量(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)。則目標(biāo)函數(shù)F*(U，Z)=取得最小值，當(dāng)且僅當(dāng)zlj=∈DOM(Aj)(1≤j≤m)，其中：

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

3.3 IIFKM算法的具體步驟

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

步驟1 隨機選取數(shù)據(jù)集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）計算數(shù)據(jù)集X中樣本xi(1≤i≤n)對每個類中心的猶豫度πl(wèi)i(t)，從而根據(jù)式（10）得到直覺模糊隸屬度矩陣U*(t)。

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

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

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

4 實驗與結(jié)果分析

4.1 實驗數(shù)據(jù)集

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

表1 數(shù)據(jù)集描述Tab.1 Description of datasets

4.2 聚類性能評估指標(biāo)

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

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

4.3 非隸屬度和猶豫度的控制參數(shù)調(diào)試

對于直覺模糊聚類算法，需要適當(dāng)設(shè)置非隸屬度和猶豫度的控制參數(shù)。在數(shù)值型數(shù)據(jù)的直覺模糊C均值算法中，Chaira［20］將非隸屬度和猶豫度的控制參數(shù)設(shè)置為0.85。文獻(xiàn)［26］中的分類型數(shù)據(jù)IFKM 算法的猶豫度控制參數(shù)λ設(shè)置為2。但是由于本文算法的直覺模糊集構(gòu)造與文獻(xiàn)［26］不一致，猶豫度的計算方式也不同，所以本文算法的猶豫度控制參數(shù)需要重新調(diào)試。經(jīng)過實驗分析，本文提出的分類型數(shù)據(jù)的加權(quán)直覺模糊聚類算法在β=0.85 時表現(xiàn)不佳，且當(dāng)β>2.5 時，聚類效果亦不理想；進一步，與文獻(xiàn)［20］中β<0.5 時聚類效果失真類似，本文算法在β<0.8 時，出現(xiàn)類中心重合的現(xiàn)象。故在接下來的實驗分析中，將模糊因子α設(shè)置為1.1［2］，且分別取β為0.85、0.95、1.05、1.85、2.0、2.5 驗證本文算法的性能。這里將IIFKM 對各數(shù)據(jù)集分別執(zhí)行100次并求出AC、PR、RE的均值記錄至表2 中。從表2 可看出，IIFKM 算法的聚類效果受猶豫度的控制參數(shù)β影響，在本文的5 個數(shù)據(jù)集中，Lung-cancer、Zoo 和Breast-cancer 數(shù)據(jù)集的β取值為0.95 時聚類效果最優(yōu)，Dermatology 和Mushroom 數(shù)據(jù)集的β取值為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 算法進行分析，求出聚類性能指標(biāo)AC、PR和RE。算法參數(shù)設(shè)置為：FKM 和IIFKM 的閾值ε參照文獻(xiàn)［24］以及具體實驗設(shè)置為0.000 01，同時將最大迭代次數(shù)T設(shè)置為100，算法的模糊因子α按文獻(xiàn)［2］推薦的設(shè)置為1.1，非隸屬度和猶豫度的控制參數(shù)β，從表2 所示的實驗結(jié)果可知，β=0.95，2.0 時本文算法取得較好聚類結(jié)果。為了使聚類結(jié)果最優(yōu)，Lung-cancer、Zoo 和Breast-cancer數(shù)據(jù)集的β取值0.95，Dermatology 和Mushroom 數(shù)據(jù)集的β取值2.0。由于上述五種算法均受初始類中心的影響較大，每次運行的結(jié)果都可能因其初始類中心的不同而有差異。為了避免隨機性，在5 個數(shù)據(jù)集上，各算法分別運行100 次后，再比較最終結(jié)果的平均值。

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

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

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

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

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

5 結(jié)語

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