劉 洪 基

(楚雄師范學(xué)院經(jīng)濟與管理學(xué)院 云南 楚雄 675000)

0 引 言

當(dāng)前，工業(yè)過程、移動互聯(lián)網(wǎng)、社交網(wǎng)絡(luò)和物聯(lián)網(wǎng)生成大量數(shù)據(jù)，并推動大數(shù)據(jù)應(yīng)用的快速發(fā)展[1-2]。在各種大數(shù)據(jù)應(yīng)用中，都有許多高維多視圖數(shù)據(jù)，高維多視圖數(shù)據(jù)通常以各種來源獲得的多個特征空間和不同結(jié)構(gòu)進行描述[3]。傳統(tǒng)聚類方法將所有視圖作為一個統(tǒng)一的變量集，對此類具有數(shù)量、種類、速度、準確性和價值等多視圖的數(shù)據(jù)聚類效果較差[4]。在大數(shù)據(jù)環(huán)境下，如何實現(xiàn)高維多視圖數(shù)據(jù)的聚類以適應(yīng)各種復(fù)雜的、大規(guī)模的應(yīng)用是最具挑戰(zhàn)性的問題之一[5]。

由于大數(shù)據(jù)的廣泛應(yīng)用，多視圖數(shù)據(jù)的聚類吸引了許多研究人員的關(guān)注。文獻[6]將多視圖任務(wù)的非監(jiān)督特征選擇保留在集群結(jié)構(gòu)中，然后提出一種交替算法來實現(xiàn)該結(jié)構(gòu)。對于多視圖聚類問題，文獻[7]提出了一種新穎的多視圖關(guān)聯(lián)傳播算法，該算法特別適合于對兩個以上的視圖進行聚類。文獻[8]提出了局部自適應(yīng)聚類(Local Adaptive Clustering,LAC)算法，該算法為每個聚類的每個特征分配權(quán)重，通過使用迭代算法最小化其目標函數(shù)。文獻[9]提出了一種多視圖數(shù)據(jù)的自動兩級變量加權(quán)K均值(Two-variables Weighted K-means,TWKM)聚類算法，該算法可以同時計算視圖和單個變量的權(quán)重，但是很容易導(dǎo)致在單個特征和單個視圖上具有較大權(quán)重的聚類，因此權(quán)重的分布不平衡。然而，上述算法主要關(guān)注于具有視圖方式關(guān)系的問題，而忽略了數(shù)據(jù)集高維特征的重要性，使得聚類結(jié)果與實際應(yīng)用存在較大差異，此外，上述方法由于聚類性能的限制對大數(shù)據(jù)應(yīng)用中更復(fù)雜的高維數(shù)據(jù)的聚類效果較差。

為了解決實際大數(shù)據(jù)應(yīng)用中的高維多視圖數(shù)據(jù)聚類問題，并且進一步提升該聚類算法的聚類性能，提出一種基于混沌粒子群優(yōu)化算法(Chaos Particle Swarm Optimization,CPSO)的智能加權(quán)K均值(Intelligent Weighted K-means,IWKM)聚類算法。

1 相關(guān)理論

1.1 加權(quán)K均值聚類算法

集群是數(shù)據(jù)對象的集合，這些數(shù)據(jù)對象在同一集群中彼此相似，但與其他集群中的對象不同[10]。給定數(shù)據(jù)對象集X=[xi,j]N×D，N是數(shù)據(jù)對象的數(shù)量，D是數(shù)據(jù)對象的維度。也就是說，數(shù)據(jù)對象具有D個特征。聚類問題試圖找到X的k分區(qū)。簇的中心是Z=[zk,j]C×D。U=[ui,k]N×C，主要通過模糊劃分矩陣描述對象是某些集群的隸屬度[9]。

作為具有敏感初始聚類中心的聚類算法，K均值被廣泛用于實際應(yīng)用中，例如圖像分割和數(shù)據(jù)挖掘[11-12]。K均值的目標是找到一個分區(qū)，以最小化帶簇的平方和。在聚類過程中，用以下式子解決樣本劃分任務(wù)：

(1)

