徐健鋒 鄒偉康 梁偉 程高潔 張遠(yuǎn)健

摘 要：當(dāng)前聚類(lèi)集成的研究主要是圍繞著集成策略的優(yōu)化展開(kāi)，而針對(duì)基聚類(lèi)質(zhì)量的度量及優(yōu)化卻較少研究?；谛畔㈧乩碚撎岢隽艘环N基聚類(lèi)的質(zhì)量度量指標(biāo)，并結(jié)合三支決策思想構(gòu)造了面向基聚類(lèi)的三支篩選方法。首先預(yù)設(shè)基聚類(lèi)篩選三支決策的閾值α、β，然后計(jì)算各基聚類(lèi)中類(lèi)簇質(zhì)量的平均值，并把其作為各基聚類(lèi)的質(zhì)量度量指標(biāo)，最后實(shí)施三支決策。決策策略為： 當(dāng)某個(gè)基聚類(lèi)的質(zhì)量度量指標(biāo)小于閾值β時(shí)，刪除該基聚類(lèi); 當(dāng)某個(gè)基聚類(lèi)的質(zhì)量度量指標(biāo)大于等于閾值α?xí)r，保留該基聚類(lèi); 當(dāng)某個(gè)基聚類(lèi)的質(zhì)量度量指標(biāo)大于等于β小于α?xí)r，重新計(jì)算該基聚類(lèi)質(zhì)量，并且再次實(shí)施上述三支決策直至沒(méi)有基聚類(lèi)被刪除或達(dá)到指定迭代次數(shù)。對(duì)比實(shí)驗(yàn)結(jié)果表明，基聚類(lèi)三支篩選方法能夠有效提升聚類(lèi)集成效果。

關(guān)鍵詞：三支決策;聚類(lèi)集成;基聚類(lèi);三支篩選

中圖分類(lèi)號(hào)：TP181

文獻(xiàn)標(biāo)志碼：A

Threeway screening method of basic clustering for ensemble clustering

XU Jianfeng1，2，3*， ZOU Weikang1， LIANG Wei2， CHENG Gaojie2， ZHANG Yuanjian3

1.School of Information Engineering， Nanchang University， Nanchang Jiangxi 330031， China;

2.School of Software， Nanchang University， Nanchang Jiangxi 330047， China;

3.College of Electronics and Information Engineering， Tongji University， Shanghai 201804， China

Abstract：

At present， the researches of ensemble clustering mainly focus on the optimization of ensemble strategy， while the measurement and optimization of the quality of basic clustering are rarely studied. On the basis of information entropy theory， a quality measurement index of basic clustering was proposed， and a threeway screening method for basic clustering was constructed based on threeway decision. Firstly，α，βwere reset as the thresholds of threeway decision of basic clustering screening. Secondly， the average cluster quality of each basic clustering was calculated and was used as the quality measurement index of each basic clustering. Finally， the threeway decision was implemented. For one threeway screening， its decision strategy is：1） deleting the basic clustering if the quality measurement index of the basic clustering is less than the thresholdβ; 2） keeping the basic clustering if the quality measurement index of the basic clustering is greater than or equals to the thresholdα; 3） recalculating the quality of a basic clustering and if the quality measurement index of the basic clustering is greater thanβand less thanαor equals toβ. For the third option， the decision process continues until there is no deletion of basic clustering or reaching the times of iteration. The comparative experiments show that the threeway screening method of basic clustering can effectively improve the ensemble clustering effects.

Key words：

threeway decision; ensemble clustering; basic clustering; threeway screening

0?引言

近年來(lái)，由于聚類(lèi)效果及魯棒性方面的優(yōu)勢(shì)，聚類(lèi)集成算法已經(jīng)逐步成為無(wú)監(jiān)督機(jī)器學(xué)習(xí)的一種熱點(diǎn)研究問(wèn)題。聚類(lèi)集成的主要思想是通過(guò)融合不同版本的基聚類(lèi)成員來(lái)實(shí)現(xiàn)無(wú)監(jiān)督的分類(lèi)任務(wù)[1]。聚類(lèi)集成的效果主要與該算法的兩個(gè)主要環(huán)節(jié)緊密相關(guān)： 首先是產(chǎn)生高質(zhì)量的基聚類(lèi)成員集合，其次是設(shè)計(jì)高效的集成策略（一致性函數(shù)）。當(dāng)前聚類(lèi)集成技術(shù)的主要研究?jī)?nèi)容也圍繞上述兩個(gè)步驟展開(kāi)。

其中集成策略就是通過(guò)有效的組合策略將基聚類(lèi)成員高效地組合起來(lái)。集成策略主要有超圖[2-4]、信息論[5]、關(guān)聯(lián)矩陣[6-7]、投票[8]、關(guān)聯(lián)規(guī)則[9]等。

