基于耦合度量的多尺度聚類挖掘方法

田真真，趙書良，李文斌，張璐璐，陳潤資

（1. 河北師范大學(xué)計算機(jī)與網(wǎng)絡(luò)空間安全學(xué)院，石家莊，050024；2. 河北師范大學(xué)河北省供應(yīng)鏈大數(shù)據(jù)分析與數(shù)據(jù)安全工程研究中心，石家莊，050024；3. 河北師范大學(xué)河北省網(wǎng)絡(luò)與信息安全重點(diǎn)實(shí)驗(yàn)室，石家莊，050024；4. 河北地質(zhì)大學(xué)信息工程學(xué)院，石家莊，050031；5.河北師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，石家莊，050024）

引 言

多尺度聚類是多尺度研究方法的一種，旨在根據(jù)不同的分辨率，從不同的尺度將一堆無標(biāo)簽的物理或抽象對象分成由相似對象組成的簇，在數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)[1-2]、計算機(jī)視覺、圖像處理和信息檢索任務(wù)中應(yīng)用較為廣泛。這些簇中的對象與本簇中的對象相似，與其他簇中的對象相異，國內(nèi)外學(xué)者根據(jù)多尺度聚類的這一特性作了一系列研究。國內(nèi)方面，文獻(xiàn)[3]結(jié)合關(guān)聯(lián)規(guī)則和概念分層理論，提出了一種基于關(guān)聯(lián)規(guī)則的多尺度挖掘方法；文獻(xiàn)[4]在文本豐富的多維數(shù)據(jù)集中，根據(jù)關(guān)鍵字搜索提出了一種基于隨即投影和哈希索引結(jié)構(gòu)的新方法ProMiSH，為許多新的應(yīng)用程序和工具提供了便利；文獻(xiàn)[5]將粒計算的概念引入到多尺度數(shù)據(jù)挖掘中，并利用斑塊模型進(jìn)行尺度轉(zhuǎn)換，提出多尺度聚類尺度上推算法；文獻(xiàn)[6]結(jié)合非參數(shù)密度估計方法，提出了一種基于多尺度信息融合的層次聚類算法，該算法能夠有效解決具有流形結(jié)構(gòu)的數(shù)據(jù)集中局部噪聲問題；文獻(xiàn)[7]將多尺度對象同像素聯(lián)合起來，提出了利用譜聚類對高空間分辨率遙感影像進(jìn)行分割的方法。國外方面，文獻(xiàn)[8]通過對加拿大魁北克南部萊姆病發(fā)生區(qū)不同空間尺度上肩胛若蟲分布的聚類分析，幫助人們了解風(fēng)險變化并采取相應(yīng)措施；文獻(xiàn)[9]通過區(qū)域化算法，提出了一種基于多尺度自舉重采樣的平均聯(lián)動層次聚類算法，對非平穩(wěn)降水時間序列的均勻降水區(qū)進(jìn)行識別；文獻(xiàn)[10]提出了一種多尺度高斯核誘導(dǎo)模糊C 均值算法，對病變進(jìn)行分割以確定病變邊緣。

從目前的研究情況來看，多尺度聚類已經(jīng)在各個學(xué)科領(lǐng)域得到廣泛研究；但從數(shù)據(jù)集的屬性類型進(jìn)行分析，大多數(shù)的研究只是針對數(shù)值型數(shù)據(jù)集，對數(shù)據(jù)進(jìn)行定量的分析與預(yù)測，而對分類屬性型數(shù)據(jù)集（簡稱為分類型數(shù)據(jù)集）進(jìn)行定性分析研究的工作很少。分類型數(shù)據(jù)集大多用字符表示屬性值，不具有數(shù)的大部分性質(zhì)，即便使用數(shù)（整數(shù)）表示，也應(yīng)當(dāng)作符號，不能進(jìn)行定量分析。對分類型數(shù)據(jù)集進(jìn)行研究，不僅需要獲取復(fù)雜的數(shù)據(jù)特征，還需要所提出的方法具有一定的靈活性。

針對存在的問題，本文的主要貢獻(xiàn)有：（1）引入最新提出的無監(jiān)督耦合度量相似性方法，提出基于耦合度量的多尺度聚類挖掘方法，對具有多尺度特性的分類型數(shù)據(jù)集進(jìn)行基準(zhǔn)尺度聚類，得到基準(zhǔn)尺度聚類結(jié)果；（2）結(jié)合尺度轉(zhuǎn)換理論以及凝聚層次聚類思想，提出基于單鏈的尺度上推算法，對基準(zhǔn)尺度的聚類結(jié)果進(jìn)行尺度轉(zhuǎn)換，進(jìn)而得到目標(biāo)尺度聚類結(jié)果；（3）將尺度轉(zhuǎn)換理論與蘭索斯(Lanczos)插值思想相結(jié)合，并根據(jù)分裂層次聚類思想，提出基于Lanczos 核的尺度下推算法，對非獨(dú)立同分布的分類型數(shù)據(jù)集進(jìn)行多尺度聚類尺度下推。