式中：U被定義為分區(qū)矩陣；ui,k是一個二進制變量；Z={Z1,Z2,…,Zk}是一組向量，表示k個簇的質(zhì)心；(xi,j-zk,j)2是第i個對象與第j個變量上的第k個簇的中心之間的距離度量。

在經(jīng)典的K均值聚類算法中，所有特征均具有相同的權(quán)重，在諸如消費者細分之類的聚類問題中，所有特征均得到同等對待。實際上，在許多實際應(yīng)用中，數(shù)據(jù)集中不同特征對聚類的影響是不同的，因此有必要為不同特征分配不同的權(quán)重。K均值類型聚類中的自動變量加權(quán)是加權(quán)K均值聚類算法，目標函數(shù)為:

(2)

式中：U被定義為n×k分區(qū)矩陣；WF是特征的權(quán)重;β表示權(quán)重函數(shù)維度。

1.2 軟子空間聚類算法

軟子空間聚類算法根據(jù)維度在發(fā)現(xiàn)相應(yīng)聚類中的作用來確定維度的子集。維度的貢獻是通過在聚類過程中分配給維度的權(quán)重來衡量的。文獻[13]提出了一種軟子空間聚類算法，目標函數(shù)的建模為：

(3)

式中：WCF=wcfk,j是每個集群中每個屬性的權(quán)重。

2 IWKM算法

2.1 高維多視圖數(shù)據(jù)的聚類

用于將X劃分為具有視圖和特征權(quán)重的集群的聚類建模為以下目標函數(shù)的最小化。

minFitness(U,Z,WV,WF)=

(4)

式中：U=[ui,k]N×C是一個N×C分區(qū)矩陣，其元素ui,k為二進制，其中ui,k=1表示對象i已分配給集群k;Z=[zk,j]C×D是一個N×C矩陣，其元素zk,j表示簇k的第j個特征;WV=[wvt]T是T視圖的權(quán)重;WF=[wfj]j∈Viewt是視圖t下的特征權(quán)重;wvtwfj(xi,j-zk,j)2是第i個對象與第k個簇的中心之間的第j個特征的加權(quán)距離度量;wvtwfj(zk,j-oj)2是第k個聚類與平均聚類中心之間的第j個特征的加權(quán)距離度量，oj是C個聚類的平均聚類中心。該值描述集群之間的耦合程度，越大表示相異性越大。

2.2 CPSO和粒子編碼

(5)

(6)

ω=ωmax-(ωmax-ωmin)×g/gmax

(7)

粒子編碼是使用粒子群搜索最佳解的前提[14]。在IWKM中，初始聚類中心、視圖權(quán)重和特征權(quán)重被編碼為粒子表示形式。每個粒子由F×C+T+F維實數(shù)向量編碼。F是聚類問題中對象的特征數(shù)。群中的第i個粒子被編碼為：

(8)

2.3 精確擾動和CPSO

為了避免局部最優(yōu)和過早收斂，利用跳躍或突變在豐富群體智能中粒子的搜索行為方面具有很大的優(yōu)勢[15]。在CPSO中，混沌邏輯序列擾動被用于幫助粒子脫離局部最優(yōu)并獲得更好的搜索質(zhì)量，具有確定性、遍歷性和隨機性，將其定義為式(9)。

x(t+1)=r·x(t)·(1-x(t))

r∈N,x(0)∈[0,1]

(9)

式中：r是控制參數(shù)，x是變量，r=4，t=0,1,2,…。

本文將CPSO的精確擾動概括為以下過程的相互作用。

步驟1創(chuàng)建合適的擾動粒子：為了減少粒子搜索過程中總體穩(wěn)定性的損失和CPU的計算代價，通過簡單的隨機抽樣方法從總共N_S個粒子中隨機選擇N_S/K_spark個粒子作為擾動對象。K_spark是Apache Spark中的工作程序節(jié)點數(shù)。

步驟2精確擾動時間：擾動的時間是粒子群過早收斂的時間。pBest和gBest之間的平均距離用于判斷粒子是否處于過早收斂狀態(tài)，記為式(10)。

(10)

