潘品臣，姜 合，呂奕錕

(齊魯工業(yè)大學(xué)(山東省科學(xué)院) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 ，濟(jì)南 250353)

1 引 言

聚類算法是數(shù)據(jù)挖掘中重要的研究內(nèi)容之一，它是一個(gè)將物理或抽象對象的集合分組為由類似的對象組成的多個(gè)類的分析過程.基本的聚類方法包括：基于劃分的方法、基于層次的方法、基于密度的方法、基于網(wǎng)絡(luò)的方法以及基于模型的方法等等[1].K-means算法最早由MacQueen提出的[2]，是典型的基于劃分的聚類算法之一，它具有簡單、快速的優(yōu)點(diǎn).但是，傳統(tǒng)K-means算法也存在著一些缺陷，其中最主要的便是對于初始中心點(diǎn)的選取比較敏感，不當(dāng)?shù)倪x擇容易陷入局部最優(yōu)且聚類結(jié)果準(zhǔn)確率低.針對這一缺陷，很多研究者提出了改進(jìn)的方法，例如：Likas等人提出了一種全局K-means算法[3]，它是一種增量式的聚類算法，通過一個(gè)確定的全局搜索過程，每次動(dòng)態(tài)地添加一個(gè)聚類中心，從合適的初始位置執(zhí)行K-means算法.袁方等人為了消除K-means算法對初始聚類中心點(diǎn)選擇上的敏感性，提出了一種優(yōu)化聚類中心的方法[4]，此方法計(jì)算每個(gè)數(shù)據(jù)對象所在區(qū)域的密度，選擇相互距離最遠(yuǎn)的k個(gè)處于高密度區(qū)域的點(diǎn)作為初始聚類中心.翟東海等人針對聚類時(shí)容易出現(xiàn)局部最優(yōu)、聚類結(jié)果不穩(wěn)定、總迭代次數(shù)較多等問題，提出了最大距離法[5]來選取初始簇中心.邢長征等人針對現(xiàn)有的基于密度優(yōu)化初始聚類中心的方法在聚類中心的搜索范圍大、消耗時(shí)間久以及聚類結(jié)果對孤立點(diǎn)敏感等問題，提出了一種基于平均密度優(yōu)化初始聚類中心的adk-means算法[6].鄒臣嵩等人提出了一種基于最大距離積與最小距離之和的協(xié)同K聚類算法[7]，該方法解決了傳統(tǒng)K-means算法聚類結(jié)果隨機(jī)性大、穩(wěn)定性差，以及最大距離乘積法迭代次數(shù)多、運(yùn)算時(shí)間長等問題.唐東凱等人針對K-means算法對初始聚類中心和離群點(diǎn)敏感的缺點(diǎn)，提出了一種優(yōu)化初始聚類中心的改進(jìn)K-means算法[8]，該方法首先計(jì)算數(shù)據(jù)集中每個(gè)對象的離群因子并進(jìn)行升序排序，使得中心點(diǎn)的位置靠前，然后引入取樣因子，從而得到候選初始中心點(diǎn)集，最后利用Max_min方法的思想在候選初始中心點(diǎn)集上選取k個(gè)聚類初始中心.

目前對于初始中心點(diǎn)的改進(jìn)都是建立在獨(dú)立同分布基礎(chǔ)上進(jìn)行的，然而數(shù)據(jù)中的屬性之間或多或少會(huì)存在相互作用和關(guān)系，是非獨(dú)立同分布的.非獨(dú)立同分布思想最早是由Cao在2011年提出的[9].隨后又有不少研究者將此思想應(yīng)用于不同方面，例如：Wang等人在無監(jiān)督學(xué)習(xí)中提出了耦合名義上的相似性度量來代替?zhèn)鹘y(tǒng)的歐式距離度量[10]，但這僅限于類別型數(shù)據(jù)集.Liu等人分別對不平衡數(shù)據(jù)下的混合耦合KNN算法、不平衡分類數(shù)據(jù)的模糊耦合KNN算法以及用于多標(biāo)簽分類的耦合KNN算法進(jìn)行了研究[11-13].Li等人提出了一種新的通用耦合矩陣分解模型(CMF)[14]，通過引入用戶與物品之間的非獨(dú)立同分布耦合關(guān)系在推薦系統(tǒng)應(yīng)用方面進(jìn)行了研究.Jian等人為無監(jiān)督學(xué)習(xí)定義了一個(gè)耦合度量相似度(CMS)[15]，它靈活地捕獲了從值到屬性到對象的異構(gòu)耦合關(guān)系，能夠靈活地適應(yīng)獨(dú)立同分布和非獨(dú)立同分布下的數(shù)據(jù)，但其主要研究對象還是類別型數(shù)據(jù)集.

