有序規(guī)范實數(shù)對多相似度K最近鄰分類算法

崔昊陽，張 暉，周 雷，楊春明，李 波，趙旭劍

（1.西南科技大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，四川 綿陽 621010；2.西南科技大學(xué) 數(shù)理學(xué)院，四川 綿陽 621010）

0 引言

分類是一種有監(jiān)督的學(xué)習(xí)方法，目前使用最廣泛的分類算法主要有K最鄰近（K-Nearest Neighbor，KNN）、支持向量機、決策樹、邏輯回歸、貝葉斯分類算法等。其中，KNN 算法是一種易于理解和實現(xiàn)的分類算法，具有準(zhǔn)確度高、精度高、對異常樣本不敏感的優(yōu)點［1-2］。KNN 的原理是將給定的測試樣本與訓(xùn)練樣本進行比較，找到與該測試樣本最相似的k個訓(xùn)練樣本，再根據(jù)投票原則確定該測試樣本的類別，即該k個訓(xùn)練樣本中屬于哪個類別的樣本數(shù)量最多，則判定該測試樣本屬于此類別［1，3］。因此，有3 個因素對于KNN 算法的性能至關(guān)重要，分別為k值的選擇、距離或相似度度量方法的選擇以及訓(xùn)練數(shù)據(jù)集［1］。

Abu Alfeilat 等［4］研究了距離測度的選擇對KNN 分類性能的影響，可知KNN 分類算法的性能在很大程度上取決于使用的距離或相似度度量方法。目前有多種距離或者相似度度量方法可供選擇，如歐氏距離、曼哈頓距離、切比雪夫距離、閔氏距離、余弦相似度、皮爾森相關(guān)系數(shù)、Jaccard 系數(shù)等。然而目前并沒有能夠適用于所有類型數(shù)據(jù)集的最佳距離度量，不同的距離或相似度度量方法都有優(yōu)缺點［4］，方法的原理和側(cè)重點也不同，如余弦相似度是通過兩個樣本向量之間的夾角的余弦值來衡量，側(cè)重于方向上的相似而非兩個樣本間距離的遠(yuǎn)近。因此，在分類時很難對某個數(shù)據(jù)集選擇恰當(dāng)?shù)木嚯x或相似度度量方法。

針對這一問題，本文考慮通過結(jié)合不同的距離或相似度度量方法，實現(xiàn)不同度量方法的互補，從而避免單一度量方法的自身缺點，更加客觀、準(zhǔn)確地描述樣本間的距離或相似度，達到提升分類的準(zhǔn)確性目的。為了實現(xiàn)不同距離或相似度度量方法的結(jié)合，本文在機器學(xué)習(xí)算法中引入了有序規(guī)范實數(shù)對（Ordered Pair of Normalized real numbers，OPN）［5］這一新的數(shù)學(xué)理論。OPN 是對直覺模糊數(shù)（Intuitionistic Fuzzy Number，IFN）和畢達哥拉斯模糊數(shù)（Pythagorean Fuzzy Number，PFN）的拓展，通過對OPN、IFN 和PFN 對比發(fā)現(xiàn)，OPN 除了可計算IFN 和PFN 無法計算的三角函數(shù)、對數(shù)等，更重要的是在IFN 和PFN 的定義中，一個實數(shù)對中的兩個實數(shù)之和或平方和的大小都有著嚴(yán)格的限制，而OPN 中卻沒有這樣的限制，所以能通過OPN 更好地將兩種不同的距離或相似度度量方法結(jié)合起來。因此，本文選擇OPN 來結(jié)合不同的距離或相似度度量方法。

