[發明專利]一種基于MIC改進的k-modes聚類方法

在審

• 申請號: 202110171636.2
• 申請日: 2021-02-08
• 公開（公告）號: CN112861969A
• 公開（公告）日: 2021-05-28
• 發明（設計）人: 李明媚;裘奕婷;文成林;袁洢苒;徐曉濱
• 申請（專利權）人: 杭州電子科技大學
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06F16/2458
• 代理公司: 浙江千克知識產權代理有限公司 33246
• 代理人: 周希良

本發明公開了一種基于MIC改進的k?modes聚類方法。本發明在傳統k?modes聚類方法上，引入MIC的概念，重新定義了一種新的距離度量方式。該方法考慮了對象某個屬性值本身的不同，又考慮了對象其它屬性對該屬性值的影響，可以通過計算它們之間的MIC值來體現屬性、對象之間的相關度，MIC值越大代表相關性越強反之越弱，使之更符合實際問題情況。通過基于MIC的距離公式計算每一個對象到類中心的距離，并將其分配到距離最小的類中心所在的類。得到新的劃分，直到每個對象所屬的類不再改變。通過對UCI數據集進行聚類仿真，結果表明基于MIC的k?modes算法能有效地提高聚類算法精度，驗證了本發明的有效性。

技術領域

本發明屬于數據挖掘領域，具體涉及一種基于MIC改進的k-modes聚類方法。

背景技術

隨著互聯網的快速發展，數據量爆炸式增長，給數據挖掘帶來更大的發展機遇。其中聚類分析是數據挖掘中的一種重要工具，作為一種無監督的學習方法，已廣泛應用于各種各樣的科學領域，例如市場營銷、生物基因學、信息學等。但是傳統的聚類分析只適用于數值型數據，例如k-means算法，是基于數值間的歐氏距離度量進行聚類。這種僅局限于數值型數據的聚類，不能準確地表達對象間的數據結構關系，而且忽視了分類對象屬性中的信息，因此并不適合分類型數據。如何對分類型數據集進行聚類，成為許多學者研究的一個重要課題。

1998年，Huang提出了一種針對分類型數據的k-modes算法，這一算法是k-means聚類方法的擴展。該算法采用簡單的0-1匹配方法來計算不同對象在同一分類屬性下兩個屬性值之間的距離。由于其算法簡便，因此被廣泛應用于科學和工業中的各個領域。但是這種采用0-1匹配的距離度量沒有把整個數據集考慮進來，而是將所有屬性視為同等地位，忽視了類中對象的區別，導致距離度量不準確。針對這個問題，許多學者從不同角度提出了改進方法。Ahmad等人改進了Huang提出的距離函數，通過屬性值之間的共現程度來刻畫每兩個屬性值之間的距離，并且提出一種新的適合混合屬性聚類的算法。張小宇等通過圖形聚類理論中的連接度來度量字符型屬性值之間的相似性。吳潤秀等利用樣本互信息來刻畫數據對象屬性之間的相互關系。雖然上述方法在一定程度上對k-modes聚類算法原有的距離度量進行了改善，但是Ahmad等人所定義的距離公式只考慮到同一個屬性下不同屬性值的差異；張小宇等所定義的基于圖形聚類連接度的距離公式計算復雜度較高；吳潤秀等所提出的基于互信息的距離公式，同樣也面臨著計算復雜度較高，互信息聯合概率難求的問題，并且在所有屬性之間的影響關系上較弱。

最大信息系數(Maximal information coefficient)，簡稱為MIC，可以檢測變量對象之間潛在的關系。MIC是兩變量間相關度的較好度量，且具備廣泛性和公平性兩種重要的屬性。MIC可以用來體現數據對象屬性之間的相互關系，每兩個數據對象之間的距離是由其各個屬性值之間的距離決定，每兩個數據對象屬性值之間的距離又是由其他屬性值之間的距離來確定，一個屬性對另一個之間的距離影響程度是由MIC值的大小來決定的，MIC值越大代表相關性越強反之越弱。因此可以考慮到整體的對象屬性與某一對象屬性之間的聯系。

發明內容

本發明針對上述現有技術的不足，提出了一種基于MIC改進的k-modes聚類方法。本發明提供了一種新的距離度量方式，用最大信息系數MIC來體現數據對象屬性之間的相關度，MIC值越大代表相關性越強反之越弱。此方法可以提高傳統k-modes的聚類精度。

為實現上述目的，本發明的技術方案是：

本發明包括以下步驟：