在上述文獻(xiàn)中有的解決了K-means算法隨機(jī)選取初始中心點(diǎn)的問題，但卻忽略了噪聲點(diǎn)對結(jié)果的影響；有的避免了噪聲點(diǎn)的影響，但忽略了屬性之間存在的交互關(guān)系.本文在非獨(dú)立同分布下提出了一種基于雙領(lǐng)域思想和Min_max方法相結(jié)合的優(yōu)化K-means初始中心選擇的方法，(即K-means algorithm based on Dual Domain idea and Min_max method within Non- Independent and Identically Distribution context，簡稱NonIID-DDMMK-means算法).數(shù)值數(shù)據(jù)可以基本表示為一個(gè)信息表的格式[16]，其中每一列表示為指定的“屬性”，每一行表示為指定的“對象”.鑒于此，本文首先考慮屬性之間的相互作用關(guān)系，利用Pearson相關(guān)系數(shù)公式計(jì)算每一列本身和其他列之間的相關(guān)系數(shù)[17]，即不同屬性之間的交互關(guān)系.然后將屬性之間的交互關(guān)系映射于原始數(shù)據(jù)每一行的對象之間，形成一個(gè)能夠體現(xiàn)屬性交互關(guān)系的新的數(shù)據(jù)集.最后利用雙領(lǐng)域思想對Min_max方法進(jìn)行優(yōu)化，即在高密度領(lǐng)域選取第一個(gè)初始中心點(diǎn)，在非噪聲點(diǎn)領(lǐng)域利用Min_max方法的思想選取其它初始中心點(diǎn)來解決初始中心點(diǎn)敏感的缺陷，并且能夠減少迭代次數(shù)，提高聚類效果.

2 K-means算法

K-means算法是聚類分析中最常用的基于劃分的算法之一，已經(jīng)在許多行業(yè)領(lǐng)域得到很好的應(yīng)用，該算法的執(zhí)行流程是：

1)隨機(jī)地在將要聚類的數(shù)據(jù)集中選擇k個(gè)數(shù)據(jù)對象作為初始聚類中心，這里的k代表類簇?cái)?shù)目.

2)遍歷數(shù)據(jù)集中剩余的每個(gè)對象，根據(jù)相似度來決定每一個(gè)數(shù)據(jù)對象應(yīng)該被分配到哪一個(gè)簇中，將每個(gè)對象分配到與其相似度最大的簇中.這里的相似性度量通常使用歐式距離來表示，兩個(gè)對象之間的距離越小說明它們之間的相似度越大.

3)重新計(jì)算每一個(gè)簇的中心點(diǎn)，將每一個(gè)簇的均值作為新的中心點(diǎn).

4)重復(fù)執(zhí)行步驟2、步驟3，直到準(zhǔn)則函數(shù)收斂，準(zhǔn)則函數(shù)見公式(1).

(1)

這里的準(zhǔn)則函數(shù)通常使用聚類誤差平方和，其中，k為簇的個(gè)數(shù)，m為簇中對象的總個(gè)數(shù)，Oij是第i簇的第j個(gè)數(shù)據(jù)對象，Ci是第i簇的均值中心.

3 NonIID-DDMMK-means算法

NonIID-DDMMK-means算法對于初始聚類中心點(diǎn)的選取主要分為三個(gè)過程：

1)利用修改后的Pearson相關(guān)系數(shù)公式計(jì)算每一列屬性之間的相關(guān)系數(shù)，即屬性之間的交互關(guān)系.并將屬性之間的交互關(guān)系映射于原始數(shù)據(jù)集的對象之間從而形成一個(gè)能夠體現(xiàn)屬性間交互關(guān)系的新的數(shù)據(jù)集；