本文提出了一種將普通數(shù)據(jù)轉(zhuǎn)化為有序規(guī)范實數(shù)對（OPN）的方法。通過使用不同的相似度或距離度量方法，將普通數(shù)據(jù)轉(zhuǎn)化為包含了不同距離或相似度信息的OPN，能實現(xiàn)不同相似度或距離度量方法的結(jié)合。由于目前還沒有對OPN 進行分類的算法，本文在KNN 算法的基礎(chǔ)上進行了改進，提出了基于有序規(guī)范實數(shù)對的K最近鄰分類算法（K-Nearest Neighbor algorithm with Ordered Pairs of Normalized real numbers，OPNs-KNN），對OPN 進行分類，實現(xiàn)了不同距離或相似度度量方法的結(jié)合。在多個真實數(shù)據(jù)集上與多種KNN 的改進算法進行對比，驗證了OPNs-KNN 在分類準(zhǔn)確率等多個評價指標(biāo)上具有明顯優(yōu)勢，并且在某些數(shù)據(jù)集上，OPNs-KNN 能夠大幅地提升分類的性能。

1 相關(guān)工作

KNN 算法是一種廣泛使用的機器學(xué)習(xí)算法，對它的改進一直是研究熱點。其中，k值的選擇、距離或相似度度量方法的選擇以及訓(xùn)練數(shù)據(jù)集對KNN 算法的性能影響較大。

KNN 算法是一種投票模型，即在選擇的k個最近鄰中，哪個類別的樣本數(shù)量最多，就判斷測試樣本屬于該類別。但實際上不同的最近鄰對測試樣本的分類有不同的貢獻，因此可以采用樣本距離加權(quán)的方法改進KNN 算法。其中代表性的工作有距離加權(quán)K近鄰規(guī)則（distance-WeightedK-Nearest-Neighbor rule，WKNN）［6］以及基于加權(quán)表示的K近鄰規(guī)則（Weighted Representation-basedK-Nearest Neighbor rule，WRKNN）［7］。此外，還可以根據(jù)樣本中各個屬性的重要性的不同，對各屬性值進行加權(quán)，計算加權(quán)后的距離來進行分類，相關(guān)的研究有基于屬性加權(quán)的K最近鄰算法［8］等。

目前也有相關(guān)研究采用新的相似度計算方法來改進KNN 算法。在實際應(yīng)用中KNN 算法一般采用歐氏距離分類，然而歐氏距離并不一定適用于所有數(shù)據(jù)集。目前多種新的相似度或者距離度量方法被提出，相關(guān)學(xué)者將它們用于改進KNN 算法，并取得了不錯的分類效果，如基于熵降噪優(yōu)化相似性距離的KNN 算法［9］、基于屬性值相關(guān)距離的KNN 算法［10］、基于Hubness-aware 共享鄰居距離的高維數(shù)據(jù)分類算法［11］等。k值的設(shè)定對KNN 算法的分類性能影響較大，但k值的確定比較困難。因此，如何更好地確定k值，也是KNN算法的主要改進方向。相關(guān)的研究有動態(tài)k值的KNN 分類方法［12］、基于信息熵的自適應(yīng)k值KNN 算法［13］等。

此外，訓(xùn)練集中的樣本對KNN 算法也有著較大的影響，特別是小訓(xùn)練集且訓(xùn)練集樣本中存在異常值時。因此，克服異常值的影響對于提升分類的性能以及降低算法對于k值的敏感性都有著非常重要的意義。目前許多相關(guān)研究是通過使用K 近鄰的局部平均向量來克服異常值，例如基于局部均值的非參數(shù)分類器LMKNN（Local Mean-basedK-Nearest Neighbor）［14］、基于局部均值的偽最近鄰（Local Mean-based Pseudo Nearest Neighbor，LMPNN）分類算法［15］、基于多局部均值的最近鄰分類（Multi-Local Means based Nearest Neighbor classifier，MLMNN）算法［16］以及基于加權(quán)局部均值表示的K近鄰規(guī)則（Weighted Local Mean Representation-basedK-Nearest Neighbor rule，WLMRKNN）。

本文提出了一種基于多相似度的分類算法。通過OPN結(jié)合不同的相似度或距離度量方法，實現(xiàn)不同相似度或距離度量方法的互補，從而達到提升算法的分類性能的目的。