而對(duì)于基聚類(lèi)成員產(chǎn)生，主要有如下兩種方法：一是采用同一聚類(lèi)方法設(shè)置不同的初始參數(shù)[10-11]或者不同聚類(lèi)方法[12-13]作用于同一數(shù)據(jù)集來(lái)得到不同的基聚類(lèi)成員; 二是采用同一聚類(lèi)方法處理同一數(shù)據(jù)集的不同非等值變形進(jìn)而得到不同的基聚類(lèi)成員，變形包括對(duì)數(shù)據(jù)集進(jìn)行投影[14-16]和采樣[17-19]操作處理。這兩種方法都以生成高質(zhì)量的基聚類(lèi)為研究目標(biāo)，但是多次反復(fù)的基聚類(lèi)計(jì)算過(guò)程難免會(huì)生成部分低質(zhì)量基聚類(lèi)，而針對(duì)基聚類(lèi)質(zhì)量的度量及其篩選方法的研究文獻(xiàn)報(bào)道目前還較少。如果能夠構(gòu)造有效的基聚類(lèi)質(zhì)量度量，并且根據(jù)基聚類(lèi)質(zhì)量對(duì)基聚類(lèi)進(jìn)行優(yōu)化篩選必然能夠提升聚類(lèi)集成的效果。鑒于基聚類(lèi)質(zhì)量的度量是一種典型的不確定問(wèn)題，本文采用信息熵理論提出了一種基聚類(lèi)質(zhì)量度量方法，并且結(jié)合三支決策思想[20-22]構(gòu)造了基聚類(lèi)三支篩選優(yōu)化模型。

1?相關(guān)技術(shù)

1.1?三支決策基本理論

三支決策是來(lái)源于粗糙集理論[23-24]的一種重要的粒計(jì)算方法[25]。相較于傳統(tǒng)的二支決策（正/負(fù)決策）而言，三支決策增加了延遲決策作為不能準(zhǔn)確作出正負(fù)決策時(shí)的決策行為，三支決策也合理地解釋了粗糙集理論中的三個(gè)決策域（正域、負(fù)域和邊界域）劃分行為。

三支決策基本思想是通過(guò)評(píng)價(jià)函數(shù)λ對(duì)某個(gè)數(shù)據(jù)對(duì)象集合D中的元素x∈D進(jìn)行不確定程度的劃分：

當(dāng)λ（x）≥α?xí)r，元素x被劃分到集合D的正決策域POS（α， β）（x）;

當(dāng)λ（x）<β時(shí)，元素x被劃分到集合D的負(fù)決策域NEG（α， β）（x）;

當(dāng)β≤λ（x）<α?xí)r，元素x被劃分到集合D的延遲決策域BND（α， β）（x）。

其中（α， β）為三支決策閾值，通常設(shè)定為 0≤β<α≤1。

基于三支決策，全域D可以被劃分為3個(gè)不相交的區(qū)域：

POS（α， β）（D）={x∈Dλ（x）≥α}

BND（α， β）（D）={x∈D|β≤λ（x）<α}

NEG（α， β）（D）={x∈D|λ（x）<β}

1.2?聚類(lèi)集成

聚類(lèi)集成的算法流程主要由基聚類(lèi)的生成和基聚類(lèi)的集成兩個(gè)主要步驟構(gòu)成。其中，生成M個(gè)基聚類(lèi)就是對(duì)數(shù)據(jù)集D執(zhí)行M次聚類(lèi)，M次聚類(lèi)的結(jié)果構(gòu)成的基聚類(lèi)集合可記作Π={C1，C2，…，CM}，其中Ci∈Π表示Π中第i個(gè)基聚類(lèi)。Π的基數(shù)Π=M為基聚類(lèi)成員數(shù)量，|*|表示集合的基數(shù)。Π中任意基聚類(lèi)成員Ci∈Π都由若干個(gè)簇構(gòu)成，記作Ci={ci1，ci2，…，ciNi}，其中任一cij∈Ci表示基聚類(lèi)Ci中的第j個(gè)類(lèi)簇，Ci的基數(shù)Ci=Ni表示Ci由Ni個(gè)類(lèi)簇構(gòu)成。Π中的任意基聚類(lèi)Ci∈Π，Cj∈Π，i≠j，則Ci與Cj的基數(shù)可以根據(jù)算法設(shè)計(jì)要求設(shè)定為相同或者不同，即Ni=Nj或者Ni≠Nj。

基聚類(lèi)集成則是使用合適的集成方法對(duì)基聚類(lèi)集合Π進(jìn)行聚合。其聚合過(guò)程可以表示為C′=f（Π），其中一致性函數(shù)f為集成方法，C′為最終聚類(lèi)結(jié)果。對(duì)于集成方法f，常用的有層次聚類(lèi)法、投票法、信息論方法和圖劃分法等方法。

2?基聚類(lèi)三支篩選

基聚類(lèi)是聚類(lèi)集成的基礎(chǔ)，基聚類(lèi)集合的每個(gè)成員Ci∈Π的質(zhì)量對(duì)聚類(lèi)集成結(jié)果都有較大的影響。為了降低低質(zhì)量基聚類(lèi)成員對(duì)聚類(lèi)集成的影響，本章提出了一種基聚類(lèi)成員質(zhì)量評(píng)價(jià)方法，并且采用三支決策的思想構(gòu)造一種基聚類(lèi)成員擇優(yōu)篩選的算法。

2.1?基于信息熵的類(lèi)簇不確定性度量

在信息理論[5]中，信息熵是對(duì)隨機(jī)變量相關(guān)不確定性的度量。在聚類(lèi)集成中給定任一類(lèi)簇cni∈Cn，其中Cn∈Π，則cni中的數(shù)據(jù)對(duì)象有可能在另一個(gè)基聚類(lèi)Cm∈Π中被劃分在Cm多個(gè)簇中。顯然，cni中的數(shù)據(jù)對(duì)象最多可以屬于Cm中的所有Nm個(gè)不同的簇，其中Nm=Cm?；谝陨锨闆r，基于信息熵的類(lèi)簇不確定性度量定義如下。

定義1?在基聚類(lèi)Π中，對(duì)任意cni∈Cn，cmj∈Cm，其中Cn∈Π，Cm∈Π且cni∩cmj≠，則cni相對(duì)于cmj的不確定度量為：