2)利用密度參數(shù)的思想，計(jì)算出數(shù)據(jù)集中的高密度領(lǐng)域和非噪聲點(diǎn)領(lǐng)域.其中，高密度領(lǐng)域用來對Min_max方法在第一個(gè)點(diǎn)的選擇上進(jìn)行確認(rèn)，非噪聲點(diǎn)領(lǐng)域用來對Min_max方法在其他點(diǎn)的選擇上進(jìn)行約束；

3)根據(jù)Min_max方法在雙領(lǐng)域中選取初始聚類中心點(diǎn).下面分別對這三個(gè)過程進(jìn)行介紹.

3.1 形成屬性間具有交互關(guān)系的數(shù)據(jù)集

之前的大部分研究都是在獨(dú)立同分布基礎(chǔ)上進(jìn)行的.然而在現(xiàn)實(shí)的數(shù)據(jù)中，屬性之間或多或少都會(huì)存在一些相互作用，傳統(tǒng)的K-means算法忽略了這些交互關(guān)系.下面對屬性間的交互關(guān)系進(jìn)行形式化表示，并舉例說明.

前面提到數(shù)值數(shù)據(jù)可以基本表示為一個(gè)信息表的格式，本文選取Iris數(shù)據(jù)集中的一個(gè)片段為例，6個(gè)對象具有4個(gè)屬性(即萼片長度a1，萼片寬度a2，花瓣長度a3，花瓣寬度a4)，分為三類，具體信息如表1所示.

表1 鳶尾花數(shù)據(jù)片段TTable 1 Data fragment T of Iris

第1步.構(gòu)建新的Pearson相關(guān)系數(shù)公式

研究變量之間的交互作用的一種傳統(tǒng)方法是通過Pearson相關(guān)系數(shù)測試變量之間的線性關(guān)系[17，18].因此，本文利用Pearson相關(guān)系數(shù)公式來計(jì)算屬性之間的交互關(guān)系，計(jì)算公式見公式(2).

(2)

其中，am和an為不同的屬性列，U為數(shù)據(jù)集中的對象個(gè)數(shù)，fm(u)為屬性am對應(yīng)的所有屬性值，μm為屬性am下所有屬性值的均值.

但是，這里主要考慮屬性之間的重要的交互關(guān)系而不是涉及所有的這些關(guān)系.因此基于p值越小相關(guān)性越顯著的原則，對原本公式進(jìn)行了修正，這里選用統(tǒng)計(jì)學(xué)中常用的0.05作為p值得劃分點(diǎn)，修正后的公式見公式(3).

(3)

第2步.計(jì)算屬性間的交互關(guān)系

由第1步得到屬性間修正后的公式(3)，進(jìn)而計(jì)算出不同屬性之間的相關(guān)系數(shù)為：

α(a1|a2，a3，a4)=(0.000 0.000 0.814)

α(a2|a1，a3，a4)=(0.000 0.000 0.000)

α(a3|a1，a2，a4)=(0.000 0.000 0.976)

α(a4|a1，a2，a3)=(0.814 0.000 0.976)

可以看出就數(shù)據(jù)片段T而言，屬性a2和其他屬性之間的相關(guān)系數(shù)為0，即無顯著相關(guān)，屬性a1和屬性a3之間也無顯著相關(guān).

第3步.將交互關(guān)系映射到原始數(shù)據(jù)集

由第2步得到不同屬性之間的相關(guān)系數(shù)后，利用公式將屬性之間的相關(guān)系數(shù)映射到對象之間，即映射到原始數(shù)據(jù)集上，具體公式見公式(4).

(4)

其中，fm(u)為屬性am對應(yīng)的所有屬性值，ω為數(shù)據(jù)集中特征屬性的個(gè)數(shù)，α(m|ni)表示屬性am和屬性ani之間的相關(guān)系數(shù)，即New_Cor(am，ani).

表2 新鳶尾花數(shù)據(jù)片段TcTable 2 New data fragment Tc of Iris

將第2步計(jì)算出來的屬性間的相關(guān)系數(shù)，利用公式(4)映射到原始數(shù)據(jù)集的對象之間，形成一個(gè)能夠體現(xiàn)屬性交互關(guān)系的新數(shù)據(jù)集Tc，具體結(jié)果如表2所示.

3.2 生成高密度領(lǐng)域和非噪聲領(lǐng)域

