基于Minkowski距離的一致聚類改進(jìn)算法及應(yīng)用研究

徐德剛　徐戲陽　陳曉　趙盼磊　蘇志芳　謝永芳　陽春華

摘要：針對一致聚類算法中聚類數(shù)目判斷不準(zhǔn)確、聚類速度慢等問題，通過集成復(fù)雜網(wǎng)絡(luò)中的Newman貪婪算法與譜聚類算法，提出了一種新的基于Minkowski距離的一致聚類算法。該算法利用Minkowski距離刻畫樣本間的相似度，根據(jù)隨機(jī)游走策略，結(jié)合不同數(shù)據(jù)的特征值分布分析方法進(jìn)行聚類，實現(xiàn)聚類數(shù)目的自動識別。實驗仿真說明算法具有較少的運算時間及較高的聚類精度。結(jié)合實際銅礦泡沫浮選過程特點，將該算法應(yīng)用于浮選工況分類，進(jìn)一步驗證了算法的有效性。

關(guān)鍵詞：一致聚類；Minkowski距離；一致矩陣；聚類數(shù)目；工況識別

中圖分類號：TP273 文獻(xiàn)標(biāo)識碼：A

聚類分析作為一種有效的數(shù)據(jù)處理方法，在復(fù)雜工業(yè)工程中得到了廣泛關(guān)注。近年來涌現(xiàn)出了多種聚類分析方法，包括層次聚類算法、劃分式聚類算法（如K-modes-Huang算法等）、基于網(wǎng)格和密度的聚類算法（如網(wǎng)格密度等值線聚類算法、基于移位網(wǎng)格概念的密度和網(wǎng)格的聚類算法SGCE）等。這些聚類方法在多個領(lǐng)域得到廣泛應(yīng)用，其理論也得到不斷的豐富和發(fā)展。

但是對不同結(jié)構(gòu)特征的數(shù)據(jù)進(jìn)行聚類分析時，現(xiàn)有的聚類方法遇到了難題，如相似度矩陣的選取問題、聚類數(shù)目的自動確定等。而一致聚類方法的提出，成為解決聚類問題的一種重要分析方法。該方法也稱作聚類集成或劃分算法，即針對某一特定的數(shù)據(jù)獲得多種數(shù)目的不同聚類結(jié)果，并從中選取最能反映聚類信息的類別。在確定聚類數(shù)目方面，一致聚類方法具有特色，并為基因微陣數(shù)據(jù)、文本數(shù)據(jù)等聚類問題的解決提供了很好的思路。由于聚類過程中聚類數(shù)目的判斷標(biāo)準(zhǔn)不盡相同，適用的領(lǐng)域也不同，其中最具有代表性的兩種一致聚類方法是結(jié)合重采樣或交叉驗證等技術(shù)的一致聚類方法和基于迭代的一致聚類方法。但這兩種一致聚類算法也存在聚類數(shù)目識別不準(zhǔn)確等問題，主要是源于其重采樣方法中最優(yōu)的采樣次數(shù)及迭代方法中的迭代次數(shù)不能有效且最優(yōu)設(shè)定。

本文提出了一種新的基于Minkowski距離的一致聚類分析方法，充分利用數(shù)據(jù)特征分布特點，自動識別聚類的數(shù)目，從而解決一致聚類中數(shù)目不能自動設(shè)定的問題。通過Minkowski距離優(yōu)化調(diào)節(jié)一致矩陣參數(shù)，能夠在不同的度量下獲得有效的聚類結(jié)果，且由于算法本身機(jī)制集成了多種聚類算法，該法還具備一定的魯棒性。仿真結(jié)果表明本文算法在聚類數(shù)目的確定精度和準(zhǔn)確度上優(yōu)于其他一致聚類算法。