H（cni，cmj）=-p（cni，cmj）lnp（cni，cmj）（1）

其中p（cni，cmj）=|cni∩cmj||cni|。

一組隨機(jī)變量的不確定性通常使用變量的聯(lián)合信息熵[5]來(lái)度量。由于對(duì)于Π任一基聚類(lèi)Cn={ cn1，cn2，…， cnNn} 中的Nn個(gè)類(lèi)簇相互獨(dú)立，因此根據(jù)定義1，Cn中任意一個(gè)類(lèi)簇cni∈Cn相對(duì)于另一個(gè)基聚類(lèi)Cm∈Π的不確定性可計(jì)為cni中元素出現(xiàn)在Cm中各個(gè)類(lèi)簇樣本的概率總和。因此，類(lèi)簇cni相較于基聚類(lèi)Cm的不確定性可定義為：

定義2?給定基聚類(lèi)集合Π，類(lèi)簇cni相對(duì)基聚類(lèi)Cm的不確定性度量為：

Hm（cni）=-∑Nmj=1p（cni，cmj）lnp（cni，cmj）（2）

其中：Nm是Cm中的類(lèi)簇?cái)?shù)，cmj是Cm中第j個(gè)類(lèi)簇。

定義2給出了每個(gè)類(lèi)簇相對(duì)任一基聚類(lèi)的不確定度量形式。對(duì)于i， j，m，p（ci，cmj）∈[0，1]，得到Hm（ci）∈[0，+∞）。當(dāng)ci中的所有數(shù)據(jù)對(duì)象屬于cm的同一簇時(shí)，ci相對(duì)Cm的不確定性達(dá)到其最小值（Hm（ci）=0）。當(dāng)cm的所有簇與ci的交集均不為空集時(shí)，ci相對(duì)Cm的不確定性將達(dá)到最大值。

假定基聚類(lèi)間相互獨(dú)立，cni∈Cn相對(duì)Π的不確定性可以被表示cni相對(duì)Π中所有Π個(gè)基聚類(lèi)的不確定性之和。因此，類(lèi)簇ci相較基聚類(lèi)集合Π的不確定性定義為：

定義3?給定基聚類(lèi)集合Π={C1，C2，…，CM}，任一基聚類(lèi)Cn∈Π的某一類(lèi)簇cni∈Cn相對(duì)Π的不確定性程度計(jì)算如下：

HΠ（cni）=∑Mm=1Hm（cni）（3）

其中M是集合Π中基聚類(lèi)的基數(shù)。

任一類(lèi)簇cni∈Cn相對(duì)集合Π的不確定性能夠反映出聚類(lèi)集成結(jié)果C′中出現(xiàn)類(lèi)簇cni可能性。如果每個(gè)基聚類(lèi)中都存在與cni相同的類(lèi)簇，則可以認(rèn)為cni一定出現(xiàn)C′中，那么cni相對(duì)Π的不確定性達(dá)到其最小值，即HΠ（ci）=0。另外，cni出現(xiàn)在C′的概率隨ci相對(duì)Π的不確定性增大而遞減。

為更好地理解不確定性的求解過(guò)程，下面給出了一個(gè)實(shí)例。其中，3個(gè)基聚類(lèi)組成的集合Π={C1，C2，C3}。C1包含3個(gè)類(lèi)簇{c11，c12，c13}，C2包含4個(gè)類(lèi)簇{c21，c22，c23，c24}，C3包含4個(gè)類(lèi)簇{c31，c32，c33，c34}。每個(gè)類(lèi)簇包含的數(shù)據(jù)對(duì)象見(jiàn)表1。

如表1所示，類(lèi)簇c11包含3個(gè)數(shù)據(jù)對(duì)象，c12包含4個(gè)數(shù)據(jù)對(duì)象，c13包含3個(gè)數(shù)據(jù)對(duì)象。若要計(jì)算C1中3個(gè)類(lèi)簇相對(duì)集合Π的不確定性。則按照以下步驟：

根據(jù)定義1計(jì)算類(lèi)簇ci相對(duì)集合Π中排除自身以外所有類(lèi)簇的不確定性。以類(lèi)簇c13為例，即為計(jì)算c13與集合Π中除其自身以外的10個(gè)類(lèi)簇間的不確定性，即 H（c13，c21）=-p（c13，c21）lnp（c13，c21）=-（2/3）×ln（2/3）≈0.270-3，同理可得H（c13，c22）≈0.366-2，H（c13，c31）≈0.366-2，H（c13，c32）≈0.366-2，H（c13，c33）≈0.366-2。另外，由于c13與c23交集為空，故H（c13，c23）=0，同理可得H（c13，c24）=0，H（c13，c34）=0， H（c13，c11）=0，H（c13，c12）=0。

根據(jù)定義2計(jì)算計(jì)算類(lèi)簇ci相對(duì)集合Π中基聚類(lèi)Cm的不確定性。根據(jù)定義3計(jì)算類(lèi)簇ci相對(duì)集合Π的不確定性， 得到所有類(lèi)簇相對(duì)整個(gè)集合的不確定性，結(jié)果見(jiàn)表2。

表格（有表名）

至此，聚類(lèi)集合Π中任一類(lèi)簇ci∈Π都可以給出對(duì)于Π的不確定性， 但由于各個(gè)基聚類(lèi)的類(lèi)簇個(gè)數(shù)不同，基聚類(lèi)質(zhì)量很難使用聯(lián)合信息熵衡量。為此，一種用基聚類(lèi)類(lèi)簇平均熵來(lái)表示基聚類(lèi)不確定性的方法被提出。

定義4?對(duì)于集合Π中的基聚類(lèi)Cm，約定衡量其不確定性指標(biāo)為基聚類(lèi)類(lèi)簇平均熵Hμ（Cm）。Hμ（Cm）表示基聚類(lèi)Cm中類(lèi)簇對(duì)基聚類(lèi)Cm的不確定性貢獻(xiàn)程度，計(jì)算公式為：

Hμ（Cm）=∑nmi=1HΠ（cmi）/nm（4）

其中： 類(lèi)簇cmi表示基聚類(lèi)Cm中的第i個(gè)類(lèi)簇，nm為基聚類(lèi)Cm中的類(lèi)簇個(gè)數(shù)，HΠ（cmi）表示基聚類(lèi)Cm中類(lèi)簇cmi的熵值。

因此，基聚類(lèi)不確定性可以通過(guò)定義4中的類(lèi)簇平均熵衡量。類(lèi)簇平均熵越大，基聚類(lèi)的不確定性越強(qiáng)，即基聚類(lèi)的質(zhì)量越差; 相反，類(lèi)簇平均熵越小，基聚類(lèi)的不確定性越弱，即基聚類(lèi)的質(zhì)量越好，故類(lèi)簇平均熵可以作為衡量基聚類(lèi)質(zhì)量的度量指標(biāo)。

2.2?面向基聚類(lèi)的三支篩選方法

三支決策思想解決不確定問(wèn)題的過(guò)程符合人類(lèi)正常決策方式思維模式。因此，基于三支決策理論和定義4，用于三支決策的基聚類(lèi)質(zhì)量評(píng)價(jià)函數(shù)λ（Cm）被構(gòu)建，定義為：

定義5?對(duì)于任一基聚類(lèi)Cm∈Π，其基聚類(lèi)篩選三支決策的評(píng)價(jià)函數(shù)為λ（Cm）=e-Hμ（Cm），其中，Hμ（Cm）為聚類(lèi)Cm的類(lèi)簇平均熵。

評(píng)價(jià)函數(shù)λ（Cm）∈（0，1]是類(lèi)簇平均熵Hμ（cmi）∈[0，+∞）的歸一化形式，通過(guò)歸一函數(shù)使得基聚類(lèi)質(zhì)量的度量指標(biāo)符合三支決策域閾值α、 β的判斷范圍，便于三支決策。

對(duì)2.1節(jié)中實(shí)例使用定義5中評(píng)價(jià)函數(shù)λ（Cm）進(jìn)行三支決策。其中計(jì)算方法為：

首先根據(jù)定義4，C1的類(lèi)簇平均熵可計(jì)算為：Hμ（C1）=∑3i=1HΠ（c1i）/3=（1.735-1+1.732-7+1.735-1）/3=1.734-1。同理可得，Hμ（C2）=1.156-3，Hμ（C3）=1.271-9。

其次根據(jù)定義5可得，C1、C2、C3的聚類(lèi)質(zhì)量的三支決策評(píng)價(jià)函數(shù)如表3所示。

由定義4可得，Hμ（cmi）∈[0，+∞），因此用于三支決策的評(píng)價(jià)函數(shù)λ（Cm）∈（0，1]。顯然，當(dāng)基聚類(lèi)Cm的不確定性較小時(shí)，λ（Cm）值更大。當(dāng)基聚類(lèi)Cm的不確定度達(dá)到最小值，即H（Cm）=0時(shí)，其λ（Cm）將達(dá)到最大值，即λ（Cm）=1。當(dāng)基聚類(lèi)不確定性接近無(wú)窮大時(shí)，基聚類(lèi)的λ（Cm）接近0。

基于上述基聚類(lèi)以及三支決策思想，構(gòu)造如下基聚類(lèi)三支篩選方法：

首先設(shè)定基聚類(lèi)質(zhì)量篩選閾值為（α， β），并且0≤β<α≤1，對(duì)任一基聚類(lèi)Cm∈Π，根據(jù)三支評(píng)價(jià)函數(shù)為λ（Cm）進(jìn)行如下三支劃分。

1）若α≤λ（Cm），則將基聚類(lèi)Cm劃分到正域區(qū)間（優(yōu)質(zhì)域），記為Cm∈POS（α， β）（Π）;

2）若λ（Cm）<β，則將基聚類(lèi)Cm劃分到負(fù)域區(qū)間（劣質(zhì)域），記為Cm∈NEG（α， β）（Π）;

3）若β≤（Cm）<α，則將基聚類(lèi)Cm劃分到延遲域區(qū)間（不確定域），記為Cm∈BND（α， β）（Π）。

經(jīng)過(guò)上述三支劃分后可以確定：POS（α， β）（Π）集合中的基聚類(lèi)為高質(zhì)量聚類(lèi)集合;NEG（α， β）（Π）集合中的基聚類(lèi)為低質(zhì)量聚類(lèi)集合;BND（α， β）（Π）集合中的基聚類(lèi)的聚類(lèi)質(zhì)量無(wú)法確定，需要進(jìn)一步判斷決策。

因此本文將保留POS（α， β）（Π）域中的優(yōu)質(zhì)基聚類(lèi)，刪除NEG（α， β）（Π）域中的劣質(zhì)基聚類(lèi)，同時(shí)更新Π=Π-NEG（α， β）（Π）。而對(duì)BND（α， β）（Π）域中的基聚類(lèi)元素，即所有更新后的Π=Π-NEG（α， β）（Π）重新計(jì)算基聚類(lèi)質(zhì)量，并再次三支決策。

通過(guò)上述三支分類(lèi)步驟的多次迭代直至|NEG（α， β）（Π）|=0（NEG（α， β）（Π）中無(wú)元素）或達(dá)到指定迭代次數(shù)，則此時(shí)獲得的Π為最優(yōu)基聚類(lèi)集合。

基于上述面向基聚類(lèi)的三支決策篩選思想可獲得如下算法。

算法?基聚類(lèi)的三支篩選算法（ThreeWay Screening Algorithm，3WDSA）。

輸入?基聚類(lèi)集合Π={C1，C2，…，CM}，迭代次數(shù)R，閾值α、β;

輸出?基聚類(lèi)集合Π。

程序前

1）

for t=1，2，…，R/*對(duì)Π基聚類(lèi)篩選迭代*/

2）

根據(jù)定義2～4計(jì)算Π中所有基聚類(lèi)類(lèi)簇平均熵

3）

for m=1，2，…，|Π|/*對(duì)Π基聚類(lèi)執(zhí)行三支決策*/

4）

根據(jù)定義5計(jì)算聚類(lèi)Cm的評(píng)價(jià)函數(shù)λ（Cm）

5）

if λ（Cm）≥α then

6）

將基聚類(lèi)Cm標(biāo)記為POS（α， β）（Π）域

7）

else if β≤λ（Cm） andλ（Cm）<α then

8）

將基聚類(lèi)Cm標(biāo)記為BND（α， β）（Π）域

9）

else

10）

將基聚類(lèi)Cm標(biāo)記為NEG（α， β）（Π）域

11）

end if

12）

end for

13）

if |NEG（α， β）（Π）| == 0 then

14）

將Π中標(biāo)記為POS（α， β）（Π）域和BND（α， β）（Π）域的基聚類(lèi)合并成新的基聚類(lèi)集合Π

15）

break

16）

end if

17）

刪除Π中標(biāo)記為NEG（α， β）（Π）域的基聚類(lèi)

18）

將Π中標(biāo)記為BND（α， β）（Π）域和POS（α， β）（Π）域的基聚類(lèi)組成基聚類(lèi)集合Π

19）

end for

20）

將基聚類(lèi)集合Π輸出為Π

程序后

3?實(shí)驗(yàn)結(jié)果

本章將使用8組數(shù)據(jù)集對(duì)所提算法進(jìn)行實(shí)驗(yàn)，并通過(guò)2種不同的聚類(lèi)算法評(píng)估指標(biāo)對(duì)聚類(lèi)集成進(jìn)行評(píng)估。本章所有實(shí)驗(yàn)在python3.6環(huán)境下進(jìn)行，其中工作站環(huán)境為Ubuntu18.04lts，Intel i77820X，32GB內(nèi)存，IDE環(huán)境為pyCharm professional 2017.11。

3.1?基數(shù)據(jù)集和評(píng)價(jià)方法

3.1.1?數(shù)據(jù)集與實(shí)驗(yàn)準(zhǔn)備

實(shí)驗(yàn)通過(guò)選取來(lái)自UCI machine learning repositor（http：//archive.ics.uci.edu/ml）的8個(gè)真實(shí)數(shù)據(jù)集，分別是圖像分割（Image Segmentation， IS）、字母識(shí)別（Letter Recognition， LR）、地球資源衛(wèi)星（Landsat Satellite， LS）、筆跡（Pen Digit， PD）、手寫(xiě)數(shù)字識(shí)別（Multiple Features， MF）、光學(xué)數(shù)字識(shí)別（Optical Digit Recognition， ODR）、鋼板故障（Steel Plates Faults， SPF）、紋理（Texture）。上述數(shù)據(jù)集的詳細(xì)描述如表4所示。

3.1.2?評(píng)價(jià)標(biāo)準(zhǔn)

為了合理評(píng)估不同算法的效果，本實(shí)驗(yàn)采用F檢驗(yàn)（Fmeasure）[26]和標(biāo)準(zhǔn)化互信息（Normalized Mutual Information， NMI）[11]兩個(gè)指標(biāo)來(lái)對(duì)聚類(lèi)結(jié)果進(jìn)行評(píng)估。

1）F檢驗(yàn)。

Fmeasure是一種準(zhǔn)確度評(píng)估指標(biāo)?；跀?shù)據(jù)集的標(biāo)準(zhǔn)聚類(lèi)Cg中各類(lèi)簇標(biāo)簽來(lái)計(jì)算某個(gè)被測(cè)試聚類(lèi)C′的準(zhǔn)確度P以及召回率R，并以此來(lái)進(jìn)一步算出F檢驗(yàn)值。