傳統(tǒng)K-means算法隨機(jī)地選擇初始聚類中心，對于中心點(diǎn)的選取比較敏感，容易陷入局部最優(yōu)且準(zhǔn)確率低.Min_max方法降低了對初始聚類中心的敏感性，提高了聚類結(jié)果的準(zhǔn)確率.但是，Min_max方法在第一個(gè)初始聚類中心點(diǎn)選擇上依然是隨機(jī)的，可能因選到離群點(diǎn)而影響準(zhǔn)確率和迭代次數(shù).針對這個(gè)問題，賴玉霞等人通過設(shè)定高密度區(qū)域[19]，然后在區(qū)域內(nèi)利用Min_max方法來選取初始中心點(diǎn)，這樣能夠很好解決第一個(gè)點(diǎn)選到離群點(diǎn)的問題.但是這樣得到的點(diǎn)過于稠密，容易造成聚類沖突，從而降低了聚類結(jié)果的質(zhì)量.熊忠陽等人針對這一問題，提出了一種最大距離積法[20]，能夠在高密度領(lǐng)域內(nèi)選點(diǎn)更加合理分散，但始終基于高密度領(lǐng)域，所以對于聚類效果的提升還是相對有限.本文僅僅在高密度領(lǐng)域內(nèi)選取第一個(gè)點(diǎn)，并且為了避免后面的選點(diǎn)也會(huì)因Min_max方法的思想而選到噪聲點(diǎn)，所以又設(shè)立了一個(gè)非噪聲領(lǐng)域，有效避免了噪聲點(diǎn)的選擇，具體步驟如下：

第1步.密度計(jì)算

數(shù)據(jù)集中對象的密度即以每個(gè)對象為圓心，以數(shù)據(jù)集中任意兩點(diǎn)間距離的平均值為半徑的圓內(nèi)包含其它對象的個(gè)數(shù).包含的個(gè)數(shù)越多，說明該對象的密度越大.

這里的半徑為對象間距離總和除以從數(shù)據(jù)集中任意取兩個(gè)對象的所有排序次序，具體公式見公式(5).

(5)

其中，N為數(shù)據(jù)集的總個(gè)數(shù)，d(Oi，Oj)為對象Oi和對象Oj的歐式距離.

而對象Oi的密度為：以O(shè)i為圓心，以avgDist為半徑的圓內(nèi)(含圓上)所包含的對象的個(gè)數(shù)，即滿足條件d(Oi，Oj)≤α×avgDist時(shí)，則說明對象Oj在以O(shè)i為圓心的圓內(nèi)，具體密度公式見公式(6).

(6)

第2步.生成高密度領(lǐng)域

高密度領(lǐng)域即高于平均密度一定倍數(shù)的數(shù)據(jù)對象組成的集合.在第1步中可以根據(jù)公式(5)和公式(6)計(jì)算出不同對象的密度，平均密度avgDens即以所有對象為圓心的圓內(nèi)(含圓上)包含的對象的個(gè)數(shù)除以數(shù)據(jù)集中對象的總個(gè)數(shù)，具體公式見公式(7).

(7)

根據(jù)公式(7)計(jì)算出的數(shù)據(jù)集中對象的平均密度，可以定義高于平均密度η倍的數(shù)據(jù)對象組成的集合為高密度領(lǐng)域，這里的η為高密度領(lǐng)域的調(diào)節(jié)系數(shù)，一般η≥1.

第3步.生成非噪聲領(lǐng)域

非噪聲領(lǐng)域即數(shù)據(jù)集中排除噪聲點(diǎn)(離群點(diǎn))的領(lǐng)域，這里根據(jù)第2步中公式(7)計(jì)算出的平均密度，定義低于平均密度ε倍的數(shù)據(jù)對象組成的集合為噪聲點(diǎn)，這里的ε為噪聲點(diǎn)調(diào)節(jié)系數(shù)，一般0<ε<1.

3.3 選取初始中心點(diǎn)

NonIID-DDMMK-means算法在初始中心點(diǎn)的選擇上主要是基于Min_max方法的思想，該方法的大體過程如下所示.

Input：數(shù)據(jù)集O，聚類個(gè)數(shù)K

Output：K個(gè)初始聚類中心點(diǎn)C

Step1.從數(shù)據(jù)集中隨機(jī)找一個(gè)點(diǎn)O1作為第一個(gè)初始中心點(diǎn)C1，即C1=O1；