當(dāng)前銅礦泡沫浮選過程生產(chǎn)環(huán)境惡劣且長期依靠人工肉眼現(xiàn)場監(jiān)測，受到工人主觀經(jīng)驗影響，易導(dǎo)致浮選工況操作波動異常，引起浮選藥劑等資源和能源的浪費。隨著計算機(jī)技術(shù)、圖像處理技術(shù)、智能控制等領(lǐng)域的迅速發(fā)展，機(jī)器視覺技術(shù)在礦物泡沫浮選領(lǐng)域得到越來越廣泛的應(yīng)用，為浮選生產(chǎn)過程提供豐富的實時監(jiān)控信息。

通過視覺圖像系統(tǒng)及液位、壓力等工藝參數(shù)傳感器測量，浮選生產(chǎn)現(xiàn)場積累了大量反映礦物生產(chǎn)狀態(tài)的泡沫圖像數(shù)據(jù)和生產(chǎn)操作信息，如何有效地分析和利用這些數(shù)據(jù)對浮選過程工況的分類、識別及過程調(diào)控具有重要意義。為此，本文提出了基于Minkowski距離的一致聚類分析方法，并應(yīng)用到銅礦泡沫浮選過程工況的判別，取得了較好的聚類效果，有助于實現(xiàn)生產(chǎn)實時工況的自動判別。

1 一致聚類方法

常規(guī)聚類分析過程中，由于單一的聚類算法無法獲得對所有數(shù)據(jù)的最優(yōu)聚類結(jié)果，融合多種聚類算法的一致聚類方法引起研究人員的關(guān)注。一致聚類具體算法流程如圖1所示。

利用聚類算法集成的一致聚類方法的出發(fā)點主要通過進(jìn)行多次采樣或結(jié)合多種聚類算法對數(shù)據(jù)進(jìn)行分析，獲得反映數(shù)據(jù)類別信息的一致矩陣，從而進(jìn)行數(shù)據(jù)的劃分。一致聚類算法已在基因數(shù)據(jù)分析及文本聚類分析等應(yīng)用中取得了較好的效果。當(dāng)前一致聚類主要有兩類算法：基于重采樣的一致聚類方法和基于迭代的一致聚類分析方法。

1.1 基于重采樣的一致聚類方法

基于重采樣的一致聚類算法輸入樣本數(shù)據(jù)為D={e₁，e₂，…，e_N}，聚類方法采用譜聚類方法，一般把重采樣分段采樣比例設(shè)為80%，采樣次數(shù)為H，聚類數(shù)目集合為K={k₁，k₂，…，k_j}（j=length（K），即設(shè)定聚類數(shù)目序列長度），輸出為聚類數(shù)目集合D，一致矩陣為M。基于重采樣的一致聚類算法流程如下所示：

結(jié)合重采樣或交叉驗證等技術(shù)來模擬原始數(shù)據(jù)的擾動，該法是通過多次運行某一聚類算法（例如隨機(jī)選取起始點的K-means或基于模型的貝葉斯聚類方法等）來獲得類別穩(wěn)定性，提供了一種可視化的途徑來觀察類別數(shù)目、類別成員以及類別邊界等信息。

大量實驗表明，盡管該方法適合基因表達(dá)數(shù)據(jù)的聚類，但對其他類別聚類效果不佳，其原因為：重采樣隨機(jī)采樣大部分樣本，采樣次數(shù)以及采樣比例對算法影響大；基于重采樣的一致聚類分析方法中確定聚類數(shù)目的準(zhǔn)則不統(tǒng)一，算法中△（k）為不同聚類數(shù)目下CDF曲線與橫軸包圍面積的變化量，其最大值對應(yīng)最終的聚類數(shù)目，將△（k）變化值作為判斷聚類數(shù)目的標(biāo)準(zhǔn)不確定。針對這些問題，一些學(xué)者提出了基于迭代的一致聚類方法。

1.2 基于迭代的一致聚類分析方法