測(cè)試聚類(lèi)C′中類(lèi)簇cj′相對(duì)標(biāo)準(zhǔn)聚類(lèi)Cg中類(lèi)簇cgi的準(zhǔn)確率P和召回率R計(jì)算為：

P（cgi，cj′）=|cgi∩cj′||cj′|（5）

R（cgi，cj′）=|cgi∩cj′||cgi|（6）

其中：cgi為標(biāo)準(zhǔn)聚類(lèi)Cg中擁有第i類(lèi)標(biāo)簽的類(lèi)簇;cj′為聚類(lèi)C′中的第j個(gè)類(lèi)簇。

類(lèi)簇cj′中匹配標(biāo)準(zhǔn)類(lèi)簇cgi的元素的百分比計(jì)算為：

FM（cj′）=2×P（ci，cj′）×R（ci，cj′）P（ci，cj′）+R（ci，cj′）（7）

聚類(lèi)結(jié)果C′相對(duì)標(biāo)準(zhǔn)聚類(lèi)Cg準(zhǔn)確度計(jì)算為：

FM（C′）=∑kj=1FM（cj′）k（8）

其中k為C′的類(lèi)簇?cái)?shù)量C′。

2）標(biāo)準(zhǔn)化互信息。

NMI檢驗(yàn)提供了一組隨機(jī)變量間的信息互通指數(shù)（關(guān)聯(lián)程度），可以通過(guò)NMI 進(jìn)行常規(guī)的聚類(lèi)評(píng)價(jià)。假設(shè)某基數(shù)為τ的數(shù)據(jù)集，若Cg為該數(shù)據(jù)集標(biāo)準(zhǔn)聚類(lèi)，C′為待分析的某個(gè)聚類(lèi)，那么C′相當(dāng)于Cg的NMI指標(biāo)得分公式為：