1 耦合度量相似性

耦合度量相似性（Couple metric similarity，CMS）是一種主要用于非獨(dú)立同分布的無監(jiān)督分類型數(shù)據(jù)集的相似性度量方法[11]。已經(jīng)存在的度量分類型數(shù)據(jù)對象相似性的方法有漢明距離(Hamming distance，HM)、圖像耦合分析[12]、發(fā)生頻率(Occurrence frequency，OF)、逆發(fā)生頻率(Inverse occurrence frequency，IOF)等，常用的算法有K-modes 以及K-prototype 算法[13]。其中漢明距離對應(yīng)于基于匹配的相似性度量，使用0 和1 來表示不同和相同的分類值之間的相似性，發(fā)生頻率和逆發(fā)生頻率都是通過不同屬性值的發(fā)生頻率來表示相似性，K-modes 算法采用差異度來表示對象間的相似性，K-prototype則是對K-means 和K-mdoes 的結(jié)合，可用于同時存在數(shù)值型屬性和分類型屬性的數(shù)據(jù)集。文獻(xiàn)[14]提出一種非監(jiān)督耦合分類數(shù)據(jù)表示框架，用于捕獲層次耦合關(guān)系；文獻(xiàn)[15]利用概念格，提出一種新的動態(tài)加權(quán)模型來增強(qiáng)概念相似性測度。但這些方法都忽略了不同屬性之間的關(guān)系。以表1 中的數(shù)據(jù)為例，說明現(xiàn)有的用于分析分類型數(shù)據(jù)集相似性方法存在的挑戰(zhàn)。人員工作統(tǒng)計表中，每個工作人員都由4 個屬性組成：性別、文化程度、職業(yè)和薪資水平。先前提出的一些相似性度量方法只考慮了對象之間的相似性，比如HM，使用HM 衡量對象Staff1 和Staff2 之間的相似性為0.5，Staff2 和Staff3 之間的相似性也為0.5。但是很明顯，同等教育程度和性別下，薪資水平跟職業(yè)有很大的關(guān)系。通過觀察表1 中的數(shù)據(jù)不難發(fā)現(xiàn)，文化程度在很大程度上會影響人們的職業(yè)和薪資水平，而由生活經(jīng)驗(yàn)可知，性別對人們的工作性質(zhì)也有一定的影響，因此同一屬性下不同屬性值和不同屬性之間的關(guān)系對分類型數(shù)據(jù)集的相似性學(xué)習(xí)有很重要的參考價值。

CMS 在測量對象相似度之前，將基于頻率的屬性內(nèi)相似度與基于共生的的屬性間相似度結(jié)合起來。屬性內(nèi)相似性捕獲屬性值的頻率分布和值之間的耦合，屬性間相似度通過考慮不同屬性屬性值共現(xiàn)條件概率的交集來聚合不同屬性值之間的屬性依賴關(guān)系。CMS 主要從屬性內(nèi)相似性、屬性間相似性和耦合對象相似性來衡量兩個對象之間的相似性。

定義1 屬性內(nèi)相似性 兩個對象A和B關(guān)于屬性j的屬性內(nèi)相似性定義為SIa(Aj,Bj)，計算公式為

表1 人員工作統(tǒng)計表Table 1 Personnel work statistics

式中：p=|N(Aj)+1|；q=|N(Bj)+1|；Aj表示對象A在第j個屬性上所對應(yīng)的屬性值；Bj表示對象B在第j個屬性上所對應(yīng)的屬性值；N(Aj)表示所有在第j個屬性取值為Aj的對象的集合，其中N(Aj)+1 是為了避免分母取值為0；|·|表示集合中元素的個數(shù)。如果屬性值相同，則它們之間的屬性內(nèi)相似性為1；當(dāng)屬性值不一致時，它們的出現(xiàn)頻率即表示它們的屬性內(nèi)相似性。

定義2 屬性間相似性 在第j個屬性中，兩個屬性值A(chǔ)j和Bj關(guān)于除了屬性j外其他屬性的屬性間相似性定義為

式中：d表示數(shù)據(jù)集屬性的個數(shù)；rk|j表示每個屬性k到屬性j的權(quán)重；SIe(Aj,Bj)表示屬性j中兩個屬性值A(chǔ)j和Bj的屬性間相似性；Sk|j(Aj,Bj)表示屬性值A(chǔ)j和Bj關(guān)于屬性k的屬性間相似性，計算公式為

定義3 耦合度量相似性兩個對象A和B之間的耦合度量相似性（CMS）定義為