該方法遵循一致聚類方法的基本思路，不同之處在于不需要對樣本進(jìn)行重采樣，而是利用了多種聚類算法分別對同一樣本數(shù)據(jù)進(jìn)行聚類，獲得一致矩陣，并通過將隨機(jī)游走的策略引入一致矩陣的分析中，獲得了概率轉(zhuǎn)移矩陣，然后通過分析概率轉(zhuǎn)移矩陣的特征值進(jìn)而確定聚類的數(shù)目。如果矩陣特征值不能明顯反映聚類信息，則將一致矩陣代替相似度矩陣進(jìn)行多次迭代，最終獲得能夠反映聚類數(shù)目的特征值分布。該法采用多種聚類算法，克服了僅采用一種聚類算法的局限性，但仍存在缺陷，包括迭代的次數(shù)及迭代終止的條件不明確性，相似度矩陣的確定方法單一，僅依賴高斯距離公式進(jìn)行標(biāo)度等問題。

針對上述兩類聚類方法存在的問題，本文通過分析這兩類方法的特點，提出了基于Minkowski距離的一致聚類分析方法，有效地避免多次迭代，能較準(zhǔn)確地獲得聚類數(shù)目信息。

2 基于Minkowski距離的一致聚類算法（CCBM）

本文提出了一種基于Minkowski距離的一致聚類數(shù)目自動識別為核心算法的一致聚類方法（CCBM-consensusclusteringbasedMinkowskidis-tance）。該方法集成多種聚類算法，與以上兩種一致聚類方法不同之處在于相似度矩陣的構(gòu)建及聚類算法的選擇上。為了克服重采樣、迭代方法采樣數(shù)目和迭代次數(shù)不能有效的最優(yōu)確定等缺點，考慮到Minkowski距離公式能夠準(zhǔn)確刻畫數(shù)據(jù)大范圍的相似度量信息，本文方法采用Minkowski距離對輸入數(shù)據(jù)進(jìn)行了不同的度量，從而完成參數(shù)設(shè)定并對相似度矩陣進(jìn)行一致聚類，并確定最能反映聚類信息的相似度度量，不需要迭代即能較準(zhǔn)確獲得聚類數(shù)目信息。下面詳細(xì)說明本文所提出的方法算法流程，如圖2所示。

2.1 Minkowski距離函數(shù)的設(shè)定

相對于常規(guī)的歐式距離或高斯距離，本文采用Minkowski距離公式，如式（1）-式（2）。其中，x和y為n維樣本點，p和？為距離調(diào)整參數(shù)。當(dāng)p取1時，式（1）為曼哈頓距離，刻畫的是數(shù)據(jù)i與j橫縱坐標(biāo)差值的絕對值之和；當(dāng)p取2時，式（1）為歐式距離，刻畫的是數(shù)據(jù)i與。j的最短距離，即對角線距離；當(dāng)p取無窮大時，式（1）為切比雪夫距離，刻畫的是數(shù)據(jù)i與j在某維度上的最大差值；p也可取其他值（如p=0.5，0.1等小于1的數(shù)）。不同p值構(gòu)建的Minkowski距離，利用算法分析會產(chǎn)生不同的聚類效果。式（2）中a為可調(diào)參數(shù)，通過調(diào)整p值及？值，該距離公式能夠從不同角度反映數(shù)據(jù)（主要是聲值影響）的相似度信息。

本文設(shè)定3種不同的p值（p分別取1，2，3）及5類不同？值（？分別取0.1，0.2，0.5，0.8，0.9），通過公式（1）-（2）獲得不同相似度矩陣的構(gòu)建（共15種），并對其進(jìn)行聚類分析。由于以上構(gòu)建的15種距離能夠較全面地刻畫數(shù)據(jù)間不同角度的相似信息，因此可以結(jié)合矩陣特征值分析方法，獲得數(shù)據(jù)不同的特征值分布，為獲得數(shù)據(jù)的聚類數(shù)目信息提供依據(jù)。

2.2 聚類算法的集成

