一種用于中醫(yī)四診分析的子空間聚類方法

許立輝，陳 敏，王池社

(1.常州市中醫(yī)醫(yī)院,江蘇 常州 213003； 2.金陵科技學(xué)院網(wǎng)絡(luò)與通信工程學(xué)院,江蘇 南京 211169；3.安徽理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,安徽 淮南 232001)

0 引 言

中醫(yī)的證候分類研究是中醫(yī)辨證施治的核心，具有重要的研究價(jià)值和臨床應(yīng)用意義[1]。一般來說，中醫(yī)的證候分類研究是基于中醫(yī)的四診信息開展的。研究通常將常用的各類臨床癥狀分成望、聞、問、切4類標(biāo)準(zhǔn)四診信息庫，再對(duì)采集到的病例樣本按四診信息進(jìn)行量化處理后，采用不同的計(jì)算機(jī)方法進(jìn)行證候提取與分析，從而為各類臨床病例提供輔助診療。

目前有很多機(jī)器學(xué)習(xí)方法應(yīng)用于中醫(yī)的證候分類研究[2]。聚類作為一種重要的無監(jiān)督學(xué)習(xí)方法，它可以有效分析數(shù)據(jù)中隱藏的類簇信息，也被廣泛應(yīng)用于中醫(yī)的證候分類研究[3]。但是，傳統(tǒng)的聚類方法在高維數(shù)據(jù)集上進(jìn)行聚類分析時(shí)，其距離計(jì)算由于樣本數(shù)據(jù)分布的稀疏性而無法基于距離來構(gòu)建簇。中醫(yī)證候分類研究中四診量化數(shù)據(jù)維度由幾十維到幾百維不等，對(duì)于這些高維數(shù)據(jù)的聚類分析無法實(shí)現(xiàn)有效挖掘。本文在對(duì)比各類聚類方法的基礎(chǔ)上，結(jié)合中醫(yī)證候分類研究的四診數(shù)據(jù)集高維的特點(diǎn)，基于子空間聚類CLIQUE算法提出了限定空間搜索策略的改進(jìn)CLIQUE算法(ChM-CLIQUE)，實(shí)驗(yàn)結(jié)果表明了本文方法的有效性。

1 子空間聚類

子空間聚類[4]是聚類算法中的一種，它通過特征選擇在不同子空間數(shù)據(jù)集中進(jìn)行聚類。其算法的核心是將搜索在子空間特征維度中進(jìn)行，它可以有效地降低待處理數(shù)據(jù)的維度而提高聚類的效果，已經(jīng)被廣泛應(yīng)用于高維數(shù)據(jù)的聚類信息挖掘，如圖像處理、人臉識(shí)別等領(lǐng)域。

針對(duì)子空間聚類本身存在的特點(diǎn)，很多研究者提出了提高聚類性能的算法。將子空間聚類方法應(yīng)用于多聚類問題[5]，可以有效提升高維數(shù)據(jù)的聚類性能；Geng等人[6]針對(duì)分布式聚類問題中的高維數(shù)據(jù)在聚類過程中形成的維度災(zāi)難問題，提出了一種新的局部密度子空間分布式聚類算法；Zhong等人[7]基于圖的子空間聚類方法，提出了一種改進(jìn)的自適應(yīng)親和度矩陣(affinity matrix)方法提高聚類性能；Lakshmi等人[8]提出了一種基于興趣的子空間聚類算法，他們采用粗糙集理論中的屬性依賴來度量子空間，有效解決了子空間聚類的規(guī)模隨著維度的增長而呈指數(shù)級(jí)擴(kuò)展問題；Xue等人[9]基于低秩核方法，提出了一種基于非凸低秩逼近和自適應(yīng)核的子空間聚類方法，有效解決了數(shù)據(jù)中的奇異值問題。Wang等人[10]提出了一種快速自適應(yīng)K均值型子空間聚類模型，從而適用于不同分布下的數(shù)據(jù)集聚類。