式中：βj表示屬性j的耦合度量屬性值相似性的權(quán)重；Sj(Aj,Bj)表示耦合度量屬性值的相似性，即將屬性值屬性內(nèi)的相似性與屬性值屬性間的相似性結(jié)合，其計算公式為

式中：α表示屬性值屬性內(nèi)的相似性和屬性值屬性間的相似性的加權(quán)調(diào)和平均。α越大，表明屬性間耦合在對象相似性中起的作用越重要，即屬性j與其他屬性屬性間的耦合比屬性j屬性內(nèi)耦合更重要。

基于無監(jiān)督耦合度量相似性的多尺度聚類算法，可以針對多尺度數(shù)據(jù)集中的分類型數(shù)據(jù)集進(jìn)行多尺度數(shù)據(jù)挖掘，不僅能夠考慮屬性內(nèi)之間的相互影響，還可以考慮到屬性間的影響，這是耦合度量相似性的精髓所在，也是多尺度聚類數(shù)據(jù)挖掘在尺度轉(zhuǎn)換時提高目標(biāo)尺度聚類性能的關(guān)鍵。

2 多尺度聚類挖掘

多尺度聚類數(shù)據(jù)挖掘是多尺度數(shù)據(jù)挖掘算法中的一種，主要針對無標(biāo)簽多尺度數(shù)據(jù)集進(jìn)行數(shù)據(jù)挖掘，基于耦合度量的多尺度聚類數(shù)據(jù)挖掘算法則是多尺度聚類數(shù)據(jù)挖掘的一種，主要針對非獨(dú)立同分布的分類型數(shù)據(jù)集進(jìn)行數(shù)據(jù)挖掘，其包含基準(zhǔn)尺度聚類、基于單鏈的尺度上推和基于Lanczos 核的尺度下推。

2.1 基準(zhǔn)尺度聚類算法

2.1.1 算法思想

本文基于耦合度量相似性方法，提出了多尺度數(shù)據(jù)挖掘基準(zhǔn)尺度聚類算法(Local scale clustering algorithm，LSCA)，其基本思想是：首先根據(jù)概率密度離散化方法，利用概率密度來對表征尺度的屬性進(jìn)行多尺度劃分，其次根據(jù)每層尺度信息熵的衰減來確定最優(yōu)尺度[16]，在選擇好的基準(zhǔn)尺度數(shù)據(jù)集上應(yīng)用數(shù)據(jù)挖掘算法LSCA 得到基準(zhǔn)尺度聚類結(jié)果。該算法思想的具體步驟如下：

2.1.2 理論基礎(chǔ)

多尺度聚類數(shù)據(jù)挖掘中，目標(biāo)尺度結(jié)果主要由基準(zhǔn)尺度的聚類結(jié)果經(jīng)過尺度轉(zhuǎn)換得到，因此基準(zhǔn)尺度在尺度轉(zhuǎn)換得到目標(biāo)尺度結(jié)果中具有重要作用。

（1）多尺度數(shù)據(jù)集的劃分與基準(zhǔn)尺度的選擇

多尺度數(shù)據(jù)集等價劃分均具有傳遞性、自反性和對稱性[17]。數(shù)據(jù)集按不同的屬性類型可以劃分為分類的（定性）和數(shù)值的（定量）。分類的包括標(biāo)稱和序數(shù)；數(shù)值的包括區(qū)間和比率。非獨(dú)立同分布分類型數(shù)據(jù)集劃分方法的主要思想是將數(shù)據(jù)預(yù)處理中的概念分層方法與無監(jiān)督離散化方法相結(jié)合，找出一個點(diǎn)或幾個點(diǎn)對具有多尺度特性的屬性進(jìn)行離散化，并劃分整個屬性區(qū)間，以此產(chǎn)生屬性值的多分辨率劃分。文獻(xiàn)[18]提出根據(jù)概率密度函數(shù)對數(shù)據(jù)集進(jìn)行離散化尺度劃分的方法，并借助得分函數(shù)評價劃分點(diǎn)的優(yōu)劣，得分函數(shù)值越大，表明劃分點(diǎn)選擇越合適。該方法不僅可以根據(jù)數(shù)據(jù)集的真實(shí)情況離散化分，同時也削弱了函數(shù)和區(qū)間劃分寬度對劃分的影響。

多尺度劃分?jǐn)?shù)據(jù)集后，數(shù)據(jù)集得到泛化，容易丟失一部分細(xì)節(jié)信息，數(shù)據(jù)集的混亂程度也變大，對基準(zhǔn)尺度的選擇成為多尺度數(shù)據(jù)挖掘的重要步驟。文獻(xiàn)[14]提出一種基于信息熵衰減選擇基準(zhǔn)尺度的方法，該方法基于數(shù)據(jù)集劃分尺度后信息量的變化情況對基準(zhǔn)尺度進(jìn)行評分，將評分最小的尺度作為基準(zhǔn)尺度，以保證進(jìn)行尺度轉(zhuǎn)換時信息損失最小，減小尺度轉(zhuǎn)換效應(yīng)。