聚類算法的集成需要考慮不同聚類算法的特點，選擇合適的聚類算法對一致聚類算法的有效集成至關(guān)重要。譜聚類算法作為劃分式聚類算法之一，能夠在任意形狀的樣本空間上聚類，并且能收斂于全局最優(yōu)解。而Newman貪婪算法作為復(fù)雜網(wǎng)絡(luò)層次式分析方法，由于其收斂速度快等優(yōu)點，在數(shù)據(jù)的聚類分析中有著廣泛的應(yīng)用。本文主要融合兩種不同Laplacian矩陣構(gòu)建的譜聚類算法（如式（3）-式（4））與復(fù)雜網(wǎng)絡(luò)中的Newman貪婪算法的改進(jìn)算法，一定程度上避免了聚類算法復(fù)雜度高的缺點。其中，D為將相似度矩陣每行之和賦值到對角線上的對角矩陣，L為相似度矩陣。

2.3 聚類數(shù)目的識別

2.3.1 聚類數(shù)目的識別準(zhǔn)則

由于相似矩陣可看作一個無向圖中節(jié)點之間的鄰接矩陣，樣本數(shù)可看作圖中的節(jié)點數(shù)，相似矩陣中的權(quán)值可看作圖中節(jié)點之間的邊，并可以利用邊的粗細(xì)代表權(quán)值的大小。

在建立的無向圖中引入隨機(jī)游走策略，獲得轉(zhuǎn)移概率矩陣P，P=D^-1S，其中S為相似矩陣，D=diag（S·e），e是一個值全為1的向量。令σ（P）={1=λ₁≥λ₂≥…≥λ_n）作為P的譜分布，即特征值分布。經(jīng)數(shù)學(xué)證明如果沒有子類的劃分，1=λ₁≥λ₂≥…≥λ_n中會有k個特征值[λ₁，…，λ_k]接近于1，而特征值λ_k與λ2_k+1之間的相對間距可以決定數(shù)據(jù)聚類的數(shù)目，這就為聚類數(shù)目的合理識別提供了數(shù)學(xué)依據(jù)。

2.3.2 一致相似矩陣及其特征值分布

首先確定所選擇的聚類數(shù)目的序列，k=[k₂，k₂，…，k_n]，其中n為所選擇類別的數(shù)目，然后分別采用3.2節(jié)的三種聚類方法；根據(jù)聚類數(shù)目k_i，i∈{1，2，…，n）進(jìn)行分別聚類，共獲得3×n個聚類結(jié)果，形成一致聚類矩陣M（如果第i個節(jié)點和第j個節(jié)點分到同一類，M_ij為1，否則為0）構(gòu)建；最后將一致相似矩陣M代替相似矩陣S，按照隨機(jī)游走策略獲得轉(zhuǎn)移概率矩陣P，求得P的特征值分布，并通過特征值的分布獲得聚類信息。

2.3.3 確定聚類數(shù)目的一致聚類算法流程

提出的基于Minkowski距離的一致聚類算法確定聚類數(shù)目的具體算法流程如圖3所示。

具體步驟如下：

結(jié)合Minkowski距離函數(shù)（如式（1）-式（2））建立樣本之間不同角度的距離測量，令聲∈[1，2，3]，？∈[0.1，0.2，0.5，0.8，0.9]，以盡量覆蓋參數(shù)的取值（共3×5=15種表示相似信息的情況）。

1）對于任取的一組p值和？值，令k=[k₁，k₂，…，k_n]（依據(jù)所采用的數(shù)據(jù)規(guī)模，本文設(shè)k∈[8，9，10，11，12，13，14，15]，共8種聚類數(shù)目），對于每一k值，分別對距離刻畫的相似信息采用上述3種聚類算法進(jìn)行聚類，可得到3×8=24個聚類結(jié)果，由這24個聚類的結(jié)果構(gòu)建一致相似矩陣M_i（i∈1，2，…，15]）。

2）重新對值p和？值進(jìn)行取值，重復(fù)前一步，最后得到15個一致相似度矩陣M=[M₁，M₂，…，M₁₅]，進(jìn)而獲得相應(yīng)的轉(zhuǎn)移概率矩陣P=[P₁，P₂，…，P15₁₅]。

3）分別對轉(zhuǎn)移概率矩陣P_i（i∈[1，2，…，15]）進(jìn)行特征值分解，并根據(jù)特征值之間差值判別規(guī)則獲得聚類的數(shù)目。

3 基于Minkowski距離的一致聚類算法（CCBM）分析

3.1 聚類數(shù)目識別分析

本文算法優(yōu)越性體現(xiàn)在聚類數(shù)目的自動識別問題上，能夠?qū)?shù)據(jù)進(jìn)行分析并獲得準(zhǔn)確的聚類數(shù)目信息。為了驗證算法有效性，測試數(shù)據(jù)為標(biāo)準(zhǔn)數(shù)據(jù)庫中的UCI數(shù)據(jù)、圖形數(shù)據(jù)及人工隨機(jī)數(shù)據(jù)等代表性數(shù)據(jù)，如表1所示。