子空間聚類的應(yīng)用研究方面，Liu等人[11]將子空間聚類應(yīng)用于信用風(fēng)險(xiǎn)評(píng)估，有效解決了信用數(shù)據(jù)集高維、類別不平衡問題；Guo等人[12]將子空間聚類應(yīng)用于癌癥的亞型識(shí)別取得了較好的結(jié)果；Zhou等人[13]提出了一種基于稀疏子空間聚類算法的社區(qū)檢測(cè)新方法，以解決在線社交網(wǎng)絡(luò)中稀疏性和短文本的高維性問題；Zhang等人[14]采用稀疏子空間聚類算法進(jìn)行出租車運(yùn)營模式發(fā)現(xiàn)；Abdolali等人[15]采用子空間聚類算法有效處理圖像數(shù)據(jù)中的去噪問題。

2 ChM-CLIQUE方法

2.1 CLIQUE算法

CLIQUE算法是一種經(jīng)典的基于網(wǎng)格的子空間聚類算法[16]，主要用于發(fā)現(xiàn)子空間中基于密度的簇。經(jīng)典的CLIQUE聚類算法過程如下：

1)將m維數(shù)據(jù)集劃分為互不相交的網(wǎng)格單元gij，這里面的網(wǎng)格單元如定義1描述。

定義1網(wǎng)格單元。令DS={D1,D2,…,Dm}表示m維數(shù)據(jù)集，每一個(gè)互不相交的子空間數(shù)據(jù)集記為gij(其中i表示第i個(gè)子空間，j表示該子空間的第j維元素)，稱之為網(wǎng)格單元。

2)計(jì)算每個(gè)網(wǎng)格單元的密度，網(wǎng)格密度如定義2。

定義2網(wǎng)格密度。對(duì)于每個(gè)網(wǎng)格單元gij,令投影到該網(wǎng)格單元中數(shù)據(jù)點(diǎn)的個(gè)數(shù)為該網(wǎng)格單元的密度，用dij表示網(wǎng)格單元gij的密度值。

3)根據(jù)設(shè)定的密度閾值來篩選稠密單元。篩選的策略是從任意稠密單元開始，根據(jù)深度優(yōu)先搜索策略來聚集鄰接的稠密單元來生成聚類簇。當(dāng)所有稠密單元都被遍歷時(shí)，算法終止。稠密單元如定義3。

定義3稠密單元。根據(jù)預(yù)先設(shè)置的密度閾值參數(shù)ε，若網(wǎng)格密度dij>ε,則判定網(wǎng)格單元gij為稠密單元，反之gij為非稠密單元。

2.2 基于限定空間的搜索策略

經(jīng)典的CLIQUE算法，其搜索稠密單元的策略為基于任意發(fā)現(xiàn)的第一個(gè)稠密單元進(jìn)行深度優(yōu)先搜索，搜索過程具有盲目性，算法時(shí)間復(fù)雜度高；其密度閾值和網(wǎng)格步長為預(yù)先設(shè)定，對(duì)于聚類簇的邊界網(wǎng)格單元識(shí)別精度較低[17]。

針對(duì)上述問題，本文提出了基于限定空間的搜索策略方法進(jìn)行算法性能改進(jìn)。方法主要包括2個(gè)部分的內(nèi)容：1)將搜索策略調(diào)整為以稠密單元中網(wǎng)格密度最大的單元為中心進(jìn)行深度優(yōu)先搜索生成聚類簇；2)基于聚類簇中樣本高斯分布的特性[18]引入網(wǎng)格自適應(yīng)密度這一概念，通過網(wǎng)格自適應(yīng)密度計(jì)算來增強(qiáng)聚類邊界的識(shí)別精度。

方法中，選擇深度優(yōu)先搜索的起點(diǎn)為稠密單元中網(wǎng)格密度最大的單元，本文定義其為稠密中心網(wǎng)格如定義4。

定義4稠密中心網(wǎng)格。第i維稠密單元的稠密中心網(wǎng)格記為gic：

gic={gik|gik=max(dij)}

