[發明專利]一種基于相鄰點連接的數據聚類方法

在審

• 申請號: 201811395547.0
• 申請日: 2018-11-22
• 公開（公告）號: CN111209926A
• 公開（公告）日: 2020-05-29
• 發明（設計）人: 王振洲
• 申請（專利權）人: 山東理工大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明公開了一種基于相鄰點連接的數據聚類方法。通過數據變換將所有數據轉換到一個正整數范圍的網格內，將網格中每個轉換數據近似的正整數對應的位置賦值為1，其他位置賦值為0，通過迭代形態學膨脹方法對賦值為1的位置的臨近位置也賦值為1，將相鄰點連接成為連通域，用連續整數對所有連通域進行自動標識，計算出單個數據點到每個連通域的距離，通過與其距離最近的連通域的標識整數標記該數據點，對于含有噪音的數據，設置距離閾值，如果某個數據點到所有連通域的距離都大于距離閾值，那么該數據點被標記為噪音，在所有的數據點被標記以后，再將它們轉換回原來的區間范圍內。實驗結果表明本發明的聚類精度明顯高于任何一種現有聚類算法。

技術領域

本發明涉及一種基于相鄰點連接的數據聚類方法，特別是涉及一種通過相鄰點的連接生成連通域，通過計算數據點與不同連通域之間的歐式距離，決定數據點的聚類。該方法可以應用到機器學習，數據挖掘，模式識別，圖像分析以及生物信息等領域。

背景技術

信息技術的高速發展積累了大量的數據, 而這些數據后面隱藏著許多重要的信息, 為了對其進行更高層次的分析, 數據聚類是核心技術。為了發現數據中存在的各種關系和規則, 并且根據現有的數據預測未來的發展趨勢，數據聚類分析至關重要。迄今為止，聚類分析方法在數據挖掘領域已取得了較好的應用效果。此外，聚類分析還成功地應用在了模式識別 、圖像處理、計算機視覺、模糊控制等應用領域 ,并在這些領域中取得了長足的發展。 然而，聚類分析還有許多急待進一步解決的問題。(1), 量大且復雜的數據的聚類結果的精確性問題。（2），數據對象分布形狀不規則時的聚類問題。（3），噪聲數據的聚類問題。（4），對數據輸入順序的獨立性 ,也就是對于任意的數據輸入順序產生相同的聚類結果。（5），對先驗知識或參數的依賴型等問題。這些問題的存在使得我們研究更加有效的聚類方法迫在眉睫。

目前比較有名的聚類方法包括基于密度的聚類算法，K均值算法，模糊c均值算法，K中心點算法，譜聚類算法以及均值漂移聚類算法等。這些方法都有這個各自優點與不足。在列舉的這些典型聚類算法中，只有基于密度的聚類算法可以對于分布形狀不規則的數據進行魯棒地聚類。然而，當類間密度大于類內密度時，基于密度的聚類算法容易陷入類內數據的聚類。并且基于密度的聚類算法容易把數據點錯誤地歸類為噪音。K均值算法可以對高維數據進行聚類，然而它容易受到數據分布形狀的影響。此外，K均值算法是一種近似算法，因此在某些數據的聚類精度比較時，K均值算法往往比不過其他算法。模糊c均值算法，K中心點算法以及均值漂移聚類算法都是借鑒了K均值算法的思想，并且融合了新的聚類標準，從而在某些數據問題上，取得了比K均值算法更加魯棒的精度。然而這些算法和K均值算法一樣都容易受到數據分布形狀的影響。譜聚類算法是另一類廣泛使用的聚類算法，比起K均值算法，譜聚類對數據分布的適應性更強，同時聚類的計算量也小很多，因為對于量大且復雜的數據，基于迭代的均值聚類算法將相當耗時。然而，譜聚類算法的聚類精度也容易受到數據分布形狀的影響。

本發明利用相同類中相鄰數據點之間距離比不同類中相鄰數據點之間的距離更近這一共有特性，開發了一種可以對任意分布形狀的數據進行魯棒聚類的通用方法。首先，所有數據被轉換到一個正數范圍的網格內，并且近似為整數。對每個近似的整數在網格中對應的位置賦值為1，其他位置賦值為0。對被賦值為1的位置的臨近位置都賦值為1，直到相同類中數據位置連接成為一個連通域。再用連續整數對所有連通域進行自動標識。計算出某個數據點到每個連通域的距離，該數據點被標記為與距離其最近的連通域的標識整數。在所有的數據點被標記以后，再將它們轉換回原來的區間范圍內。實驗結果證明本發明的聚類精度遠遠高于其他聚類算法。

發明內容

本發明的目的是針對現有聚類算法的精度容易受到數據分布形狀的影響，提供一種基于相鄰點連接的數據聚類方法，該方法充分利用不同數據的共有特性，通過連接類內相鄰數據點形成連通域，再通過數據點到不同連通域的歐式距離對數據點進行聚類。

為了實現上述發明的目的，本發明采用下述技術方案實現。