（2）基準(zhǔn)尺度聚類

基準(zhǔn)尺度的選擇對于多尺度聚類數(shù)據(jù)挖掘來說非常重要，同樣，基準(zhǔn)尺度的聚類結(jié)果也很重要，聚類結(jié)果的好壞，將對尺度轉(zhuǎn)換結(jié)果有很大的影響。因此，基準(zhǔn)尺度的聚類結(jié)果應(yīng)盡可能地保留數(shù)據(jù)的原始特性，如數(shù)據(jù)的信息量、異質(zhì)性以及耦合性。

①信息量

②異質(zhì)性

異質(zhì)性就是一個群體里面，所有個體的特征差異程度。異質(zhì)性越高，個體的特征分布越分散。一般大尺度下異質(zhì)性會相對較低。

③耦合性

耦合性是程序結(jié)構(gòu)中各個模塊之間相互關(guān)系的度量。本文指的是屬性內(nèi)和屬性間的相互關(guān)系，隨著尺度的改變，屬性間的相關(guān)性也會隨之改變。

CMS 相似性度量方法將屬性內(nèi)和屬性間的相似性相結(jié)合，且該方法是基于度量的，滿足度量空間的性質(zhì)。度量空間在數(shù)學(xué)領(lǐng)域指的是一個集合，且集合中的各個元素之間的距離是可定義的，度量空間也稱作距離空間，滿足如下條件：

（a）正定性：ρ(x,y) ≥0且ρ(x,y) =0,當(dāng)且僅當(dāng)x=y

（b）對稱性：ρ(x,y) =ρ(y,x)

（c）三角不等式：ρ(x,y) ≤ρ(x,z) +ρ(y,z)

度量空間有很多良好的性質(zhì)，因此CMS 具有作為度量的有效性。

譜聚類算法以譜圖理論為基礎(chǔ)，能夠聚類任意分布的數(shù)據(jù)集，并且收斂于全局最優(yōu)解，本質(zhì)是將數(shù)據(jù)的聚類問題轉(zhuǎn)換為圖的最優(yōu)劃分問題，在數(shù)據(jù)聚類方面有很好的應(yīng)用價值。該算法首先根據(jù)給定數(shù)據(jù)集生成一個描述樣本間相似度的鄰接矩陣，然后求出度矩陣，并根據(jù)鄰接矩陣和度矩陣得出拉普拉斯矩陣，最后根據(jù)拉普拉斯矩陣得到特征值和特征向量，并構(gòu)造分類器，根據(jù)特征向量完成對數(shù)據(jù)集的聚類。其中拉普拉斯矩陣具有對稱性，它的所有特征值都是實(shí)數(shù)，且都大于等于0。

文獻(xiàn)[12]分別將CMS 與譜聚類和K-modes 算法相結(jié)合，實(shí)驗(yàn)結(jié)果表明，將CMS 與譜聚類結(jié)合比將CMS 與K-mdoes 算法結(jié)合具有更好的聚類結(jié)果。根據(jù)上述CMS 的性質(zhì)和譜聚類的優(yōu)勢，譜聚類算法與CMS 相似性方法結(jié)合具有一定的理論基礎(chǔ)，可以用于對具有多尺度特性的非獨(dú)立同分布的分類型數(shù)據(jù)集進(jìn)行多尺度聚類數(shù)據(jù)挖掘。

2.2 基于單鏈的尺度上推算法

2.2.1 算法思想

尺度轉(zhuǎn)換是多尺度聚類數(shù)據(jù)挖掘的關(guān)鍵，是多尺度領(lǐng)域研究的重中之重，尺度上推算法是尺度轉(zhuǎn)換的一種。本文借助凝聚層次聚類的思想，提出了多尺度數(shù)據(jù)挖掘尺度上推算法(Upscaling algorithm CMS, UACMS )。該算法的基本思想是：將每一個基準(zhǔn)尺度聚類中心作為一個初始簇，根據(jù)相似性度量方法，將最相似的兩個簇合并在一起，直到達(dá)到設(shè)定的簇的數(shù)目。具體實(shí)現(xiàn)步驟如下：

2.2.2 理論基礎(chǔ)

尺度上推思想類似于層次聚類中的凝聚層次聚類。凝聚層次聚類是一種自底向上的方法，簡單地說，其算法就是通過計算每個簇之間的相似性，并將相似性最高的兩個簇進(jìn)行合并，生成聚類樹的過程。凝聚層次聚類各個簇之間相互合并的依據(jù)分為3 種：單鏈(Single linkage)、全鏈(Complete linkage)和平均鏈(Average linkage)。