Step2.遍歷數(shù)據(jù)集中的其他對象，分別計(jì)算各個(gè)樣本點(diǎn)與第一個(gè)初始中心點(diǎn)C1的距離，找到一個(gè)距離C1最遠(yuǎn)的點(diǎn)O2作為第二個(gè)初始中心點(diǎn)C2；

Step3.遍歷剩余的所有對象，分別計(jì)算它們與C1和C2的距離，記為di1和di2.令其中較小值為min(di1，di2)，并將較小值都存入集合D中.接著，計(jì)算集合D中所有距離的最大值為max(min(di1，di2))，記為O3；

Step4.重復(fù)上面的操作，直到找到K個(gè)初始中心點(diǎn).

可以發(fā)現(xiàn)Min_max方法在第一個(gè)點(diǎn)的選擇上依然是隨機(jī)的.針對這一問題，本文在高密度領(lǐng)域中對第一個(gè)初始聚類中心進(jìn)行確認(rèn)，這里并不是選取高密度領(lǐng)域內(nèi)密度最大的點(diǎn)作為第一個(gè)初始聚類中心點(diǎn)，而是選擇高密度領(lǐng)域內(nèi)距離樣本集中心最遠(yuǎn)的點(diǎn)作為第一個(gè)初始聚類中心點(diǎn)，這樣的選點(diǎn)更加符合聚類分布的特點(diǎn).樣本集的中心即樣本中所有對象的均值，具體見公式(8).

(8)

在第一個(gè)初始聚類中心確認(rèn)之后，使用Min_max方法對剩余的點(diǎn)進(jìn)行選取，這里本文設(shè)立了一個(gè)非噪聲領(lǐng)域，不僅可以防止選到的點(diǎn)為噪聲點(diǎn)而影響聚類結(jié)果的情況，也可以防止所有的點(diǎn)都在高密度領(lǐng)域內(nèi)選取，而導(dǎo)致的選點(diǎn)過于稠密，容易造成聚類沖突，從而降低了聚類結(jié)果的質(zhì)量等問題的發(fā)生.

3.4 NonIID-DDMMK-means算法描述

綜合上述3個(gè)過程，下面給出NonIID-DDMMK-means算法的整體描述：

Input：數(shù)據(jù)集O，聚類個(gè)數(shù)K

Output：完成聚類的K個(gè)簇

Step1.對數(shù)據(jù)集O，根據(jù)3.1小節(jié)中的計(jì)算過程來計(jì)算每一列屬性之間的相關(guān)系數(shù)，并映射到數(shù)據(jù)集的對象之間，形成新的能夠體現(xiàn)屬性間交互關(guān)系的數(shù)據(jù)集.

Step2.將得到的數(shù)據(jù)集按照3.2小節(jié)中的步驟來計(jì)算出它的平均密度，并調(diào)節(jié)η和ε的值來生成合適的高密度領(lǐng)域和非噪聲領(lǐng)域.

Step3.按照3.3小節(jié)中的思想，在高密度領(lǐng)域中選取一個(gè)距離樣本集中心最遠(yuǎn)的點(diǎn)作為第一個(gè)初始中心點(diǎn)，然后在非噪聲領(lǐng)域使用Min_max方法選擇其它初始中心點(diǎn)，從而得到K個(gè)初始聚類中心.

Step4.從Step 3中得到的初始中心點(diǎn)出發(fā)，執(zhí)行K-means算法，得到聚類結(jié)果.

4 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)環(huán)境：硬件：Intel(R)Core(TM)i7-6700 CPU@3.40GHz，8GB的內(nèi)存；軟件：VirtualBox虛擬機(jī)(Linux系統(tǒng))，集成開發(fā)軟件Python3.6，Pycharm2017.實(shí)驗(yàn)采用的數(shù)據(jù)集：本文選用UCI中的Iris、Parkinsons、Blood數(shù)據(jù)集.

表3 測試數(shù)據(jù)集信息Table 3 Details of test data

