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

在審

• 申請?zhí)枺?/td>: 201611173890.1
• 申請日: 2016-12-16
• 公開（公告）號: CN106778869A
• 公開（公告）日: 2017-05-31
• 發(fā)明（設(shè)計）人: 夏書銀
• 申請（專利權(quán)）人: 重慶郵電大學(xué)
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 北京同恒源知識產(chǎn)權(quán)代理有限公司11275
• 代理人: 廖曦

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

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

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

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

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

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

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

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

8)通過j＝j(luò)+1將子序列的長度增加1并轉(zhuǎn)向步驟1)。

2.如權(quán)利要求1所述的一種基于參考點的近鄰搜索算法，其特征在于：所述ε的設(shè)置方法為：ε作為常量，本算法的時間復(fù)雜度為O(dn)～O(dnlog₂n)，ε值越大，算法步驟3)中的子序列將會包含越多的樣本點；如果ε很小，算法中參數(shù)j的迭代次數(shù)將會增加；但是如果ε很大，將可能會增加算法的時間復(fù)雜度；因此，ε應(yīng)該在保證算法的時間復(fù)雜度控制在O(nlogn)的情況下設(shè)置得越大越好；

在本算法中，ε被設(shè)置為關(guān)于n的對數(shù)函數(shù)log_mn時，算法中子序列的長度為2*n*k*log_mn

所以ε被設(shè)置為log_mn時，本算法的時間復(fù)雜度和快速排序是相同的，即為nlog₂n，為了將ε設(shè)置的盡量大，m取值為2。