其中g(shù)ik為第i維網(wǎng)格密度最大的稠密單元。

一般來說，對(duì)于聚類效果較好的聚類分布，每個(gè)簇中的樣本點(diǎn)密集地分布在簇中心，而邊緣一般比較稀疏[19]，這一特性符合高斯分布的特性。本文通過引入網(wǎng)格自適應(yīng)密度計(jì)算代替密度閾值和網(wǎng)格步長的預(yù)先設(shè)定方法，增強(qiáng)聚類邊界的識(shí)別精度。

網(wǎng)格自適應(yīng)密度計(jì)算公式見定義5。

定義5網(wǎng)格自適應(yīng)密度。定義ρij為自適應(yīng)因子優(yōu)化之后網(wǎng)格單元gij的密度，稱之為網(wǎng)格自適應(yīng)密度：

其中：

λij定義為網(wǎng)格單元密度自適應(yīng)因子，計(jì)算如下：

f(dij)為網(wǎng)格單元gij中的概率密度函數(shù)，其計(jì)算公式如定義6；n為網(wǎng)格單元數(shù)。

定義6概率密度函數(shù)。定義f(x)為樣本點(diǎn)x的概率密度函數(shù)如下：

其中：μ為均值，σ為標(biāo)準(zhǔn)差，σ2為方差。

根據(jù)上述定義的網(wǎng)格自適應(yīng)密度值，按下式判別稠密單元和非稠密單元：

2.3 ChM-CLIQUE算法描述

ChM-CLIQUE算法以CLIQUE算法為基礎(chǔ)，通過搜索策略的優(yōu)化提升算法的效率。算法流程描述如下：

1)將m維數(shù)據(jù)集劃分為互不相交的網(wǎng)格單元gij，生成網(wǎng)格單元。

2)計(jì)算每個(gè)網(wǎng)格單元的密度dij并進(jìn)行降序排序，記下稠密中心網(wǎng)格gic。

3)通過計(jì)算網(wǎng)格自適應(yīng)密度來識(shí)別是否為稠密單元格，并且從每一維度的網(wǎng)格單元密度最大的中心稠密單元開始深度優(yōu)先遍歷生成聚類簇。

經(jīng)典的CLIQUE算法在識(shí)別稠密網(wǎng)格單元時(shí)，忽視了樣本分布的特性，將聚類邊界的非稠密單元中的數(shù)據(jù)點(diǎn)作為噪點(diǎn)進(jìn)行處理，導(dǎo)致聚類的精度低。本文引進(jìn)網(wǎng)格單元的自適應(yīng)密度ρij，可以有效地解決將聚類邊界誤判為噪點(diǎn)的問題，從而提高聚類的效率。ChM-CLIQUE算法偽代碼見算法1。

算法1ChM-CLIQUE算法

輸入：DS，step，ε

輸出：ChM-CLIQUE算法結(jié)果clusters

1.grid=createGrid(DS,step);

//根據(jù)DS生成網(wǎng)格單元

2.grid_den=calDensity(grid);//計(jì)算網(wǎng)格密度

3.grid_sort=sortByDensity(grid_den);

//根據(jù)網(wǎng)格單元密度進(jìn)行降序排序

4.create clusters and set clusterNo=0;

//生成聚類簇結(jié)果集合

5.for i=1 to grid_sort.length:

6.clusterNo++;

//標(biāo)記新簇

7.if(grid_sort[i]=0) then

//判斷grid_sort[i]是否被“訪問”，0為“未訪問”

8.if(dense(grid_sort[i])>ε) then

//判斷grid_sort[i]是否為稠密單元

9.cluster.add(grid_sort[i]);//將稠密單元加入當(dāng)前聚類集合中

10.dfsSearching grid_sort[i];//從grid_sort[i]繼續(xù)dfs遍歷

11.end if

12.grid_sort[i]=1;//標(biāo)記grid_sort[i]為“已訪問”

13.end if

14.clusters.add(cluster);//將當(dāng)前簇加入聚類簇結(jié)果集合

