基于Minkowski距離的一致聚類改進算法及應用研究

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

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

關鍵詞：一致聚類；Minkowski距離；一致矩陣；聚類數目；工況識別

中圖分類號：TP273 文獻標識碼：A

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

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

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

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

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

1 一致聚類方法

常規聚類分析過程中，由于單一的聚類算法無法獲得對所有數據的最優聚類結果，融合多種聚類算法的一致聚類方法引起研究人員的關注。一致聚類具體算法流程如圖1所示。

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

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

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

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

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

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

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

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

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

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

2.1 Minkowski距離函數的設定

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

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

2.2 聚類算法的集成

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

2.3 聚類數目的識別

2.3.1 聚類數目的識別準則

由于相似矩陣可看作一個無向圖中節點之間的鄰接矩陣，樣本數可看作圖中的節點數，相似矩陣中的權值可看作圖中節點之間的邊，并可以利用邊的粗細代表權值的大小。

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

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

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

2.3.3 確定聚類數目的一致聚類算法流程

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

具體步驟如下：

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

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

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

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

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

3.1 聚類數目識別分析

本文算法優越性體現在聚類數目的自動識別問題上，能夠對數據進行分析并獲得準確的聚類數目信息。為了驗證算法有效性，測試數據為標準數據庫中的UCI數據、圖形數據及人工隨機數據等代表性數據，如表1所示。

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

由圖4-圖7可以發現，本文算法對表1中數據聚類數目的識別非常準確，可有效地判斷概率轉移矩陣特征值分布（統計值接近于1的特征值數目）并確定聚類數目。

3.2 聚類數目結果分析

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

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

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

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

在浮選過程人礦條件穩定的情況下，首槽泡沫會隨著生產操作參數的改變發生變化。因此，根據浮選泡沫的表觀形狀和其帶礦量的多少，可以將銅優浮選粗選首槽泡沫進行工況分類，并將分類結果對應相應的操作變量，以給出合理的操作建議，指導操作。如圖9所示為浮選泡沫圖像的3種不同浮選生產狀態，銅礦泡沫形態的特征可以分別描述為：

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

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

C類泡沫：泡沫上負荷量減少，泡沫多為虛泡、不穩定、易破裂或兼并。

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

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

5 結論

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