式中：N_S和dim是群的粒子數(shù)和粒子的維度；Q_d代表過早收斂的閾值；如果d(pBest,gBest)≤Q_d，則出現(xiàn)過早收斂和局部最優(yōu)，然后應(yīng)采用適合N_S/K_spark粒子的擾動。

步驟3精確擾動維度：由于粒子具有一個以上的維，因此根據(jù)慣性的優(yōu)先級，優(yōu)先選擇一些具有較高慣性的維來進行擾動。第j維中的pBest和gBest的慣性可以由均方差給出，分別記為式(11)和式(12)。

Q_pBest

(11)

Q_gBest

(12)

式中：N_S和m是群的粒子數(shù)和當(dāng)前迭代數(shù)。如果sd(pBestj)≤Q_pBest或sd(gBestj)≤Q_gBest，則第j維的pBest、gBest是惰性的，需要進行擾動。其中Q_pBest和Q_gBest分別是pBest和gBest的惰性閾值。

2.4 IWKM流程

IWKM算法的流程如圖1所示。

圖1 IWKM算法流程

3 實驗評估

3.1 測試環(huán)境和spark

在分布式和并行計算環(huán)境中，Apache Spark是一個重要的開源集群計算框架，它為隱式數(shù)據(jù)并行和容錯的整個集群編程提供了一個接口[16]。Spark的彈性分布式數(shù)據(jù)集(RDD)是分布式程序的工作集，可以提供受限形式的分布式共享內(nèi)存。因此，本文選擇了Apache Spark作為大數(shù)據(jù)應(yīng)用中IWKM的計算平臺。在本文實驗中，對IWKM進行了測試，并在包括Apache Spark和Single Node在內(nèi)的各種計算環(huán)境中進行了比較。Single Node配備了Intel Core i5- 4210M 2.6 Hz，3.8 GB RAM和Ubuntu 14.04LTS操作系統(tǒng)。

Apache Spark有一個主節(jié)點，配置為Intel Core i7- 3820@3.6 GHz，64 GB DDRIII和1 TB高效云磁盤，十個工作節(jié)點，相關(guān)配置為Intel Xeon E5- 2690@2.9 GHz，16 GB DDRIII和500 GB高效云磁盤，應(yīng)用版本為Apache Spark 1.6.0。

3.2 測試數(shù)據(jù)集

為了評估本文算法的性能，還通過RI(Rand Index)、JC(Jaccard coefficient)和Folk的評估指標，將IWKM與LAC、親和傳播(Affinity Propagation,AP)[17]、歸一化分割(Normalized Cut,Ncut)[11]、密度聚類(Density Clustering,DC)[18]和TWKM進行了比較。為了公平比較，PSO和CPSO使用相同的30人口規(guī)模和150個適應(yīng)度值進行評估。IWKM和其他五種算法已在5個高維多視圖數(shù)據(jù)集中進行了測試，其中包括多特征數(shù)據(jù)集、互聯(lián)網(wǎng)廣告數(shù)據(jù)集、Spambase數(shù)據(jù)集、圖像分割集和心電圖數(shù)據(jù)集。這些數(shù)據(jù)集及其應(yīng)用的基本信息如表1所示。

表1 高維多視圖數(shù)據(jù)集的特征

多特征數(shù)據(jù)集是從荷蘭實用程序圖的集合中提取的手寫數(shù)字數(shù)據(jù)集，其中包含2 000個屬于10類(0～9)的數(shù)字對象。每類有200個對象。每個對象均由649個特征表示，這些特征分為以下六個視圖：1) Mfeat-fou視圖包含76個字符形狀的傅里葉系數(shù)；2) Mfeat-fac視圖包含216個配置文件相關(guān)性；3) Mfeat-kar視圖包含64個Karhunen-Love系數(shù)；4) Mfeat-pix視圖包含240個像素窗口；5) Mfeat-zer視圖包含47個Zernike時刻；6) Mfeat-mor視圖包含6個形態(tài)特征。

