許立輝，陳 敏，王池社

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

0 引 言

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

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

1 子空間聚類

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

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

子空間聚類的應(yīng)用研究方面，Liu等人[11]將子空間聚類應(yīng)用于信用風險評估，有效解決了信用數(shù)據(jù)集高維、類別不平衡問題；Guo等人[12]將子空間聚類應(yīng)用于癌癥的亞型識別取得了較好的結(jié)果；Zhou等人[13]提出了一種基于稀疏子空間聚類算法的社區(qū)檢測新方法，以解決在線社交網(wǎng)絡(luò)中稀疏性和短文本的高維性問題；Zhang等人[14]采用稀疏子空間聚類算法進行出租車運營模式發(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ù)集，每一個互不相交的子空間數(shù)據(jù)集記為gij(其中i表示第i個子空間，j表示該子空間的第j維元素)，稱之為網(wǎng)格單元。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

其中：

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

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

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

其中：μ為均值，σ為標準差，σ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)計算每個網(wǎng)格單元的密度dij并進行降序排序，記下稠密中心網(wǎng)格gic。

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

經(jīng)典的CLIQUE算法在識別稠密網(wǎng)格單元時，忽視了樣本分布的特性，將聚類邊界的非稠密單元中的數(shù)據(jù)點作為噪點進行處理，導致聚類的精度低。本文引進網(wǎng)格單元的自適應(yīng)密度ρij，可以有效地解決將聚類邊界誤判為噪點的問題，從而提高聚類的效率。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);//計算網(wǎng)格密度

3.grid_sort=sortByDensity(grid_den);

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

4.create clusters and set clusterNo=0;

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

5.for i=1 to grid_sort.length:

6.clusterNo++;

//標記新簇

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]);//將稠密單元加入當前聚類集合中

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

11.end if

12.grid_sort[i]=1;//標記grid_sort[i]為“已訪問”

13.end if

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

15.end for

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

3 實驗結(jié)果及分析

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

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

3.1 數(shù)據(jù)準備

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

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

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

3.2 聚類結(jié)果分析

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

表2 2組實驗的聚類結(jié)果分析表

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

圖1 各實驗輪廓系數(shù)比較

不同實驗下，CLIQUE算法實驗與ChM_CLIQUE算法實驗耗時如圖2所示。

圖2 各實驗耗時比較

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

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

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

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

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

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

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

4 結(jié)束語

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