在獨(dú)立同分布下采用傳統(tǒng)K-means算法(OR-K)，原始Min_max方法(OR-MMK)以及文獻(xiàn)[5-7]中的算法對三個(gè)數(shù)據(jù)集進(jìn)行聚類測試.在非獨(dú)立同分布下采用傳統(tǒng)K-means算法(CR-K)，原始Min_max方法(CR-MMK)，文獻(xiàn)[5,19,20]中的方法以及本文算法(CR-DDMMK)對三個(gè)數(shù)據(jù)集進(jìn)行聚類測試.為提高數(shù)據(jù)可比性，在進(jìn)行聚類測試之前，我們對原始數(shù)據(jù)集T和具有交互關(guān)系的數(shù)據(jù)集Tc的每一列進(jìn)行歸一化，這里采用Z-Score標(biāo)準(zhǔn)化.其中Iris、Parkinsons、Blood數(shù)據(jù)集的信息特征如表3所示.

4.1 驗(yàn)證聚類準(zhǔn)確率的提升

實(shí)驗(yàn)中對獨(dú)立同分布下的OR-K算法、OR-MMK算法以及文獻(xiàn)[5-7]中的算法和非獨(dú)立同分布下的CR-K算法、CR-MMK算法以及本文的CR-DDMMK算法在三個(gè)數(shù)據(jù)集上進(jìn)行驗(yàn)證比較，這里本文取20次實(shí)驗(yàn)的平均值，具體結(jié)果如圖1所示.

圖1 聚類準(zhǔn)確率對比Fig.1 Contrast of clustering accuracy

從圖1中可以看出非獨(dú)立同分布下的聚類準(zhǔn)確率整體要高于獨(dú)立同分布下的結(jié)果.其中，Iris數(shù)據(jù)集在非獨(dú)立同分布下的CR-K算法低于獨(dú)立同分布下的OR-MMK算法以及文獻(xiàn)[5-7]中的算法主要是因?yàn)槠涫艹跏贾行狞c(diǎn)影響較大，不當(dāng)?shù)某跏贾行狞c(diǎn)可能會(huì)導(dǎo)致聚類結(jié)果準(zhǔn)確率較差.為了進(jìn)一步的驗(yàn)證，本文對Iris數(shù)據(jù)集下的OR-K算法和CR-K算法進(jìn)行詳細(xì)對比，具體如表4所示.

表4 兩種算法在Iris數(shù)據(jù)集上的結(jié)果Table 4 Results of the two algorithms on the Iris data set

從表4中可以看出Iris數(shù)據(jù)確實(shí)受初始中心點(diǎn)的影響較大，不僅如此，還可以看出在獨(dú)立同分布下的OR-K算法的準(zhǔn)確率上限為84.67%，而非獨(dú)立用分布下的CR-K算法的準(zhǔn)確率上限為93.33%，這也證實(shí)了非獨(dú)立同分布思想的有效性.并且本文的在非獨(dú)立同分布下對Min_max方法進(jìn)行優(yōu)化的NonIID-DDMMK-means算法在準(zhǔn)確率上較CR-MMK算法也有一定的提升.

對于Parkinsons和Blood數(shù)據(jù)集，從圖1中可以看出其受初始聚類中心的影響相對較小，獨(dú)立同分布下的OR-MMK算法和文獻(xiàn)[5-7]中的算法對于聚類準(zhǔn)確率的提升效果不明顯，而非獨(dú)立同分布下的CR-K算法和CR-MMK算法以及本文算法都較OR-K算法有一個(gè)大幅的提升，這主要得益于非獨(dú)立同分布思想的有效性.并且可以發(fā)現(xiàn)本文算法較CR-MMK算法在這兩個(gè)數(shù)據(jù)集中同樣有進(jìn)一步的提升，這也證實(shí)了本文算法的有效性.

4.2 驗(yàn)證聚類效果的提升

實(shí)驗(yàn)中對非獨(dú)立同分布下的CR-K算法、文獻(xiàn)[19,20]中的方法以及本文算法在非獨(dú)立同分布下的三個(gè)數(shù)據(jù)集上進(jìn)行驗(yàn)證比較，取20次實(shí)驗(yàn)的平均值，聚類平方誤差和越小說明聚類效果越佳.由于Iris數(shù)據(jù)集與其它兩個(gè)數(shù)據(jù)集的數(shù)值范圍相差較大，所以將其分開展示，具體如圖2-圖3所示.

圖2 Iris聚類效果對比Fig.2 Contrast of clustering effect on Iris圖3 Parkinsons和Blood聚類效果對比Fig.3 Contrast of clustering effect on Parkinsons and Blood