①單鏈

也稱作最近鄰(Nearest-neighbor)，就是取兩個簇當(dāng)中相似性最大的兩個樣本的相似性作為這兩個簇的相似性。這種合并方法容易造成一種鏈?zhǔn)?Chaining)效果，兩個簇從整體來看離得相對較遠(yuǎn)，但是由于其中部分樣本離得較近而合并，從而導(dǎo)致得到的合并簇較松散，進(jìn)一步擴(kuò)大了鏈?zhǔn)叫?yīng)。所謂的鏈?zhǔn)叫?yīng)，即前邊產(chǎn)生的結(jié)果會對后邊的結(jié)果產(chǎn)生一系列的影響。

②全鏈

全鏈就是將兩個簇中相似性最小的兩個樣本間的相似性作為兩個簇的相似性，效果剛好與單鏈相反，限制很大。

③平均鏈

平均鏈就是將兩個簇中兩兩樣本間的相似性求平均值作為兩個簇之間的相似性。這種方法受異常點(diǎn)的影響相對較大，而且時間復(fù)雜度也比較高.

UACMS 就是借助凝聚層次聚類思想中單鏈求兩個簇之間相似性的方法，對基準(zhǔn)尺度聚類結(jié)果進(jìn)行簇合并，進(jìn)而達(dá)到尺度上推的目的，其思想可用圖1 進(jìn)行表示。圖1 中的一個虛線圈表示一個簇，一個實(shí)線圈表示尺度劃分中的一個塊。

2.3 基于Lanczos 核的尺度下推算法

2.3.1 算法思想

尺度下推是尺度轉(zhuǎn)換的另一種表現(xiàn)形式。本文借助Lanczos 插值和分裂層次聚類的思想提出了多尺度聚類尺度下推算法（Downscaling based on Lanczos，DSAL)。該算法的思想是：首先得到基準(zhǔn)尺度聚類結(jié)果，其次將基準(zhǔn)尺度聚類結(jié)果作為已知樣本，利用Lanczos 核公式計算每個樣本的權(quán)重，得到新的聚類中心，最后計算樣本間的相似性，得到目標(biāo)尺度聚類結(jié)果。尺度下推的核心相當(dāng)于從宏觀到微觀，從展現(xiàn)整體的特征到顯示個體特征的過程，這個過程中可以得到更多的細(xì)節(jié)信息。該過程類似于分裂層次聚類，即將一個簇不斷地拆分為更多的簇。DSAL 的思想如圖2 所示，具體實(shí)現(xiàn)步驟如下：

圖1 尺度上推思想Fig.1 Idea of upscaling

圖2 尺度下推思想Fig.2 Idea of downscaling

2.3.2 理論基礎(chǔ)

在層次聚類中，凝聚層次聚類與分裂層次聚類的原理相反。分裂層次聚類采用自上而下的策略，首先將所有樣本都視為屬于同一個簇，然后根據(jù)它們之間的相似性逐漸進(jìn)行劃分，得到越來越多更小的簇，直到滿足終止條件。尺度下推算法的思想與分裂層次聚類類似，但又有所不同：它是將基準(zhǔn)尺度數(shù)據(jù)集的聚類結(jié)果作為初始數(shù)據(jù)集，然后對其進(jìn)行分裂，直到滿足目標(biāo)尺度的終止條件。

由于多尺度領(lǐng)域非常注重算法效率，因此需要嚴(yán)格把控尺度轉(zhuǎn)換所需要的時間，這也是在尺度轉(zhuǎn)換過程中用基準(zhǔn)尺度的聚類結(jié)果得到目標(biāo)尺度聚類結(jié)果的一個重要原因。本文提出的尺度下推算法DSAL 利用的就是對基準(zhǔn)尺度聚類結(jié)果進(jìn)行插值操作，得到每個樣本的權(quán)重，然后產(chǎn)生新的樣本點(diǎn)。對于一維數(shù)據(jù)集，假設(shè)輸入的點(diǎn)為x，則Lanczos 對應(yīng)位置的權(quán)重計算公式為

通常a取值為2 或3，當(dāng)a=2 時適用于縮小插值；a=3 時，適用于放大插值。通常根據(jù)輸入樣本x的取值，就可以確定樣本x所對應(yīng)的權(quán)重，同理也可以得到其他樣本的權(quán)重，然后對所有需要用到的樣本的取值加權(quán)平均，就可以得到想要的插值結(jié)果，即

根據(jù)已有樣本點(diǎn)之間的關(guān)系及其取值，可以得到新樣本點(diǎn)的取值，進(jìn)而可以得到目標(biāo)尺度聚類結(jié)果。

3 實(shí) 驗(yàn)

3.1 數(shù)據(jù)集