互聯(lián)網(wǎng)廣告數(shù)據(jù)集包含來自各種網(wǎng)頁的3 279幅圖像，這些圖像被分類為廣告或非廣告。有20幅圖片的值缺失。我們的實驗在3 259個實例上進行，刪除了缺失值的實例。在六個視圖中描述了實例。視圖1包含3種圖像幾何形狀(寬度、高度和長寬比)；視圖2在包含圖片的頁面網(wǎng)址(基本網(wǎng)址)中包含457個詞組；視圖3包含495個圖像URL的短語(圖像URL)；視圖4在圖像所指向的頁面的URL中包含472個短語(目標URL)；視圖5包含111個錨文本；視圖6包含19個圖像的文本alt(替代)html標簽(alt文本)。

Spambase是一個數(shù)據(jù)集，其垃圾郵件的收集來自郵局主管和具有現(xiàn)場垃圾郵件的個人，非垃圾郵件的收集來自現(xiàn)場工作和個人電子郵件，其中包含4 601個屬于2類(垃圾郵件、非垃圾郵件)的對象。每個對象都由57個要素表示，這些要素分為三個視圖，分別是單詞頻率視圖、字符頻率視圖和大寫游程視圖。1) 單詞頻率視圖包含word類型的48個連續(xù)實數(shù)屬性；2) 字符頻率視圖包含char類型的6個連續(xù)實數(shù)屬性；3) 大寫游程視圖包含測量連續(xù)大寫字母序列長度的3個連續(xù)實數(shù)屬性。

在該數(shù)據(jù)集中，從7幅室外圖像的數(shù)據(jù)庫中隨機抽取了2 310個實例。手動分割圖像以為每個像素創(chuàng)建一個分類。每個實例都是一個3×3的區(qū)域。數(shù)據(jù)集包含19個特征，可分為2個視圖：形狀視圖包含9個有關(guān)形狀信息的特征，而RGB視圖包含10個有關(guān)顏色信息的特征。

自動處理2 126例胎兒心電圖(Cardiotocograms,CTG)并測量相應(yīng)的診斷特征。CTG還由三位專家產(chǎn)科醫(yī)生進行分類，并為他們每個人分配了共識分類標簽。分類既涉及形態(tài)學(xué)模式(A，B，C，…)，也涉及胎兒狀態(tài)(N，S，P)。因此，該數(shù)據(jù)集可用于10類或3類實驗。在此實驗中，將其用作3類數(shù)據(jù)集。在數(shù)據(jù)集中，可以將21個要素劃分為3個視圖：每秒指標、可變性視圖和直方圖視圖。

3.3 評估指標

本文使用的三個外部標準可以定義如下：

(1)RI=(SS+DD)/(SS+SD+DS+DD)，RI越大，說明聚類結(jié)果與真實情況越吻合。

(2)JC=SS/(SS+SD+DS)，該指標用于衡量兩個數(shù)據(jù)的相似度，JC越大，相似度越大，聚類精度越高。

3.4 參數(shù)分析

為了分析3個參數(shù)(Q_d、Q_gbest和Q_pBest)對高維多視圖數(shù)據(jù)的聚類性能的影響，在Single Node上對3個數(shù)據(jù)集(Mfeat數(shù)據(jù)集、互聯(lián)網(wǎng)廣告數(shù)據(jù)集Spambase數(shù)據(jù)集)中的IWKM進行了測試。為了減少統(tǒng)計錯誤，所有數(shù)據(jù)集均獨立進行了10次模擬。

根據(jù)過早收斂的閾值評估，將Q_d在Mfeat和Spambase數(shù)據(jù)集中以5步長設(shè)置在[5，45]。將Q_d在互聯(lián)網(wǎng)廣告數(shù)據(jù)集中以3步長設(shè)置在[2，20]。關(guān)于它們的平均評價指標的統(tǒng)計結(jié)果如圖2所示。可以看出，當(dāng)Q_d分別選擇為30、8和25時，IWKM具有在Single Node上的3個數(shù)據(jù)集中進行聚類的最佳性能。參數(shù)Q_gbest和Q_pBest是維度慣性的閾值，用于測量每個維度中位置的可感知變化是否發(fā)生。三個數(shù)據(jù)集上的參數(shù)Q_gbest和Q_pBest也與Q_d類似地進行分析。關(guān)于它們的平均評價指標的統(tǒng)計結(jié)果分別示于圖3和圖4。由于在Spambase中JC和RI的值幾乎相等，因此JC和RI的曲線重疊。根據(jù)參數(shù)分析的結(jié)果，將選擇最佳參數(shù)值Q_d、Q_gbest和Q_pBest并在下一個實驗中進行測試。