NMI（C′，Cg）=∑μ′i=1∑μgj=1υijlogυijτωiθj∑μ′i=1ωilogωiτ∑μgj=1θjlogθjτ（9）

其中：μ′為基聚類(lèi)C′中的類(lèi)簇?cái)?shù)量C′，μg為真實(shí)聚類(lèi)Cg中的類(lèi)簇?cái)?shù)量Cg。

ωi為元素出現(xiàn)在聚類(lèi)C′中第i個(gè)類(lèi)簇中元素的基數(shù)ci′，θj為標(biāo)準(zhǔn)聚類(lèi)Cg中第j個(gè)類(lèi)簇中元素的基數(shù)cj′。

另外，υij為基聚類(lèi)C′中第i個(gè)類(lèi)簇和標(biāo)準(zhǔn)聚類(lèi)Cg中第j個(gè)類(lèi)簇中的公共元素個(gè)數(shù)ci′∩cj′。

上述F檢驗(yàn)與NMI指標(biāo)的取值范圍均為[0，1]，且當(dāng)取值越接近1聚類(lèi)算法性能越好。

3.2?對(duì)比實(shí)驗(yàn)分析

本文擬從不同角度設(shè)計(jì)對(duì)比實(shí)驗(yàn)，分析不同算法在數(shù)據(jù)集上的表現(xiàn)。選取k均值（kmeans）、證據(jù)累積聚類(lèi)（Evidence Accumulation Clustering， EAC）[12]、局部加權(quán)證據(jù)累積 （Locally Weighted Evidence Accumulation， LWEA）[27]、局部加權(quán)圖劃分（Locally Weighted Graph Partitioning， LWGP）[27]作為參與對(duì)比的基準(zhǔn)算法。使用本文提出的三支篩選算法（3WDSA）優(yōu)化EAC、LWEA、LWGP得到的3WDSAEAC、3WDSALWEA、3WDSALWGP算法與其他傳統(tǒng)方法kmeans、超圖分割算法（HyperGraph Partitioning Algorithm， HGPA）進(jìn)行對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)迭代次數(shù)R設(shè)置為5，并在閾值α和β的值域[0，1]上分別選取100個(gè)不同的閾值α和β，實(shí)驗(yàn)選取基準(zhǔn)數(shù)據(jù)集為DS1。其中100個(gè)α和100個(gè)β組成的閾值對(duì)（α，β）對(duì)算法影響如圖1所示。