本文使用H 省全員人口數(shù)據(jù)集（簡稱renkou）、UCI 和Kaggle 公用數(shù)據(jù)集(Zoo, Soybeanlarge, Dermatology, BreastCancer, Titanic)驗(yàn)證算法的有效性和可行性。表2 給出了數(shù)據(jù)集的名稱、屬性數(shù)、樣本數(shù)、類別數(shù)和有無缺失值等方面信息。其中數(shù)據(jù)集Soybeanlarge，Dermatology和BreastCancer 在實(shí)驗(yàn)結(jié)果中分別用Sol，Der和BrC 表示。

實(shí)驗(yàn)環(huán)境為Windows 版本和Windows 10專業(yè)工作站版；處理器為Intel(R) Core(TM)i7-3770 CPU @ 3.40 GHz 3.40 GHz；已安裝的內(nèi)存(RAM)8.00 GB；系統(tǒng)類型為64 位操作系統(tǒng)、基于x64 的處理器。

表2 數(shù)據(jù)集相關(guān)信息Table 2 Information of the dataset

算法采用python 語言具體實(shí)現(xiàn)，實(shí)驗(yàn)設(shè)計思路如下：首先利用譜聚類與CMS，HM[19]，OF，IOF 和Eskin 相似性度量方法相結(jié)合，直接在目標(biāo)尺度數(shù)據(jù)集上進(jìn)行聚類挖掘；為了增加實(shí)驗(yàn)的對比性，使用最傳統(tǒng)的分類型數(shù)據(jù)集聚類方法K-modes 算法在目標(biāo)尺度上進(jìn)行數(shù)據(jù)挖掘；最后使用本文算法得到目標(biāo)尺度聚類結(jié)果。

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

使用MSE，歸一化互信息（Normalized mutual information，NMI），F(xiàn)-score 以及運(yùn)行時間4 個指標(biāo)對文獻(xiàn)[13]中的不同算法以及本文提出的尺度上推算法和尺度下推算法分別在目標(biāo)尺度上進(jìn)行了實(shí)驗(yàn)對比和分析。其中用到的對比算法均為根據(jù)公式或理論將算法還原后得到，其中CMS，HM 和OF 方法部分?jǐn)?shù)據(jù)集的NMI 值、F-score 值取文獻(xiàn)[12]中的最佳運(yùn)行結(jié)果，其他數(shù)據(jù)集的運(yùn)行結(jié)果均是還原算法后所得。為增加對比性，也與經(jīng)典K-modes 算法進(jìn)行了對比，其中用到的相似性度量方法為python 自帶的匹配方法。下文實(shí)驗(yàn)結(jié)果中的黑體數(shù)據(jù)表示所有算法在數(shù)據(jù)集中的最優(yōu)值。

3.2.1 尺度上推

尺度上推算法即UACMS 算法，通過基準(zhǔn)尺度聚類中心得到目標(biāo)尺度聚類中心，從而可以得到目標(biāo)尺度聚類結(jié)果。聚類結(jié)果表明，尺度上推UACMS 算法在6 個數(shù)據(jù)集中有4 個在NMI 上優(yōu)于CMS，HM，OF，IOF，Eskin 和K-modes 方法。

不同算法的NMI 值比較結(jié)果如表3 所示。由表3 可知，UACMS 算法的NMI 值相比其他算法平均提高了13.1%，其中OF 方法的平均NMI 值最小。NMI 值越接近于1，表明數(shù)據(jù)集的預(yù)測類標(biāo)簽與真實(shí)類標(biāo)簽越接近。UACMS 算法對于Titanic 和BrC 數(shù)據(jù)集的NMI 值不如其他方法，主要是受這兩個數(shù)據(jù)集中屬性間關(guān)系的影響，控制兩個屬性間相互影響大小的參數(shù)需要不斷調(diào)節(jié)，同時一個簡單的數(shù)字很難描述出屬性間的復(fù)雜關(guān)系，這將是未來工作的一個挑戰(zhàn)。

表3 尺度上推：不同算法的NMI 比較Table 3 Upsacling：NMI comparsion of different algorithms

不同算法MSE 值的比較結(jié)果如表4 所示。從表4 可以看出，UACMS 算法在6 個數(shù)據(jù)集中有4 個數(shù)據(jù)集比其他所有對比算法的MSE 值都小，UACMS 算法的MSE 值相對于其他算法平均降低了0.827，其中OF 算法的MSE 次之。MSE 值越小，表示簇內(nèi)對象之間越緊密，盡管OF 方法的NMI 值最小，但是其生成的簇比較緊湊。

不同算法F-score 值的比較結(jié)果如表5 所示。由表中的數(shù)據(jù)可知，UACMS 算法的F-score 值整體上高于其他對比算法，UACMS 算法的F-score 值相對于其他算法平均提高了12.8%，其中較為經(jīng)典的Kmodes 算法的F-score 值最小，主要是因?yàn)镵-modes 算法的聚類中心具有較大的隨機(jī)性，且其并沒有考慮到屬性間的相互影響。CMS 方法在多尺度數(shù)據(jù)挖掘中的應(yīng)用，提高了CMS 的F-score 值。