(a) 多特征數(shù)據(jù)集

(b) 互聯(lián)網(wǎng)廣告數(shù)據(jù)集

(c) Spambase數(shù)據(jù)集圖2 參數(shù)Q_d變化曲線

(a) 多特征數(shù)據(jù)集

(b) 互聯(lián)網(wǎng)廣告數(shù)據(jù)集

(c) Spambase數(shù)據(jù)集圖3 參數(shù)Q_gbest變化曲線

(a) 多特征數(shù)據(jù)集

(b) 互聯(lián)網(wǎng)廣告數(shù)據(jù)集

(c) Spambase數(shù)據(jù)集圖4 參數(shù)Q_pbest變化曲線

3.5 PSO和CPSO的比較

為了驗證CPSO在IWKM中聚類中心、視圖權(quán)重和特征權(quán)重的優(yōu)化，我們在Single Node上的三個高維多視圖數(shù)據(jù)集中測試了CPSO和PSO。通過CPSO和PSO將數(shù)據(jù)集運行10次，圖5記錄并比較了各種算法的平均結(jié)果。在CPSO中，提出一種精確的擾動，包括合適的擾動粒子、精確的擾動時間和擾動維數(shù)，以提高優(yōu)化性能?？梢钥闯?，CPSO可以在Single Node上的所有三個高維多視圖數(shù)據(jù)集中實現(xiàn)更好的解決方案精度，并盡早獲得最佳解決方案。顯然，CPSO在IWKM集群方面比PSO具有更好的性能。因此，可以得出結(jié)論，作為一種重要的優(yōu)化方法，CPSO可以幫助IWKM在高維多視圖數(shù)據(jù)中獲得更好的初始聚類中心、視圖權(quán)重和特征權(quán)重。

(a) 多特征數(shù)據(jù)集

(b) 互聯(lián)網(wǎng)廣告數(shù)據(jù)集

(c) Spambase數(shù)據(jù)集圖5 PSO與CPSO的比較

3.6 IWKM視圖權(quán)重比較

為了進一步評估獲得視圖權(quán)重的性能，在五個不同的高維多視圖數(shù)據(jù)集中測試了TWKM和IWKM。兩個算法在數(shù)據(jù)集中運行了10次，并記錄了IWKM和TWKM的平均結(jié)果并在表2中進行了比較。顯然，IWKM和TWKM可以為5個高維多視圖數(shù)據(jù)集獲得有效權(quán)重。特別是在互聯(lián)網(wǎng)廣告和圖像分割這兩個數(shù)據(jù)集中，TWKM和IWKM在獲得視圖權(quán)重方面具有相似的性能。但是，在Apache Spark和Single Node上，在其他3個數(shù)據(jù)集(Mfeat、Spambase和心電圖)中，IWKM可以獲得比TWKM更好、更合理的視圖權(quán)重。TWKM計算出的視圖權(quán)重常常集中在一個視圖上，這與現(xiàn)實應(yīng)用不符。IWKM計算的權(quán)重比TWKM計算的權(quán)重更合理，并且特征的權(quán)重處于相同情況。因此，可以得出結(jié)論，在視圖權(quán)重方面，IWKM比TWKM具有更好的性能。

表2 TWKM和IWKM計算的視圖權(quán)重

續(xù)表2

利用CPSO進行優(yōu)化得到六個聚類算法的最優(yōu)參數(shù)值如表3所示。為了進一步驗證本文算法在大數(shù)據(jù)應(yīng)用中對高維多視圖數(shù)據(jù)進行聚類的綜合性能，在Apache Spark和Single Node兩種不同的計算平臺上，通過RI、JC和Folk的評估指標，在五個高維多視圖數(shù)據(jù)集中將IWKM與其他五種算法進行了比較。