圖1中XOY平面的X軸為自然增長(zhǎng)的α值，Y軸為自然增長(zhǎng)的β值，縱軸為不同閾值下聚類(lèi)集成算法相較于未篩選結(jié)果的提升率。不同閾值調(diào)節(jié)模型產(chǎn)生優(yōu)質(zhì)基礎(chǔ)聚類(lèi)的比率，從而使得最終聚類(lèi)結(jié)果擁有更好的效果。如圖1所示，隨著閾值變化，算法的提升率發(fā)生改變。算法的提升率隨閾值對(duì)的增加而上升，直至達(dá)到最高，隨后算法的提升率隨閾值對(duì)的增加而下降。

閾值α和β在各數(shù)據(jù)集下最佳取值結(jié)果見(jiàn)表5。通過(guò)100輪實(shí)驗(yàn)，最佳閾值在[0，1]中獲得。閾值α和β影響篩選模型的效果，只有取合適閾值時(shí)，提出的三支篩選算法才比基準(zhǔn)算法有更好的促進(jìn)作用。

根據(jù)表5中的數(shù)據(jù)，發(fā)現(xiàn)8個(gè)數(shù)據(jù)集的閾值α約為0.25，閾值β約為0.55， 所以，用該閾值對(duì)進(jìn)行其他的實(shí)驗(yàn)?；谒谢鶞?zhǔn)數(shù)據(jù)集的性能，本文推薦使用閾值α∈[0.20，0.29]和閾值β∈[0.49，0.58]。

為了驗(yàn)證本文提出的三支篩選算法（3WDSA）的有效性，對(duì)比實(shí)驗(yàn)設(shè)計(jì)如下：

1）3WDSAEAC、3WDSALWEA算法與基礎(chǔ)kmeans算法的性能對(duì)比;

2）3WDSAEAC、3WDSALWEA、3WDSALWGP與EAC、LWEA、LWGP、HGPA之間的性能對(duì)比;

最后為了驗(yàn)證不同基聚類(lèi)集合基數(shù)對(duì)3WDSA算法的有效性影響，進(jìn)而實(shí)施第3個(gè)實(shí)驗(yàn)：

3）不同基聚類(lèi)集合基數(shù)M對(duì)3WDSAEAC、3WDSALWEA、3WDSALWGP、EAC、LWEA、LWGP、HGPA算法的影響。

3.2.1?與基聚類(lèi)對(duì)比