15.end for

16.return clusers;//返回聚類的結(jié)果集合

3 實(shí)驗(yàn)結(jié)果及分析

為了檢驗(yàn)ChM-CLIQUE算法的聚類效果，本文在中醫(yī)臨床采集數(shù)據(jù)集上進(jìn)行多組對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)所采用計(jì)算機(jī)的硬件為Intel(R) Core(TM) i5-5200U CPU @ 2.20 GHz，內(nèi)存8 GB，操作系統(tǒng)為Windows 10 64位操作系統(tǒng)，算法實(shí)現(xiàn)采用Python語言。

為了評(píng)估聚類算法的有效性，聚類結(jié)果的性能評(píng)價(jià)指標(biāo)采用輪廓系數(shù)(Silhouette Coefficient)[20]，輪廓系數(shù)結(jié)合內(nèi)聚度和分離度2種因素，輪廓系數(shù)取值范圍為[-1,1]，取值越接近1則說明聚類性能越好，相反，取值越接近-1則說明聚類性能越差。

3.1 數(shù)據(jù)準(zhǔn)備

本次應(yīng)用實(shí)驗(yàn)，采用臨床采集的患者四診變量的數(shù)據(jù)集(簡稱數(shù)據(jù)集DM)。數(shù)據(jù)集DM包含82個(gè)樣本，每個(gè)樣本包含1280個(gè)特征。82個(gè)樣本為中醫(yī)領(lǐng)域的四診變量，1280個(gè)特征為1280個(gè)患者在這82個(gè)四診變量上的程度取值情況，通過聚類分析來挖掘這82個(gè)四診變量內(nèi)部的關(guān)聯(lián)性。而對(duì)于數(shù)據(jù)集DM這種82個(gè)樣本、1280維特征的數(shù)據(jù)集，存在“維度災(zāi)難”[21]的問題，基本不可能在1280維上產(chǎn)生有效的聚類結(jié)果，高維數(shù)據(jù)可采用降維方法如主成分分析(PCA)[22]，但會(huì)導(dǎo)致數(shù)據(jù)信息丟失，無法形成有效聚類，故采用改進(jìn)的子空間聚類算法ChM-CLIQUE算法進(jìn)行聚類。

數(shù)據(jù)集DM格式如表1所示，四診變量為樣本，共計(jì)82個(gè)，四診程度為四診變量所對(duì)應(yīng)的特征，共計(jì)1280個(gè)特征，每個(gè)特征取值為1、2、3、4，代表無、輕、中、重4個(gè)等級(jí)，DM數(shù)據(jù)集如表1所示。

表1 DM數(shù)據(jù)集的數(shù)據(jù)結(jié)構(gòu)內(nèi)容

3.2 聚類結(jié)果分析

在數(shù)據(jù)集DM上進(jìn)行2組對(duì)比分析實(shí)驗(yàn),其中第一組對(duì)比分析實(shí)驗(yàn)采用了傳統(tǒng)的CLIQUE算法,第二組實(shí)驗(yàn)采用了改進(jìn)的ChM-CLIQUE算法，因?yàn)镃LIQUE算法對(duì)于密度閾值和網(wǎng)格步長參數(shù)比較敏感，所以對(duì)于每組實(shí)驗(yàn)分別進(jìn)行多次實(shí)驗(yàn)。結(jié)果如表2所示。

表2 2組實(shí)驗(yàn)的聚類結(jié)果分析表

對(duì)于ChM-CLIQUE算法，優(yōu)化了搜索策略，并且增強(qiáng)了聚類邊界的精度，可以從表2看到ChM-CLIQUE算法實(shí)驗(yàn)的輪廓系數(shù)要高于CLIQUE算法的，并且耗時(shí)要更短。不同實(shí)驗(yàn)下的輪廓系數(shù)如圖1所示。

圖1 各實(shí)驗(yàn)輪廓系數(shù)比較