本文采用具有代表性的數(shù)據(jù)包括隨機(jī)5類（仿真中利用Matlab軟件mvnrnd函數(shù)設(shè)置均向量分別為[1，1]，[1，6]，[6，1]，[6，6]及[3.5，3.5]，對應(yīng)方差均為0.1而獲得的高斯數(shù)據(jù)）、Flame圖形數(shù)據(jù)、Iris數(shù)據(jù)及Wine數(shù)據(jù)（對維數(shù)較高的采用SVD降維），仿真結(jié)果如圖4-圖7所示。

由圖4-圖7可以發(fā)現(xiàn)，本文算法對表1中數(shù)據(jù)聚類數(shù)目的識別非常準(zhǔn)確，可有效地判斷概率轉(zhuǎn)移矩陣特征值分布（統(tǒng)計值接近于1的特征值數(shù)目）并確定聚類數(shù)目。

3.2 聚類數(shù)目結(jié)果分析

為了對比本文一致聚類方法與其他一致聚類算法的不同，針對表1的數(shù)據(jù)，分別進(jìn)行聚類分析，得到的結(jié)果如表2所示。

由表2可發(fā)現(xiàn)，基于迭代的一致聚類算法耗時最少，主要是由于其迭代次數(shù)較少且沒有重采樣和參數(shù)選擇環(huán)節(jié)，但是其判斷數(shù)據(jù)類別數(shù)目不準(zhǔn)確，如Iris數(shù)據(jù)的類別判斷，其迭代終止的準(zhǔn)則不明確，因此判斷聚類數(shù)目不可靠。基于重采樣的一致聚類算法耗時最多，主要是由于其迭代次數(shù)較大，這是為了提高精度而選擇較多迭代次數(shù)的結(jié)果，但是其判斷類別數(shù)目也不準(zhǔn)確，如隨機(jī)5類數(shù)據(jù)的類別判斷。本文算法由于要對Minkowski距離公式參數(shù)進(jìn)行選擇，故耗時多于基于迭代的一致聚類算法，但是參數(shù)選擇種類相對固定，耗時少于基于重采樣的一致聚類算法。本文算法對于表1中4類數(shù)據(jù)聚類數(shù)目的判斷準(zhǔn)確，在聚類數(shù)目的識別準(zhǔn)確性上優(yōu)于其他兩種一致聚類算法。

4 銅礦泡沫浮選的工況識別

在某企業(yè)銅礦泡沫浮選廠中銅優(yōu)粗選流程如圖8所示。銅礦石經(jīng)過球磨粉碎過程，磨礦后的礦漿首先經(jīng)過抑泥槽，后接攪拌槽，再通過粗選首槽（槽I）和粗選槽Ⅱ，其中礦物泡沫到精選過程，而礦漿到掃選過程。根據(jù)該流程生產(chǎn)工藝特點獲知，對浮選生產(chǎn)有關(guān)鍵作用的是銅優(yōu)浮選過程的粗選首槽。

