許立輝，陳 敏，王池社

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

0 引 言

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

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

1 子空間聚類

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

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

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

2 ChM-CLIQUE方法

2.1 CLIQUE算法

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

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

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

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

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

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

定義3稠密單元。根據預先設置的密度閾值參數ε，若網格密度dij>ε,則判定網格單元gij為稠密單元，反之gij為非稠密單元。

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

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

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

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

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

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

其中gik為第i維網格密度最大的稠密單元。

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

網格自適應密度計算公式見定義5。

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

其中：

λij定義為網格單元密度自適應因子，計算如下：

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

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

其中：μ為均值，σ為標準差，σ2為方差。

根據上述定義的網格自適應密度值，按下式判別稠密單元和非稠密單元：

2.3 ChM-CLIQUE算法描述

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

1)將m維數據集劃分為互不相交的網格單元gij，生成網格單元。

2)計算每個網格單元的密度dij并進行降序排序，記下稠密中心網格gic。

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

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

算法1ChM-CLIQUE算法

輸入：DS，step，ε

輸出：ChM-CLIQUE算法結果clusters

1.grid=createGrid(DS,step);

//根據DS生成網格單元

2.grid_den=calDensity(grid);//計算網格密度

3.grid_sort=sortByDensity(grid_den);

//根據網格單元密度進行降序排序

4.create clusters and set clusterNo=0;

//生成聚類簇結果集合

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);//將當前簇加入聚類簇結果集合

15.end for

16.return clusers;//返回聚類的結果集合

3 實驗結果及分析

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

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

3.1 數據準備

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

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

表1 DM數據集的數據結構內容

3.2 聚類結果分析

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

表2 2組實驗的聚類結果分析表

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

圖1 各實驗輪廓系數比較

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

圖2 各實驗耗時比較

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

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

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

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

表3 CLIQUE算法聚類結果

表4 ChM-CLIQUE算法聚類結果

從中醫(yī)專家知識的角度出發(fā)，對于CLIQUE算法和ChM-CLIQUE算法在臨床采集患者四診變量的數據集上面進行聚類，ChM-CLIQUE算法聚類的結果更加貼近實際，也較為符合中醫(yī)領域專家的劃分規(guī)則。

4 結束語

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