[發明專利]一種基于k-means的高維含噪聲數據的分類方法

在審

• 申請號: 201811468317.2
• 申請日: 2018-12-03
• 公開（公告）號: CN109376800A
• 公開（公告）日: 2019-02-22
• 發明（設計）人: 陳子忠;丁鑫;夏書銀;劉運勝
• 申請（專利權）人: 重慶郵電大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 北京同恒源知識產權代理有限公司 11275
• 代理人: 趙榮之

本發明涉及一種基于k?means的高維含噪聲數據的分類方法，涉及機器學習領域，利用本方法可以在對存在噪聲屬性的高維數據進行分類時取得較好的效果。包括以下步驟：首先每次利用已知類別的數據集的部分維度數據來構建多棵k?means樹，然后通過搜索每一棵樹來得到待分類數據的預測類別，最后把每一棵樹產生的分類結果進行投票，以得到最終的分類結果。本發明相對于一般的分類算法，大大提高了高維噪聲數據的分類效果。

技術領域

本發明屬于機器學習領域，涉及一種基于k-means的高維含噪聲數據的分類方法。

背景技術

當前在許多算法中都涉及到了近鄰匹配的問題，尤其是在機器學習和計算機視覺領域中。最常見的如k-nearest neighbor算法，kd-knn算法等，屬于有監督學習算法，即在已知類別的樣本基礎上來預測未知樣本所屬類別或是分類。然而一般的近鄰精確查找算法在數據量較大的時候，特別是高維數據中效果低下，故而人們在實驗中常用近似近鄰查找算法來代替精確查找，這一般能減少一到兩個數量級的時間開銷，并且精度損失很小，如the priority search k-means tree算法，就是一種針對處理高維數據的算法。

然而從現實生活中采集的數據里經常存在無用屬性，我們稱之為噪聲屬性或特征，比如在對動物圖像進行分類時，圖像中動物以外的背景像素點就會對分類產生干擾，影響分類結果。一般的近似查找算法在對這類數據進行處理時，會在很大程度上受到噪聲特征帶來的影響，以至于精度不佳。

發明內容

有鑒于此，本發明的目的在于提供一種解決一般近似近鄰算法在處理含噪聲的高維數據的分類問題時效果不佳，基于k-means樹的高維噪聲數據分類方法。

為達到上述目的，本發明提供如下技術方案：

一種基于k-means樹的高維噪聲數據分類方法，包括步驟：

S1：將已知類別的數據集作為訓練集，每次利用訓練集的部分維度數據來構建多棵k-means樹；

S2：通過搜索每一棵樹來得到待分類數據的預測類別；

S3：對每一棵樹產生的分類結果進行投票，以此來得到待分類數據的最終預測類別。

進一步，步驟S1中所述數據集包括含噪聲屬性的高維數據，每次選取訓練集的部分數據用于建樹時，是對屬性進行隨機選取，即從數據的所有特征屬性中隨機選取r個屬性，并且每次建樹前，都會隨機選取屬性，故每棵樹選取的特征屬性都是不同的。

進一步，在步驟S1中，構建k-means樹時，根結點設置為空，每次通過k-means算法，把數據聚為N類，然后用這N個類構建N個子節點，再在各個子節點中重復k-means聚類操作，直至點的個數不足N個，就用這些點來創建葉節點。

進一步，步驟S2中，所述搜索每一棵樹，包括以下步驟：

S21：假設用作判定類別的近鄰點數為k，設置最大查找點數range，即搜索范圍；

S22：用一個隊列R來存儲這range個數據信息，即只要找到range個數據點就停止樹搜索，然后從隊列R中選離預測點最近的k個點作為近鄰點；

S23：從根結點開始，比較Q與根結點的所有分支結點的距離，選擇最近的那一支繼續向下搜索，同時把另外幾個分支結點加入一個隊列queue，循環使用這種方法直到遍歷到葉子結點；

S24：把葉子結點信息加入R，并判斷R中數據個數是否超過range，若已經達到range，則停止搜索；若R中結點數不足range，則把隊列queue中的點根據到Q的距離進行排序，然后從距離最小的那個結點開始繼續遍歷直到葉子結點；

S25：重復以上過程，直到R中存有range個數據。