為了驗(yàn)證3WDSA對(duì)聚類(lèi)集成算法的提升效果，本節(jié)對(duì)比3WDSAEAC、3WDSALWEA與基礎(chǔ)kmeans等算法的性能得分。實(shí)驗(yàn)方法為，分別使用3WDSAEAC、3WDSALWEA算法運(yùn)行100次實(shí)驗(yàn)數(shù)據(jù)，同時(shí)計(jì)算這100次實(shí)驗(yàn)的NMI得分均值作為算法性能得分; 也分別執(zhí)行了100次基礎(chǔ)kmeans、EAC、LWEA算法，并計(jì)算各自的NMI平均得分作為基準(zhǔn)參考。

實(shí)驗(yàn)結(jié)果如圖2所示， 在所有測(cè)試數(shù)據(jù)集上3WDSAEAC和3WDSALWEA效果顯著優(yōu)于基準(zhǔn)kmeans算法; 特別是3WDSALWEA在所有測(cè)試數(shù)據(jù)集上獲得了最好的NMI均值得分。在對(duì)聚類(lèi)集成算法不友好的SPF數(shù)據(jù)集上，3WDSAEAC和3WDSALWEA的算法表現(xiàn)仍然能夠優(yōu)于基準(zhǔn)kmeans算法，且效果明顯高于基準(zhǔn)EAC和LWEA算法。

3WDSAEAC和3WDSALWEA在LR數(shù)據(jù)集上的NMI均值得分提升效果最為顯著，較基準(zhǔn)EAC和LWEA分別上升了1.12%和1.36%;在IS、LS、PD等數(shù)據(jù)集上，3WDSAEAC和3WDSALWEA在基準(zhǔn)EAC和LWEA上有明顯的效果提升。而在測(cè)試數(shù)據(jù)集MF上，3WDSAEAC和3WDSALWEA比較基準(zhǔn)EAC和LWEA效果提升不明顯。綜上所述，實(shí)驗(yàn)數(shù)據(jù)表明，3WDSA能夠提升聚類(lèi)集成的效果。

3.2.2?與其他聚類(lèi)集成方法對(duì)比

為了進(jìn)一步驗(yàn)證3WDSA在聚類(lèi)集成方法上的提升效果，本節(jié)對(duì)比3WDSAEAC、3WDSALWEA、3WDSALWGP算法與EAC、LWEA、LWGP、HGPA算法之間的聚類(lèi)F檢驗(yàn)與NMI性能得分。其中HGPA為用于衡量對(duì)照組準(zhǔn)確性的算法。

同時(shí)，設(shè)定實(shí)驗(yàn)在基聚類(lèi)基數(shù)M相同的前提下執(zhí)行每個(gè)算法50次，然后計(jì)算平均F檢驗(yàn)和NMI得分。

實(shí)驗(yàn)結(jié)果如表6所示，每個(gè)數(shù)據(jù)集下獲得的最好效果均已加粗顯示。3WDSAEAC、3WDSALWEA、3WDSALWGP在LR數(shù)據(jù)集上平均提升效果最好，Texture數(shù)據(jù)集次之。即使LWEA和LWGP采用了局部權(quán)重策略，一定程度上降低了低質(zhì)量聚類(lèi)對(duì)聚類(lèi)集成的影響，經(jīng)過(guò)3WDSA優(yōu)化的3WDSALWEA和3WDSALWGP算法在各數(shù)據(jù)集上仍有1%～2%的算法效果提升。上述聚類(lèi)效果的提升是因?yàn)?WDSA消除了低質(zhì)量基聚類(lèi)對(duì)聚類(lèi)集成結(jié)果的消極影響，從而提升了高質(zhì)量基聚類(lèi)對(duì)聚類(lèi)集成結(jié)果的積極影響。本實(shí)驗(yàn)進(jìn)一步證明了3WDSA在提升聚類(lèi)集成算法性能上的有效性。

4?結(jié)語(yǔ)

本文提出了一種基聚類(lèi)三支決策篩選方法。該方法在使用信息熵構(gòu)建基聚類(lèi)質(zhì)量度量的基礎(chǔ)上進(jìn)行三支篩選，并且可與任意聚類(lèi)集成算法相融合。通過(guò)多組對(duì)比實(shí)驗(yàn)證明基聚類(lèi)三支篩選方法能夠有效提升經(jīng)典聚類(lèi)集成方法的聚類(lèi)效果。該研究顯示三支決策理論是提升無(wú)監(jiān)督學(xué)習(xí)效果的一種有效策略。

參考文獻(xiàn) （References）

[1]宋敬環(huán). 聚類(lèi)集成算法研究[D]. 哈爾濱： 哈爾濱工程大學(xué)， 2015：1. （SONG J H. Research on clustering ensemble method[D]. Harbin： Harbin Engineering University， 2015： 1）.

[2]STREHL A， GHOSH J. Cluster ensembles： a knowledge reuse framework for combining partitionings[J]. Journal of Machine Learning Research， 2003， 3（3）： 583-617.

[3]YU Z， LI L， LIU J， et al. Adaptive noise immune cluster ensemble using affinity propagation[J]. IEEE Transactions on Knowledge and Data Engineering， 2015，27（12）： 3176-3189.

[4]HUANG D， LAI J， WANG C. Combining multiple clusterings via crowd agreement estimation and multigranularity link analysis[J]. Neurocomputing， 2015， 170： 240-250.

[5]YANG Y. Elements of information theory[J]. Journal of the American Statistical Association， 2008， 103（3）： 429-429.