在浮選過程人礦條件穩(wěn)定的情況下，首槽泡沫會隨著生產(chǎn)操作參數(shù)的改變發(fā)生變化。因此，根據(jù)浮選泡沫的表觀形狀和其帶礦量的多少，可以將銅優(yōu)浮選粗選首槽泡沫進(jìn)行工況分類，并將分類結(jié)果對應(yīng)相應(yīng)的操作變量，以給出合理的操作建議，指導(dǎo)操作。如圖9所示為浮選泡沫圖像的3種不同浮選生產(chǎn)狀態(tài)，銅礦泡沫形態(tài)的特征可以分別描述為：

A類泡沫：泡沫粒徑、形狀不規(guī)則，多為細(xì)長的扁形且以連生體存在，泡沫間的邊緣不明顯，礦化程度高，含泥多，泡沫負(fù)荷過多，泡沫顏色泛白、粘稠、穩(wěn)定度高，但泡沫尺寸小、速度慢。

B類泡沫：泡沫顏色、大小適中、形狀規(guī)則，氣泡上有堅實的礦物負(fù)荷。

C類泡沫：泡沫上負(fù)荷量減少，泡沫多為虛泡、不穩(wěn)定、易破裂或兼并。

通過現(xiàn)場觀察和生產(chǎn)指標(biāo)分析對比研究，在這3類浮選生產(chǎn)狀態(tài)中，B類狀態(tài)對應(yīng)泡沫含礦最多。由于在銅優(yōu)浮選粗選首槽已經(jīng)構(gòu)建由高分辨率工業(yè)攝像機(jī)、高頻光源及高性能工業(yè)控制計算機(jī)等設(shè)備組成的泡沫圖像采集平臺，準(zhǔn)確提取了反映生產(chǎn)工況的泡沫表征特征（包括紋理、大小、顏色等）。針對圖9所示的3類泡沫圖像特征，隨機(jī)選取了實際生產(chǎn)過程的1個月200組數(shù)據(jù)，其中A，B，C類數(shù)據(jù)分別為50，100，50組數(shù)據(jù)，對其采用基于Minkowski距離的一致聚類算法分析，一致矩陣特征值分布如圖10所示。由圖可見，可以明顯劃分為3類工況，數(shù)據(jù)聚類的結(jié)果準(zhǔn)確性高。原數(shù)據(jù)和聚類后的數(shù)據(jù)分別如圖11和圖12所示。

通過對比分析發(fā)現(xiàn)選取200組數(shù)據(jù)中只有2個誤分點，正確率達(dá)到98.5%。因此，本文所提算法可用于實際銅礦泡沫浮選過程圖像數(shù)據(jù)的有效聚類，從而有助于進(jìn)一步實現(xiàn)浮選生產(chǎn)工況的自動識別，識別浮選泡沫生產(chǎn)狀態(tài)，為浮選生產(chǎn)操作提供指導(dǎo)。

5 結(jié)論

針對常規(guī)聚類算法中相似度矩陣的選取問題、聚類數(shù)目的自動確定等問題，本文提出了基于Minkowski距離的一致聚類分析方法。該方法利用Minkowski距離公式對數(shù)據(jù)進(jìn)行不同角度度量，集成多種聚類算法進(jìn)行聚類，根據(jù)隨機(jī)游走策略，并將獲取的一致矩陣轉(zhuǎn)化為概率轉(zhuǎn)移矩陣，結(jié)合不同數(shù)據(jù)的特征值分布分析方法確定類別數(shù)目，實現(xiàn)自動聚類。通過對標(biāo)準(zhǔn)數(shù)據(jù)實驗對比表明算法具有較快的運算速度和較高的類別劃分準(zhǔn)確度。將本文算法應(yīng)用到銅礦泡沫浮選過程工況分類效果，進(jìn)一步驗證算法有效性，也為泡沫浮選工況自動識別及生成過程操作提供了指導(dǎo)信息。