2 預(yù)備知識

本章介紹了有序規(guī)范實數(shù)對（OPN）的相關(guān)基礎(chǔ)知識。

定 義1 將α=(μα，να) 稱為一個OPN，其中，0 <μα且να<1。

令α=(0.9，0.8)，因 為0 <0.9 且0.8 <1，所 以α=(0.9，0.8)是一個OPN。但在直覺模糊數(shù)（IFN）的定義中，μα+να需要小于等于1，所以α不是一個IFN；同理，在畢達哥拉斯模糊數(shù)（PFN）的定義中需要小于等于1，所以α也不是一個PFN。

定 義2 使α=(μα，να)，β=(μβ，νβ)，α和β均為一個OPN，當(dāng)μα=μβ且να=νβ時，α=β。

定義3α=(μα，να)，β=(μβ，νβ)，α和β均為一個OPN，πα=|μα+να-1|，則α和β之間的距離可以定義為：

與其他模糊數(shù)（如IFN 和PFN）相比，OPN 中的兩個數(shù)的大小限制較少，將普通數(shù)據(jù)轉(zhuǎn)換為OPN 的方法可以更加方便和多樣。因此，本文選擇OPN 來結(jié)合兩種不同的距離或相似度度量。此外，OPN 在數(shù)學(xué)方面也有一些優(yōu)勢，例如，它可以計算IFN 和PFN 無法計算的三角函數(shù)、對數(shù)等。

3 有序規(guī)范實數(shù)對分類算法

3.1 普通數(shù)據(jù)轉(zhuǎn)化為有序規(guī)范實數(shù)對

如定義1 所述，一個OPN 中的兩個實數(shù)間的大小限制較寬松，因此能使用不同方法來生成一個OPN 中的兩個實數(shù)。

然后通過定義5 所示的方式，將普通數(shù)據(jù)轉(zhuǎn)換為OPN。

該轉(zhuǎn)化方法是基于Wiswedel 等［17］提出的平行宇宙中學(xué)習(xí)的范式。相似度或距離度量有很多種，如曼哈頓距離、歐氏距離、切比雪夫距離、閔氏距離、余弦相似度等，可根據(jù)數(shù)據(jù)集的特點選擇兩種相似度度量方法。該方法涉及的參數(shù)為q，不同的q代表計算原始數(shù)據(jù)之間相似度或距離時所選擇的點不同。

可將X2轉(zhuǎn)化為Z2={ (4.123，0.600)，(3.606，0.800) }。

可以看出，例1 得到的兩個實數(shù)對均不能滿足定義1 中OPN 的定義，因此這些實數(shù)對還不能被稱為OPN。所以本文還提供了一種規(guī)范化方法如定義6 所示，將所有實數(shù)對全部規(guī)范化到（0，1）范圍內(nèi)，從而滿足OPN 的定義。