表3 實驗中六種聚類算法的參數(shù)值

在實驗中，視圖數(shù)與特征數(shù)的乘積記錄為pf×v，用于描述高維多視圖數(shù)據(jù)的復(fù)雜性。特征數(shù)越大，高維多視圖數(shù)據(jù)越復(fù)雜。在表1中，根據(jù)pf×v的值，Mfeat的數(shù)據(jù)集(特征數(shù)：649，視圖數(shù)：6，pf×v=649×6=3 894)、互聯(lián)網(wǎng)廣告數(shù)據(jù)集(特征數(shù)：1 557，視圖數(shù)：6，pf×v=1 557×6=9 342)比Spambase數(shù)據(jù)集(特征數(shù)：57，視圖數(shù)：3，pf×v=57×3=171)、圖像分割數(shù)據(jù)集(特征數(shù)：19，視圖數(shù)：2，pf×v=19×2=38)、心電圖數(shù)據(jù)集(特征數(shù)：21，視圖數(shù)：3，pf×v=21×3=63)更復(fù)雜。

表4總結(jié)了IWKM與其他五種算法在Apache Spark和Single Node上的綜合比較。比較它們的平均結(jié)果(10倍)和標準偏差以減少統(tǒng)計誤差。從這些結(jié)果中，可以看到IWKM在Mfeat數(shù)據(jù)集和互聯(lián)網(wǎng)廣告數(shù)據(jù)集中明顯優(yōu)于的其他五種算法。在Spambase數(shù)據(jù)集中，IWKM的性能優(yōu)于TWKM和DC，但AP在Mfeat數(shù)據(jù)集中的效果最差。在Mfeat數(shù)據(jù)集中，DC和IWKM均比LAC、AP、Ncut和TWKM更好。在互聯(lián)網(wǎng)廣告數(shù)據(jù)集中，AP、TWKM和IWKM的性能優(yōu)于LAC、Ncut和DC。LAC明顯優(yōu)于Spambase數(shù)據(jù)集中的其他五種算法(包括IWKM)，但Spambase數(shù)據(jù)集的復(fù)雜度低于Mfeat數(shù)據(jù)集和互聯(lián)網(wǎng)廣告數(shù)據(jù)集。因此，可以得出結(jié)論，在這些復(fù)雜的數(shù)據(jù)集中，IWKM在針對具有更多視圖和更高維度數(shù)據(jù)集來說，例如多特征和互聯(lián)網(wǎng)廣告數(shù)據(jù)集，勝過其他五種算法。在心電圖數(shù)據(jù)集中，IWKM優(yōu)于其他的五種算法。但是，在圖像分割中，Ncut和TWKM的性能要優(yōu)于IWKM。由于心電圖數(shù)據(jù)集比圖像分割數(shù)據(jù)集更為復(fù)雜，因此高維多視圖數(shù)據(jù)集越復(fù)雜，IWKM的性能越好?？傊琁WKM可以更加有效地處理大數(shù)據(jù)應(yīng)用中的高維多視圖數(shù)據(jù)集的聚類。同時，在這些復(fù)雜的數(shù)據(jù)集中，IWKM優(yōu)于其他五種算法。

表4 五種算法的比較

4 結(jié) 語

針對傳統(tǒng)聚類算法無法處理大數(shù)據(jù)中多視圖高維數(shù)據(jù)問題，提出一種基于混沌粒子群優(yōu)化算法的智能加權(quán)K均值聚類算法。通過實驗證明了CPSO可以幫助IWKM在高維多視圖數(shù)據(jù)中獲得更好的初始聚類中心、視圖權(quán)重和特征權(quán)重，為聚類精度的提升提供良好的初始值要求。另外本文方法能夠有效實現(xiàn)多視圖高維數(shù)據(jù)的聚類，且針對視圖越多、維數(shù)越高、數(shù)據(jù)越復(fù)雜的數(shù)據(jù)集越能夠體現(xiàn)該算法的優(yōu)越性。