表4 尺度上推：不同算法的MSE 比較Table 4 Upsacling：MSE comparsion of different algorithms

表5 尺度上推：不同算法的F-score 比較Table 5 Upsacling：F-score comparsion of different algorithms

運(yùn)行時間是評價算法好壞的重要指標(biāo)。不同算法運(yùn)行時間的比較結(jié)果如表6 所示。從表6 可以看出，UACMS 算法在所有測試數(shù)據(jù)集上均快于其他對比算法，運(yùn)行時間平均提高了11.32 min；其他對比算法的運(yùn)行時間整體上隨數(shù)據(jù)量的增大而逐漸增加，但UACMS 算法的運(yùn)行時間與數(shù)據(jù)集的大小沒有明顯關(guān)系。因?yàn)閁ACMS 算法的運(yùn)行時間與基準(zhǔn)尺度的聚類數(shù)目和基準(zhǔn)尺度的劃分塊數(shù)有關(guān)系，不受原始數(shù)據(jù)集大小的影響。由于運(yùn)行時間受算法復(fù)雜度和運(yùn)行環(huán)境的影響，有時運(yùn)行速度也可以靠犧牲內(nèi)存來提高，因此本文中運(yùn)行時間的比較結(jié)果僅為參考數(shù)據(jù)，是所有對比算法在相同的實(shí)驗(yàn)環(huán)境下運(yùn)行得到的，具有一定的相對性。綜上，通過對比實(shí)驗(yàn)證明了尺度上推算法UACMS 的有效性和可行性。UACMS 算法相對于其他算法而言，在NMI，MSE，F(xiàn)-score 以及運(yùn)行時間方面均得到很大改善，聚類質(zhì)量顯著提高。

表6 尺度上推：不同算法的運(yùn)行時間比較Table 6 Upsacling：Running time comparsion of different algorithms s

3.2.2 尺度下推

DSAL 算法以及其他對比算法在不同數(shù)據(jù)集上的NMI 值比較結(jié)果如表7 所示。從表7 中的數(shù)據(jù)可知，DSAL 算法整體上的NMI 值高于其他對比算法。DSAL 算法的NMI 值相比其他算法平均提高了19.2%，其中K-modes 算法的NMI 值最低，主要有兩個原因：一個是所選數(shù)據(jù)集屬性之間有一定的影響，而K-modes 算法并沒有考慮不同屬性間的影響；另一個原因?yàn)镵-modes 算法的聚類中心具有一定的隨機(jī)性，聚類結(jié)果不穩(wěn)定。對比實(shí)驗(yàn)結(jié)果表明DSAL 算法的預(yù)測結(jié)果與真實(shí)結(jié)果更為相近，對于不同屬性間具有相互影響的數(shù)據(jù)集比較有優(yōu)勢。

表7 尺度下推：不同算法的NMI 值比較Table 7 Downsacling：NMI comparsion of different algorithms

不同算法MSE 值的比較結(jié)果如表8 所示。從表8 可以看出，DSAL 算法在6 個數(shù)據(jù)集中的3 個上的MSE 值比其他所有對比算法的MSE 值都小，表明DSAL 算法預(yù)測簇的緊密性與其他對比算法相比大體相近；DSAL 算法的MSE 值相對于其他算法平均降低了0.028，表明DSAL 算法形成的簇整體比其他算法略加緊密，而IOF 方法效果一般。

表8 尺度下推：不同算法的MSE 值比較Table 8 Downsacling：MSE comparsion of different algorithms

不同算法F-score 值的比較結(jié)果如表9 所示。從表9 中數(shù)據(jù)可知，DSAL 算法的F-score 值6 個數(shù)據(jù)集中有5 個都高于其他方法，而BreastCancer 數(shù)據(jù)集效果不如其他方法的原因可能是其屬性間的相互關(guān)系較復(fù)雜，無法用一個簡單的參數(shù)表示其關(guān)系；DSAL 算法的F-score 值相對于其他算法平均提高了15.5%，OF 方法得到的平均F-score 值最小。

表9 尺度下推：不同算法的F-score 值比較Table 9 Downsacling：F-score comparsion of different algorithms