定義6 OPN 數(shù)據(jù)集Z中具有n個數(shù)據(jù)，Zj為OPN 數(shù)據(jù)集Z中的第j個數(shù)據(jù)(0

圖1 以Iris 數(shù)據(jù)集為例展示了本節(jié)的轉(zhuǎn)換方法。Iris 數(shù)據(jù)集中有3 類數(shù)據(jù)（class 1～3），每個數(shù)據(jù)有4 個屬性。使用歐氏距離和余弦相似度作為相似度度量，q=10，將每個數(shù)據(jù)轉(zhuǎn)換為4 個OPN。圖1 中的4 個部分分別對應(yīng)轉(zhuǎn)換得到的4個OPN。每個OPN 中的兩個實數(shù)分別用作橫坐標(biāo)和縱坐標(biāo)的值，以展示它們在空間中的位置。

圖1 將Iris數(shù)據(jù)集中的數(shù)據(jù)轉(zhuǎn)化為OPNFig.1 All data in Iris dataset converting to OPN

從圖1 可以看出，在每個子圖中，3 個類別的數(shù)據(jù)都有較好的可區(qū)分性，并顯示出不同的結(jié)構(gòu)特征。后續(xù)的分類算法將綜合各個OPN 的差異，得出最終的分類結(jié)果。

3.2 有序規(guī)范實數(shù)對的K最近鄰分類算法

KNN 的核心是樣本間相似度或者距離的度量。本文將兩個OPN 組成的數(shù)據(jù)間距離定義如下。

定義7Xj和Vi是轉(zhuǎn)化為OPN 后的兩個數(shù)，且它們均有m個特征，其中：

該距離定義的核心是考慮了在兩個相互對應(yīng)的OPN 之中，它們所包含的相似度信息之間的差異，最后綜合各個OPN 上的差異，得出最終的距離。如果相似度信息差異越大，則距離越大；如果相似度信息差異越小，則距離越小。

OPNs-KNN 的具體步驟如算法1 所示。

算法1 OPNs-KNN。

輸入 訓(xùn)練集T，測試樣本Xj，指定的兩種相似度或距離度量方法，q和k值；

輸出 測試樣本Xj所屬類別。

步驟1 利用3.1 節(jié)中的方法及指定的相似度或距離度量方法，計算測試樣本Xj和訓(xùn)練集中各點與各個坐標(biāo)軸上與原點距離為q的點的兩種距離或相似度，將Xj和訓(xùn)練集中各點全部轉(zhuǎn)化為OPN。

步驟2 利用式（8）計算出測試樣本與訓(xùn)練集中各點的距離。

步驟3 選取與測試樣本最近的k個訓(xùn)練數(shù)據(jù)，其中，屬于哪個類別的樣本最多，則判定該測試樣本也屬于該類別。

對OPNs-KNN 的復(fù)雜度進行分析。由于OPNs-KNN 基于KNN 算法，兩者同屬于懶惰學(xué)習(xí)（lazy-learning）算法，新的測試樣本需利用式（8）來計算與訓(xùn)練集中各個樣本之間的距離，因此算法的時間復(fù)雜度與訓(xùn)練樣本的數(shù)量成正比。設(shè)訓(xùn)練集中樣本的數(shù)量為n，則OPNs-KNN 的時間復(fù)雜度可以表示為O(n)。而在空間復(fù)雜度上，需存儲測試樣本與各個訓(xùn)練樣本之間的距離，因此空間復(fù)雜度可以表示為O(n)。

為了更直觀地展示OPNs-KNN 的分類效果，仍以Iris 數(shù)據(jù)集為例進行可視化展示。將Iris 數(shù)據(jù)集中50%數(shù)據(jù)作為訓(xùn)練集，剩余50%數(shù)據(jù)集用作測試集。如圖2 所示，不同形狀代表數(shù)據(jù)的類別，圖2（a）、（c）、（e）、（g）為原始數(shù)據(jù)轉(zhuǎn)化為OPN 后的真實情況（采用數(shù)據(jù)真實標(biāo)簽繪圖）；圖2（b）、（d）、（f）、（h）為分類結(jié)果（采用OPNs-KNN 的分類結(jié)果繪圖）。

圖2 OPNs-KNN分類結(jié)果與數(shù)據(jù)集真實情況的對比Fig.2 Comparison between classification results of OPNs-KNN and real situation of dataset

由圖2 可以看出，OPNs-KNN 給出的分類結(jié)果與測試數(shù)據(jù)的真實標(biāo)簽基本一致，表明OPNs-KNN 在Iris 數(shù)據(jù)集上有效。有關(guān)OPNs-KNN 的性能將在實驗部分進一步闡述。

4 實驗與結(jié)果分析

本文選擇準(zhǔn)確率、召回率和F1 值對分類效果進行評價［18］。使用scikit-learn 庫中的函數(shù)來計算上述指標(biāo)，且召回率、F1 值計算函數(shù)中的average 設(shè)定為macro。實驗采用了UCI 中的多個公開數(shù)據(jù)集（https：//archive.ics.uci.edu），具體信息如表1 所示。

表1 UCI數(shù)據(jù)集Tab.1 UCI datasets

為了更準(zhǔn)確客觀地描述分類算法的性能，實驗采用了10 次10 折交叉驗證的方法。10 折交叉驗證是指將數(shù)據(jù)集劃分為近似相等且互斥的10 個子集，然后每次取出1 個子集作為測試集，剩下9 個子集作為訓(xùn)練集，然后執(zhí)行分類算法，直到每個子集都輪流作為了一次測試集［19］。10 次10 折交叉驗證則是將10 折交叉驗證的過程執(zhí)行10 次。最終取10 次10折交叉驗證中各評價指標(biāo)的平均值作為最終報告的結(jié)果。

4.1 OPNs-KNN的參數(shù)選擇

4.1.1q值的選擇

為了研究q的取值對OPNs-KNN 在不同數(shù)據(jù)集上準(zhǔn)確率的影響，本文在各個數(shù)據(jù)集上進行了實驗：將OPNs-KNN 中使用的兩種相似度或距離度量固定為歐氏距離和余弦相似度，k的取值固定為該數(shù)據(jù)集上的最佳k值，只改變q值的大小，q的取值范圍為［0.1，20］，每次按0.1 遞增，取10 次10 折交叉驗證后的結(jié)果進行展示。實驗結(jié)果如圖3 所示。

圖3 q值對于OPNs-KNN準(zhǔn)確率的影響Fig.3 Influence of q value on accuracy of OPNs-KNN

從圖3 可知，q值對算法的準(zhǔn)確率確有影響，但影響的幅度都不大，并且在部分?jǐn)?shù)據(jù)集上，q值的變化對于算法準(zhǔn)確率并沒有影響。因此，q值的選擇并不是影響算法準(zhǔn)確率的最主要因素。但綜合圖3 中算法在各數(shù)據(jù)集上準(zhǔn)確率的變化，在本文所采用的數(shù)據(jù)集上，推薦將q默認(rèn)設(shè)置為10。

