[發明專利]一種基于參考點的快速精確近鄰分類算法

在審

• 申請號: 201611173890.1
• 申請日: 2016-12-16
• 公開（公告）號: CN106778869A
• 公開（公告）日: 2017-05-31
• 發明（設計）人: 夏書銀
• 申請（專利權）人: 重慶郵電大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 北京同恒源知識產權代理有限公司11275
• 代理人: 廖曦

技術領域

本發明屬于計算機技術領域，涉及一種基于參考點的快速精確近鄰分類算法。

背景技術

k近鄰分類算法(k Nearest Neighbors’Algorithm，kNN)是機器學習領域最為經典和常用的分類算法之一。當前，該算法已經廣泛應用于特征選擇，模式識別，聚類，噪音檢測分類等諸多領域。最基本的全搜索k近鄰算法(Full Searching algorithm，FSA)算法是通過計算待分類點到各已知類別點的歐式距離以確定k個最近鄰點，因此其時間復雜度較高(O(n²))，算法效率很低。另外，現有的k近鄰算法在不平衡數據集中的分類精度無法保證。現有的改進的近鄰算法主要在于提高k近鄰算法的效率，這些算法大體可以分為兩類：第一類，創建搜索樹以降低時間復雜度。比如，Kim和Park使用有序分拆方法來創建一個多分支搜索樹以提高搜索效率；Wang和Gan將投射聚類和主軸搜索樹算法相結合以減少運算時間。Chen等使用贏家更新搜索方法和下界樹來改善算法效率。以上改進算法的不足之處在于，隨著數據維數增加，其時間復雜度急劇變壞，且失去穩定性，所以算法的時間復雜度在(O(nlogn)～O(n²))。第二類，近似k最近鄰算法。該類算法通過搜索近似的k最近鄰樣本代替精確的最近鄰樣本，來避免所有樣本之間距離的直接計算，以提高搜索效率。譬如，Ra和Kim通過計算待分類點到各已知類別點的平均值的差異來除去不可能數據點；Lai使用三角不等式和投影值以降低計算復雜度；Xia在研究數據維度對最近鄰搜索算法影響后提出了LDMDBA算法；還有一些算法通過聚類來提高算法效率。這些算法雖然在效率上得到了提升，但是都在不同程度上犧牲了算法的精度，要低于精確最近鄰算法(即FSA或是其他基于樹索引結構的算法)。總結來說，兩類算法無法在保證算法精度的情況下，將算法在包括高維數據集上的各種數據上的時間復雜度降低到O(nlogn)。另外，這些改進算法都無法解決k近鄰算法在不平衡數據集上精度下降的問題。

發明內容

有鑒于此，本發明的目的在于提供一種新的分類算法，即一種基于參考點的快速精確近鄰分類算法(RPkN)。該近鄰搜索算法與現有k近鄰算法不同的是，其不再搜索最近鄰樣本用來分類，而是對分類問題更有效的樣本。該特性使RPkN能突破現有的最近鄰分類算法在處理不平衡數據低精度的局限性，使得RPkN具有更好的分類預測精度。另外，相比現有基于樹的精確最近鄰算法，RPkN算法不依賴任何樹索引結構，所以能夠更高效地處理高維數據，該算法的時間復雜度在任何數據集中可以保證在O(nlogn)。另外，RPkN仍然保留了現有最近鄰查詢算法的優勢：在線、多分類、不依賴訓練等。

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

一種基于參考點的快速精確近鄰分類算法，該算法用參考點的距離來替代樣本點之間的距離的進行直接計算，找到了比最近鄰樣本更加適合分類的樣本點，以提高算法的分類精度，算法給定數據集D∈R_d，k是近鄰算法中要搜索的近鄰數，A是D中的一個樣本點，ε為關系近鄰搜索算法時間復雜度的常量；表示候選參考點設置為單位向量及其反向量，定義變量ExistingNeighbors＝NULL，j＝1，具體步驟包括：

1)設置子序列的長度為2j*k*ε，并選擇第i個候選參考點為當前的參考點；

2)計算所有樣本點的參考點因子值，即RPF值，并對所有樣本點按照其RPF值進行排序并生成一個有序序列；

3)在由ExistingNeighbors和以A為中心且長度為2j*k*ε的子序列構成的集合中，找到與到A最近的k的樣本點；

4)計算所有樣本點的近鄰樣本及整個數據集的分類精度；

5)i＝i+1，將第i個候選參考點設置為下一個參考點；并計算加入新參考點后的分類精度；

6)如果所有候選參考點被加入且精度增加，用所有樣本的k近鄰樣本替代ExistingNeighbors，轉向步驟7)；如果還有候選參考點未被加入且精度增加，用所有樣本的k近鄰樣本替代ExistingNeighbors，轉向步驟5)；

7)如果子序列長度增加后算法的分類精度降低，算法終止；否則，轉向步驟8)；

8)通過j＝j+1將子序列的長度增加1并轉向步驟1)。