運(yùn)行時間是評價算法好壞的重要指標(biāo)。不同算法運(yùn)行時間的比較結(jié)果如表10 所示。從表10 可以看出，DSAL 算法在所有測試數(shù)據(jù)集上均快于其他對比算法，運(yùn)行時間平均提高了11.42 min。其中，由文獻(xiàn)[12]可知，算法CMS 的時間復(fù)雜度很高，其中求兩個對象之間相似性的時間復(fù)雜度為O(nm3R2)，m表示屬性個數(shù)，n表示對象個數(shù)，R表示不同屬性值個數(shù)。將CMS 方法應(yīng)用到基準(zhǔn)尺度，對原始數(shù)據(jù)集分塊執(zhí)行CMS 方法，相當(dāng)于減少了算法運(yùn)行的對象個數(shù)，有時也可以減少不同屬性值個數(shù)，從而減少運(yùn)行時間。由表10 還可知，DSAL 算法的運(yùn)行速度明顯比原始的CMS 方法快很多，CSM 方法在多尺度數(shù)據(jù)挖掘中的應(yīng)用也是對該方法的一種優(yōu)化。其他對比算法的運(yùn)行時間整體上隨數(shù)據(jù)量的增大而逐漸增加，但DSAL 算法的運(yùn)行時間與數(shù)據(jù)集大小沒有明顯關(guān)系。因?yàn)镈SAL 算法與UACMS 算法一樣，運(yùn)行時間與基準(zhǔn)尺度的聚類數(shù)目和基準(zhǔn)尺度的劃分塊數(shù)有關(guān)系，并不受原始數(shù)據(jù)集大小的影響。由于算法的運(yùn)行時間受多種因素影響，比如運(yùn)行算法的機(jī)器配置，代碼優(yōu)化程度等，因此本文中的運(yùn)行時間僅為本實(shí)驗(yàn)環(huán)境下的運(yùn)行時間，僅供參考。

表10 尺度下推：不同算法的運(yùn)行時間比較Table 10 Downsacling：Running time comparsion of different algorithms s

綜上，通過對比實(shí)驗(yàn)證明了尺度下推算法DSAL 的有效性和可行性。DSAL 算法相較其他算法而言，在NMI，MSE，F(xiàn)-score 以及運(yùn)行時間方面均得到很大改善，聚類質(zhì)量得到顯著提高。

4 結(jié)束語

現(xiàn)有的多尺度聚類算法主要是針對于數(shù)值屬性型數(shù)據(jù)集進(jìn)行定量的分析，對分類屬性型數(shù)據(jù)集的研究相對較少，盡管有K-modes 算法針對分類型數(shù)據(jù)集進(jìn)行聚類，K-prototype 算法可以對數(shù)值屬性和分類屬性混合的數(shù)據(jù)集進(jìn)行聚類，但二者都沒有考慮不同屬性間的相互影響。而耦合度量相似性是一種基于度量的相似性度量方法，并且考慮到了屬性間和屬性內(nèi)的關(guān)系對樣本間相似性的影響。因此，本文提出基于耦合度量相似性的多尺度聚類算法，針對非獨(dú)立同分布的分類型多尺度數(shù)據(jù)集進(jìn)行多尺度數(shù)據(jù)挖掘，并提出了基于基準(zhǔn)尺度聚類結(jié)果進(jìn)行尺度轉(zhuǎn)換的尺度轉(zhuǎn)換方法：基于單鏈的尺度上推算法UACMS 以及基于Lanczos 核的尺度下推算法，并且實(shí)驗(yàn)結(jié)果證明了所提算法的有效性和可行性。

本文中的對比算法CMS，HM，OF，IOF 以及Eskin 相似性度量方法都是根據(jù)參考文獻(xiàn)[12]以及參考文獻(xiàn)[13]中的公式經(jīng)過代碼還原得到，代碼或許可經(jīng)過犧牲內(nèi)存縮短運(yùn)行時間進(jìn)行優(yōu)化，因此實(shí)驗(yàn)中的運(yùn)行時間僅為本實(shí)驗(yàn)環(huán)境下所消耗的時間，可通過優(yōu)化算法節(jié)省時間，因此本文運(yùn)行時間結(jié)果僅供參考。經(jīng)過上面的實(shí)驗(yàn)可以發(fā)現(xiàn)所提出的算法與其他對比算法相比，在性能及效率上有了很大的提高，但是對于某些特殊數(shù)據(jù)集預(yù)測結(jié)果并未達(dá)到理想效果。在下一步工作中，首先將進(jìn)一步完善用于分類型數(shù)據(jù)集的多尺度聚類算法以及對比算法，提高對比算法的運(yùn)行效率，改善多尺度聚類算法，使其能在更多的數(shù)據(jù)集上得到更高的NMI 值，提高預(yù)測結(jié)果的準(zhǔn)確率以及所得簇的緊湊性，從理論和實(shí)踐上尋找更適合的分類型多尺度數(shù)據(jù)集的相似性度量方法，提高聚類效率和性能；其次，屬性間的相互關(guān)系并不能僅靠一個參數(shù)或者簡單的加權(quán)來表示，還需要探索更好的方法來衡量對象之間的相似性，并不斷完善所提出的算法。