4.1.2 相似度或距離度量的選擇

本文嘗試了3 種常見的距離度量來與余弦相似度組合進行實驗，包括曼哈頓距離、歐氏距離和閔氏距離（其中p值為閔氏距離公式中的參數(shù)，不同p值下的閔氏距離度量不同），本文簡寫為MD、ED 和MKD，實驗結(jié)果如圖4 所示。這3 種距離在與余弦相似度組合后，均有著不錯的準(zhǔn)確率。因為目前各種距離或相似度的度量方法較多，無法嘗試所有距離和相似度度量之間的組合，但從圖4 而言，大多數(shù)數(shù)據(jù)集上歐氏距離與余弦相似度搭配均有著不錯的準(zhǔn)確率，因此本文采用歐氏距離與余弦相似度作為OPNs-KNN 的兩種默認(rèn)相似度或距離度量方法。

圖4 不同距離與余弦相似度組合下的OPNs-KNN在各數(shù)據(jù)集上的準(zhǔn)確率Fig.4 Accuracy of OPNs-KNN on each dataset under combinations of different distance and cosine similarity

4.1.3k值的選擇

圖5 為OPNs-KNN（采用歐氏距離及余弦相似度，q=10）在部分?jǐn)?shù)據(jù)集中不同k值下的準(zhǔn)確率，并對比了分別采用歐氏距離和余弦相似度的KNN 算法。從圖5 可知，OPNs-KNN 與KNN 算法一樣容易受到k值的影響，因此k值的選擇仍然是OPNs-KNN 的主要問題。同時，OPNs-KNN 相較于采用單一相似度度量方法的KNN 算法，在一些數(shù)據(jù)集上（如wine 數(shù)據(jù)集）的準(zhǔn)確率提升明顯。