[6]IAMON N， BOONGOEN T， GARRETT S， et al. A linkbased approach to the cluster ensemble problem[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2011， 33（12）： 2396-2409.

[7]WANG T. CATree： a hierarchical structure for efficient and scalable coassociationbased cluster ensembles[J]. IEEE Transactions on Systems， Man， and Cybernetics， Part B： Cybernetics， 2011， 41（3）： 686-698.

[8]TUMER K， AGOGINO A K. Ensemble clustering with voting active clusters[J]. Pattern Recognition Letters， 2008， 29（14）：1947-1953.

[9]董彩云， 杜韜， 郭春燕，等. 聚類(lèi)后的關(guān)聯(lián)規(guī)則快速更新算法研究[J]. 計(jì)算機(jī)應(yīng)用研究， 2004， 21（11）： 30-32.（DONG C Y， DU T， GUO C Y， et al. Research on fast adapting algorithm of association rules after clustering[J]. Application Research of Computers， 2004， 21（11）： 30-32.）

[10]TOPCHY A， JAIN A K， PUNCH W. Clustering ensembles： models of consensus and weak partitions [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2005， 27（12）：1866-1881.

[11]STREHL A， GHOSH J. Cluster ensembles： a knowledge reuse framework for combining multiple partitions [J]. Journal of Machine Learning Research， 2002， 3： 583-617.

[12]FRED A L， JAIN A K. Combining multiple clusterings using evidence accumulation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2005， 27（6）： 835-850.

[13]FERN X Z， BRODLEY C E. Random projection for high dimensional data clustering： a cluster ensemble approach[C]// Proceedings of the 20th International Conference on Machine Learning. Palo Alto： AAAI Press， 2003： 187-192.

[14]KUNCHEVA L I， VETRO D P. Evaluation of stability ofkmeans cluster ensembles with respect to random initialization[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2006， 28（11）：1798-1808.

[15]MINAEIBIDGOLI B， TOPCHY A， PUNCH W F. Ensembles of partitions via data resampling[C]// Proceedings of the 2004 International Conference on Information Technology： Coding and Computing. Washington， DC： IEEE Computer Society， 2004： 188-192.

[16]DUDOIT S， FRIDLYAND J. Bagging to improve the accuracy of a clustering procedure[J]. Bioinformatics， 2003， 19（9）： 1090-1099.

[17]YANG Y， JIANG J. Hybrid samplingbased clustering ensemble with global and local constitutions[J]. IEEE Transactions on Neural Networks and Learning Systems， 2017， 27（5）： 952-965.

[18]ZHOU P， DU L， WANG H， et al. Learning a robust consensus matrix for clustering ensemble via KullbackLeibler divergence minimization[C]// Proceedings of the 24th International Conference on Artificial Intelligence. Palo Alto： AAAI Press， 2015： 4112-4118.

[19]YU Z， LUO P， YOU J， et al. Incremental semisupervised clustering ensemble for high dimensional data clustering[J]. IEEE Transactions on Knowledge and Data Engineering， 2016， 28（3）：701-714.

[20]YAO Y. An outline of a theory of threeway decisions[C]// Proceedings of the 8th International Conference on Rough Sets and Current Trends in Computing. Heidelberg： Springer， 2012：1-17.

[21]WANG L， MIAO D， ZHAO C. Chinese emotion recognition based on threeway decisions[C]// Proceedings of the 10th International Conference on Rough Sets and Knowledge Technology. Heidelberg： Springer， 2015：299-308.

[22]XU J， MIAO D， ZHANG Y， et al. A threeway decisions model with probabilistic rough sets for stream computing[J]. International Journal of Approximate Reasoning， 2017， 88： 1-22.

[23]LI W， XU W H. Doublequantitative decisiontheoretic rough set[J]. Information Sciences， 2015， 316： 54-67.

[24]QIAN Y， ZHANG H， SANG Y， et al. Multigranulation decisiontheoretic rough sets[J]. International Journal of Approximate Reasoning， 2014， 55（1） ：225-237.

[25]苗奪謙， 徐菲菲， 姚一豫，等. 粒計(jì)算的集合論描述[J]. 計(jì)算機(jī)學(xué)報(bào)， 2012， 35（2）：351-363.（MIAO D Q， XU F F， YAO Y Y， et al. Settheoretic formulation of granular computing[J]. Chinese Journal of Computers， 2012， 35（2）： 351-363.）

[26]ABUALIGAH L M， KHADER A T， ALBETAR M A， et al. Text feature selection with a robust weight scheme and dynamic dimension reduction to text document clustering[J]. Expert Systems with Applications， 2017， 84（C）：24-36.

[27]HUANG D， WANG C， LAI J. Locally weighted ensemble clustering[J]. IEEE Transactions on Cybernetics， 2016， 48（5）：1460-1473.

This work is partially supported by the National Natural Science Foundation of China （61763031， 61673301）， the National Key Research and Development Program of China （213）.

XU Jianfeng， born in 1973， Ph. D.， professor. His research interests include granular computing， rough set， threeway decision， deep learning， ensemble clustering.

ZOU Weikang， born in 1995， M. S. candidate. His research interests include granular computing， rough set， threeway decision， ensemble clustering.

LIANG Wei， born in 1993， M. S. candidate. His research interests include machine learning， granular computing， rough set， threeway decision， deep learning， ensemble clustering.

CHENG Gaojie， born in 1985， M. S.， lecturer. Her research interests include granular computing， rough set， machine learning， ensemble clustering.

ZHANG Yuanjian， born in 1990， Ph. D. candidate. His research interests include granular computing， threeway decision， multilabel learning.