從圖2中可以看出，在非獨(dú)立同分布下的Iris數(shù)據(jù)集中用文獻(xiàn)[19,20]中的方法能夠有效降低聚類平方誤差和，提升聚類效果.同時(shí)，驗(yàn)證了文獻(xiàn)[20]中的方法較文獻(xiàn)[19]的確有所提升，但是選點(diǎn)還是有些稠密，因此可以發(fā)現(xiàn)本文的算法在使用雙領(lǐng)域思想后能夠較文獻(xiàn)[20]有更進(jìn)一步的提升.

從圖3中可以看出，在非獨(dú)立同分布下的Parkinsons和Blood數(shù)據(jù)集中用文獻(xiàn)[19，20]中的方法同樣能夠降低聚類平方誤差和.其中，文獻(xiàn)[19]方法和文獻(xiàn)[20]方法得出來的值是一樣的，這主要是因?yàn)檫@兩個(gè)數(shù)據(jù)集的初始聚類中心點(diǎn)的個(gè)數(shù)為2，兩個(gè)文獻(xiàn)中的方法在取前兩個(gè)初始點(diǎn)時(shí)的思想是相同的.在這兩個(gè)數(shù)據(jù)集中，本文的算法較前兩者仍然有進(jìn)一步的提升，這也驗(yàn)證了雙領(lǐng)域思想對于聚類效果提升方面的有效性.

4.3 驗(yàn)證運(yùn)算效率的提升

實(shí)驗(yàn)中對非獨(dú)立同分布下的CR-K算法、CR-MMK算法、文獻(xiàn)[5]和文獻(xiàn)[19]中的方法以及本文算法在非獨(dú)立同分布下的三個(gè)數(shù)據(jù)集上進(jìn)行驗(yàn)證比較，取20次實(shí)驗(yàn)的平均值，迭代次數(shù)越少說明運(yùn)算效率越高，具體結(jié)果如圖4所示.

圖4 迭代次數(shù)對比Fig.4 Contrast of iteration number

從圖4中可以發(fā)現(xiàn)，在Iris數(shù)據(jù)集中迭代次數(shù)整體呈一個(gè)下降趨勢，但是在Parkinsons和Blood數(shù)據(jù)集中，CR-MMK算法、文獻(xiàn)[5]和文獻(xiàn)[19]中的方法較最初的CR-K算法有一些波動(dòng)，這主要是因?yàn)镸in_max方法以及最大距離的方法在取第二個(gè)點(diǎn)時(shí)很容易取到噪聲點(diǎn)，并且過于稠密的初始中心點(diǎn)也會(huì)影響運(yùn)算效率.而本文的方法設(shè)立了雙領(lǐng)域，并在第一個(gè)初始中心點(diǎn)的選擇上更加符合聚類分布的特點(diǎn)，所以迭代次數(shù)要更少，運(yùn)算效率更高.

5 結(jié) 論

針對傳統(tǒng)K-means算法在進(jìn)行數(shù)據(jù)聚類時(shí)，往往忽略了數(shù)據(jù)集中屬性之間的交互關(guān)系以及其對初始中心點(diǎn)的選取比較敏感，不當(dāng)?shù)倪x入容易導(dǎo)致局部最優(yōu)、聚類不穩(wěn)點(diǎn)、收斂速度慢等問題，本文提出了一種非獨(dú)立同分布下基于雙領(lǐng)域思想和Min_max方法相結(jié)合的優(yōu)化K-means初始中心選擇的方法.該方法首先通過修改后的Pearson相關(guān)系數(shù)公式來計(jì)算不同屬性之間的交互關(guān)系并映射到原始數(shù)據(jù)集的對象之間，從而形成能夠體現(xiàn)交互關(guān)系的新數(shù)據(jù)集.然后通過設(shè)立雙領(lǐng)域來避免選到噪聲點(diǎn)以及選點(diǎn)過于稠密等問題.最后利用優(yōu)化后的Min_max方法找到全部初始中心點(diǎn)并完成聚類.實(shí)驗(yàn)表明，本文提出的NonIID-DDMMK-means算法具有較高的準(zhǔn)確率、較好的聚類效果以及相對較少的迭代次數(shù).因此，本文提出的非獨(dú)立同分布下的聚類算法是有效的，可行的.