圖5 k值對OPNs-KNN的準(zhǔn)確率影響Fig.5 Influence of k value on accuracy of OPNs-KNN

4.2 OPNs-KNN的性能表現(xiàn)

綜合4.1 節(jié)，采用歐氏距離及余弦相似度，q取10 為默認(rèn)參數(shù)，表2 為默認(rèn)參數(shù)下OPNs-KNN 在各數(shù)據(jù)集上的指標(biāo)。

表2 默認(rèn)參數(shù)下的OPNs-KNN在各數(shù)據(jù)集上性能表現(xiàn)及對應(yīng)k值Tab.2 Performance of OPNs-KNN on each dataset under default parameters and corresponding k value

然而默認(rèn)參數(shù)并不是一定為最佳參數(shù)，實驗中嘗試了曼哈頓距離、歐氏距離、閔氏距離（p=3 至10）以及余弦相似度之間的兩兩組合，q在［0.1，20］范圍內(nèi)按0.1 遞增，k在［1，20］范圍內(nèi)按1 遞增來尋找最佳參數(shù)，各數(shù)據(jù)集對應(yīng)的最佳參數(shù)如表3 所示。在表3 所設(shè)定的最佳參數(shù)下，OPNs-KNN在各數(shù)據(jù)集上的性能表現(xiàn)如表4 所示。

表3 OPNs-KNN具有最佳性能表現(xiàn)的參數(shù)設(shè)定Tab.3 Parameter setting for OPNs-KNN with best performance

4.3 OPNs-KNN與其他算法對比

將OPNs-KNN 與WKNN、LMPNN、LMKNN、MLMNN、WRKNN 以及WLMRKNN 這6 種KNN 的改進算法進行對比，這些算法的性能由相關(guān)文獻［7，20］所報道。

表5 中展示了OPNs-KNN 與其他算法的準(zhǔn)確率對比，可以看出，OPNs-KNN 在各數(shù)據(jù)集上的準(zhǔn)確率均優(yōu)于其他算法，分類準(zhǔn)確率提高了0.29～15.28 個百分點。

表5 不同算法在各數(shù)據(jù)集上的分類準(zhǔn)確率對比 單位：%Tab.5 Comparison of classification accuracy of different algorithms on each dataset unit：%

同時，將表2 和表5 對比可知，即使在默認(rèn)參數(shù)下，OPNs-KNN 也同樣具有較高的分類準(zhǔn)確率。在各個數(shù)據(jù)集上，默認(rèn)參數(shù)下的OPNs-KNN 的準(zhǔn)確率仍然超過了最佳參數(shù)下的多個算法的準(zhǔn)確率。

5 結(jié)語

本文將有序規(guī)范實數(shù)對應(yīng)用于機器學(xué)習(xí)算法中，提出了一種利用不同的相似度或距離度量將普通數(shù)據(jù)轉(zhuǎn)化為包含了不同相似度或距離度量信息的有序規(guī)范實數(shù)對的方法，并提出了有序規(guī)范實數(shù)對最近鄰分類算法，從而在最近鄰分類算法中實現(xiàn)了不同相似度或者距離度量方法的結(jié)合和互補。實驗結(jié)果表明，相較于對比算法，在實驗數(shù)據(jù)集上OPNs-KNN 分類準(zhǔn)確率提高了0.29～15.28 個百分點。

目前OPNs-KNN 的準(zhǔn)確率仍然主要受k值的影響，這與KNN 算法一致，因此如何降低k值對算法準(zhǔn)確率的影響，將是該方法后期進一步改進的方向。同時，除KNN 算法外，在分類、聚類、降維等機器學(xué)習(xí)任務(wù)中，仍有多種算法的性能易受到所選擇的相似度或距離度量方法影響（如K-Means、FuzzyC-Means、AGNES 等）；因此本文提出的利用OPN 來結(jié)合不同相似度或距離度量的方法還可以進一步推廣，在更多算法中通過不同相似度或距離度量的互補，達到提升算法性能的目的。