[發(fā)明專利]基于由P系統(tǒng)進化的可編輯樣本集的K最近鄰分類算法

在審

• 申請?zhí)枺?/td>: 201710642135.1
• 申請日: 2017-07-31
• 公開（公告）號: CN108009561A
• 公開（公告）日: 2018-05-08
• 發(fā)明（設計）人: 彭宏;胡娟;陳光春;張國洲;黃文成;王軍
• 申請（專利權）人: 西華大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 四川君士達律師事務所 51216
• 代理人: 芶忠義

本發(fā)明提供的基于由P系統(tǒng)進化的可編輯樣本集的K最近鄰分類算法包括：組織型P系統(tǒng)設計：系統(tǒng)包括q個細胞，每個細胞中包括m個對象，細胞中的對象為n維二進向量，用于指示原始樣本集中的哪些樣本被包含在可編輯樣本集中；P系統(tǒng)的q個細胞協(xié)同地搜索最優(yōu)指示向量Z：每個細胞中包含一個最好對象，每個細胞使用轉(zhuǎn)運規(guī)則將其最好對象轉(zhuǎn)運到環(huán)境中，更新環(huán)境中所對應的最好對象，并將自己的最好對象轉(zhuǎn)運給下一個細胞；可編輯樣本集生成：采用離散二進制PSO的速度?位移模型作為進化規(guī)則，依據(jù)停機條件停機后，環(huán)境中的最好對象即為最優(yōu)的可編輯樣本集；KNN分類器依據(jù)生成的可編輯樣本集構(gòu)造分類規(guī)則，對未知樣本進行分類，提高了分類器的分類性能。

技術領域

本發(fā)明屬于數(shù)據(jù)挖掘分類技術領域，具體地說，涉及一種基于由P系統(tǒng)進化的可編輯樣本集的K最近鄰分類算法。

背景技術

K最近鄰(k-Nearest Neighbor，KNN))分類算法是最受歡迎的監(jiān)督學習分類方法。它是一種在訓練階段不依賴于建立模型的非參數(shù)方法，其分類規(guī)則是基于給定的訓練實例與待測試實例之間的相似度函數(shù)。KNN算法已成為數(shù)據(jù)挖掘中最相關的算法，它是機器學習在各個領域中許多應用的一個組成部分。分類算法已廣泛被應用于各個方面：比如智能系統(tǒng)、計算機視覺、生物信息學、海洋探測、航空航天技術、工業(yè)生產(chǎn)、安全監(jiān)控、科學理論研究等許多重要領域。

但是KNN分類算法也有其不足的地方，1)高的計算復雜性：為了找出k最近鄰居集，需要計算未知樣本與所有訓練樣本之間的距離(或相似性)。2)對訓練樣本的依賴性：分類器僅由訓練樣本生成的，沒有使用其它數(shù)據(jù)，分類器嚴重地依賴于訓練樣本,哪怕訓練集有較小的改變，分類器需要重新計算。3)樣本之間沒有權重區(qū)別：所有訓練樣本被等同對待，這些樣本之間沒有差別，即使大的訓練。4)維數(shù)災問題：當樣本的特征維數(shù)太高時，分類器的性能會嚴重變差。

發(fā)明內(nèi)容

有鑒于此，本發(fā)明所要解決的技術問題是提供了一種基于由P系統(tǒng)進化的可編輯樣本集的K最近鄰分類算法，以解決當訓練樣本集太大時，KNN分類器需要花費過多的時間來計算未知樣本與所有訓練樣本的距離(或相似性)的問題。

為解決上述技術問題，本發(fā)明公開了一種基于由P系統(tǒng)進化的可編輯樣本集的K最近鄰分類算法。所述方法包括：

組織型P系統(tǒng)設計：系統(tǒng)包括q個細胞，每個細胞中包括m個對象，細胞中的對象為n維二進向量，用于指示原始樣本集中的哪些樣本被包含在可編輯樣本集中；

P系統(tǒng)的q個細胞協(xié)同地搜索最優(yōu)指示向量Z：每個細胞中包含一個最好對象，每個細胞使用轉(zhuǎn)運規(guī)則將其最好對象轉(zhuǎn)運到環(huán)境中，更新環(huán)境中所對應的最好對象，并將自己的最好對象轉(zhuǎn)運給下一個細胞；

可編輯樣本集生成：采用離散二進制PSO的速度-位移模型作為進化規(guī)則，依據(jù)停機條件停機后，環(huán)境中的最好對象即為最優(yōu)的可編輯樣本集；

KNN分類器依據(jù)生成的可編輯樣本集構(gòu)造分類規(guī)則，對未知樣本進行分類。

如上所述的算法，可選的，采用一個3維整數(shù)數(shù)組來表示P系統(tǒng)中的所有對象：Z(q,m,n)；

第i細胞中第j個對象記為可表示為：