不同實(shí)驗(yàn)下，CLIQUE算法實(shí)驗(yàn)與ChM_CLIQUE算法實(shí)驗(yàn)耗時(shí)如圖2所示。

圖2 各實(shí)驗(yàn)耗時(shí)比較

為了檢驗(yàn)2種算法在不同規(guī)模的數(shù)據(jù)集的實(shí)際運(yùn)行時(shí)間，對(duì)數(shù)據(jù)集DM進(jìn)行數(shù)據(jù)增強(qiáng)操作，構(gòu)造出不同規(guī)模的數(shù)據(jù)集，原始的數(shù)據(jù)集DM包含82個(gè)示例，通過數(shù)據(jù)增強(qiáng)分別構(gòu)造出1000、2000、3000、4000、5000樣本量的數(shù)據(jù)集，讓CLIQUE和ChM-CLIQUE分別在這些數(shù)據(jù)集上進(jìn)行對(duì)比實(shí)驗(yàn)，比較實(shí)際運(yùn)行時(shí)間。不同數(shù)據(jù)規(guī)模情況下，CLIQUE算法實(shí)驗(yàn)與ChM_CLIQUE算法實(shí)驗(yàn)耗時(shí)如圖3所示。

圖3 2種算法在不同規(guī)模數(shù)據(jù)集上的運(yùn)行時(shí)間

在數(shù)據(jù)集DM上進(jìn)行2組對(duì)比實(shí)驗(yàn)和不同規(guī)模數(shù)據(jù)集實(shí)驗(yàn)中可以看出，ChM-CLIQUE算法相對(duì)于CLIQUE算法在效率和精確度上都有了一定的提高。

其次使用專家知識(shí)作為外部指標(biāo)[23]來對(duì)比CLIQUE和ChM-CLIQUE算法在數(shù)據(jù)集DM上聚類的結(jié)果。根據(jù)CLIQUE算法聚類出的結(jié)果如表3所示，根據(jù)ChM-CLIQUE算法聚類出的結(jié)果如表4所示。

表3 CLIQUE算法聚類結(jié)果

表4 ChM-CLIQUE算法聚類結(jié)果

從中醫(yī)專家知識(shí)的角度出發(fā)，對(duì)于CLIQUE算法和ChM-CLIQUE算法在臨床采集患者四診變量的數(shù)據(jù)集上面進(jìn)行聚類，ChM-CLIQUE算法聚類的結(jié)果更加貼近實(shí)際，也較為符合中醫(yī)領(lǐng)域?qū)＜业膭澐忠?guī)則。

4 結(jié)束語

基于限定空間搜索策略的ChM-CLIQUE算法針對(duì)傳統(tǒng)CLIQUE算法存在的搜索稠密網(wǎng)格單元效率低，以及對(duì)于聚類的邊界網(wǎng)格單元識(shí)別精度低的問題進(jìn)行優(yōu)化。ChM-CLIQUE算法對(duì)每一維的稠密單元的網(wǎng)格密度進(jìn)行排序，確定每一維中網(wǎng)格密度最大的稠密單元，以此稠密單元為中心網(wǎng)格進(jìn)行深度優(yōu)先搜索生成聚類簇，避免CLIQUE算法“盲目”搜索，提高了算法的性能；對(duì)于識(shí)別聚類的邊界網(wǎng)格單元，ChM-CLIQUE算法基于聚類簇中樣本高斯分布的特性提出網(wǎng)格自適應(yīng)密度，增強(qiáng)聚類邊界的識(shí)別精度。本文通過多組算法實(shí)驗(yàn)和應(yīng)用實(shí)驗(yàn)，分析ChM-CLIQUE算法與傳統(tǒng)的CLIQUE算法的時(shí)間復(fù)雜度和聚類的效果，算法實(shí)驗(yàn)采用輪廓系數(shù)作為聚類的性能評(píng)價(jià)指標(biāo)，表明ChM-CLIQUE算法相比于CLIQUE算法在時(shí)間復(fù)雜度和聚類效果上都有較為明顯的改善。