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

在審

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

1.一種基于k-means樹的高維噪聲數據分類方法，其特征在于：包括以下步驟：

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

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

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

2.根據權利要求1所述的基于k-means樹的高維噪聲數據分類方法，其特征在于：步驟S1中所述數據集包括含噪聲屬性的高維數據，每次選取訓練集的部分數據用于建樹時，是對屬性進行隨機選取，即從數據的所有特征屬性中隨機選取r個屬性，并且每次建樹前，都會隨機選取屬性，故每棵樹選取的特征屬性都是不同的。

3.根據權利要求1所述的基于k-means樹的高維噪聲數據分類方法，其特征在于：在步驟S1中，構建k-means樹時，根結點設置為空，每次通過k-means算法，把數據聚為N類，然后用這N個類構建N個子節點，再在各個子節點中重復k-means聚類操作，直至點的個數不足N個，就用這些點來創建葉節點。

4.根據權利要求1所述的基于k-means樹的高維噪聲數據分類方法，其特征在于：步驟S2中，所述搜索每一棵樹，包括以下步驟：

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

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

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

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

S25：重復S24，直到R中存有range個數據。

5.根據權利要求1所述的基于k-means樹的高維噪聲數據分類方法，其特征在于：步驟S3中，對每一棵樹產生的分類結果進行投票的方法包括：收集每一棵樹產生的預測結果，選取重復出現次數最多的判定來作為待預測數據的最后分類結果。

6.根據權利要求2所述的基于k-means樹的高維噪聲數據分類方法，其特征在于：隨機選取的特征屬性個數r為總特征屬性個數的平方根。

7.根據權利要求3所述的基于k-means樹的高維噪聲數據分類方法，其特征在于：樹中的每個非葉節點只存儲聚類中心和子節點信息，訓練集的數據只存放在葉子節點。

8.根據權利要求4所述的基于k-means樹的高維噪聲數據分類方法，其特征在于：在對每棵樹進行搜索時，停止搜索的條件是R中的數據個數超過了預先設置的搜索范圍range，range為k的整數倍。

9.根據權利要求4所述的基于k-means樹的高維噪聲數據分類方法，其特征在于：在樹中搜索停止后，從R中選離預測點最近的k個點作為近鄰點，然后根據這k個點的類別標簽來得到這棵樹的預測結果。

10.根據權利要求9所述的基于k-means樹的高維噪聲數據分類方法，其特征在于：k個點判定類別的方法采用投票的機制。