齊 晴，沈正飛，曹 健，應(yīng) 俊，趙 龍

1.上海交通大學(xué)計(jì)算機(jī)科學(xué)與工程系，上海2002402.上海海勃物流軟件有限公司，上海200080

近年來(lái)，隨著數(shù)據(jù)的積累，如何利用機(jī)器學(xué)習(xí)算法從大量的數(shù)據(jù)中學(xué)習(xí)知識(shí)已經(jīng)成為一個(gè)人們普遍關(guān)心的問(wèn)題.對(duì)于一個(gè)機(jī)器學(xué)習(xí)算法，除了需要有較好的預(yù)測(cè)性能和良好的泛化能力外，還應(yīng)該具備如下幾個(gè)特點(diǎn)：1）快速訓(xùn)練；2）快速預(yù)測(cè)；3）可以應(yīng)對(duì)大規(guī)模在線(xiàn)數(shù)據(jù)以及流數(shù)據(jù).想要設(shè)計(jì)一個(gè)算法同時(shí)滿(mǎn)足上述條件是比較困難的，而在諸如計(jì)算機(jī)視覺(jué)、推薦系統(tǒng)、廣告預(yù)測(cè)等領(lǐng)域，巨大的數(shù)據(jù)量對(duì)機(jī)器學(xué)習(xí)算法的計(jì)算效率優(yōu)化提出了更大的挑戰(zhàn).

K-近鄰算法（K-nearest neighbor,KNN）是一種非監(jiān)督式算法，它針對(duì)待分類(lèi)樣本尋找最相似的k個(gè)樣本，利用它們的標(biāo)簽判定待分類(lèi)樣本的類(lèi)別.作為一種經(jīng)典的機(jī)器學(xué)習(xí)算法，KNN 因效果較好而得到了普遍的應(yīng)用.研究者們也不斷深化KNN 算法的模型，例如文獻(xiàn)[1]提出了利用D-S 證據(jù)理論對(duì)近鄰的標(biāo)簽進(jìn)行聚合形成最后的分類(lèi)結(jié)果的方法.

在KNN 算法中，需要為待分類(lèi)樣本與每個(gè)歷史樣本計(jì)算距離并進(jìn)行比較，從而能夠找到最相近的k個(gè)歷史樣本.隨著歷史案例庫(kù)的不斷擴(kuò)大，KNN 算法的運(yùn)行效率將急劇下降.特別是在面向多用戶(hù)進(jìn)行實(shí)時(shí)決策的系統(tǒng)中，具有較大的日活躍用戶(hù)數(shù)量（daily active user，DAU）與每秒查詢(xún)率（queries-per-second，QpS），對(duì)系統(tǒng)的吞吐量和算法的效率都有較高的要求，此時(shí)KNN 的效率可能會(huì)成為系統(tǒng)的制約因素.文獻(xiàn)[2]提出的邊界樹(shù)與邊界森林算法在解決KNN 方法的計(jì)算和存儲(chǔ)需求方面具有顯著的特性.邊界樹(shù)是一個(gè)所有節(jié)點(diǎn)都依附于訓(xùn)練集合的樹(shù)形結(jié)構(gòu).在查詢(xún)時(shí)，當(dāng)前遍歷到的節(jié)點(diǎn)視為根節(jié)點(diǎn)，并將待查詢(xún)（預(yù)測(cè)）樣本與根節(jié)點(diǎn)及其所有孩子節(jié)點(diǎn)進(jìn)行比較.如果根節(jié)點(diǎn)是距離最近的樣本點(diǎn)，則該節(jié)點(diǎn)是分類(lèi)或回歸問(wèn)題的目標(biāo)節(jié)點(diǎn)；否則將目標(biāo)遷至與待預(yù)測(cè)樣本距離最近的孩子節(jié)點(diǎn)，并重復(fù)此過(guò)程.因而，邊界樹(shù)被視作一種可以實(shí)現(xiàn)高效KNN 查詢(xún)的分層數(shù)據(jù)結(jié)構(gòu)，允許快速KNN 分類(lèi)、回歸、檢索，且它們的內(nèi)存需求隨著呈現(xiàn)數(shù)據(jù)量的增加而非常緩慢地增長(zhǎng).

傳統(tǒng)的KNN 算法中假定歷史樣本上的標(biāo)簽是唯一且正確的，而在某些場(chǎng)景下歷史樣本的標(biāo)簽并不一定就是唯一正確的，也就是說(shuō)，標(biāo)簽具有一定的不確定性.這種不確定性可以通過(guò)其他信息進(jìn)行度量.例如，針對(duì)醫(yī)療方案推薦問(wèn)題，如果歷史樣本的標(biāo)簽是多個(gè)專(zhuān)家投票決定的，那么專(zhuān)家的投票分歧度就可以衡量標(biāo)簽的不確定程度.如何考慮歷史樣本標(biāo)簽的不確定性并利用KNN 進(jìn)行決策是一個(gè)值得探討的問(wèn)題.

類(lèi)似于普通KNN 算法在找到k個(gè)近鄰后過(guò)于簡(jiǎn)易的決策過(guò)程，普通的邊界樹(shù)算法僅僅使用遞歸遍歷的終止節(jié)點(diǎn)作為分類(lèi)或者回歸問(wèn)題的目標(biāo)節(jié)點(diǎn)而沒(méi)有利用到邊界樹(shù)的其他節(jié)點(diǎn).邊界樹(shù)算法在通過(guò)多次遞歸快速找到相似樣本后，如何更加合理地進(jìn)行決策是本文研究的一個(gè)重點(diǎn).另外，關(guān)于如何計(jì)算距離是KNN 算法中的核心問(wèn)題，文獻(xiàn)[2]在考慮歐幾里得距離時(shí)忽略了樣本標(biāo)簽的不確定性對(duì)距離可能產(chǎn)生的影響.本文將利用樣本的意見(jiàn)集合OpS 進(jìn)一步優(yōu)化距離的計(jì)算及邊界樹(shù)中的節(jié)點(diǎn)轉(zhuǎn)移概率.本文改進(jìn)了傳統(tǒng)的邊界樹(shù)算法，提出一種面向標(biāo)簽不確定的歷史樣本庫(kù)的K-近鄰高效決策方法.文中將對(duì)KNN 算法和邊界樹(shù)算法進(jìn)行簡(jiǎn)單介紹，在此基礎(chǔ)上詳細(xì)介紹本文提出的方法并對(duì)實(shí)驗(yàn)過(guò)程和結(jié)果進(jìn)行詳細(xì)討論.

1 K-近鄰算法

KNN 算法是一種經(jīng)典的機(jī)器學(xué)習(xí)算法.利用KNN 算法進(jìn)行決策的基本過(guò)程是找出最相似的k個(gè)近鄰，再根據(jù)這k個(gè)近鄰進(jìn)行決策.KNN 算法相比于其他方法具有以下優(yōu)點(diǎn)：

1）KNN 算法具有明確的可解釋性.通過(guò)算法的輸出預(yù)測(cè)結(jié)果，使用者可以直觀(guān)地知道算法是依據(jù)哪些鄰近樣本做出該決策的，這在醫(yī)療等領(lǐng)域顯得特別重要.使用KNN 算法為病人推薦治療方案時(shí)，醫(yī)生可以追本溯源找到歷史類(lèi)似病例進(jìn)而輔助醫(yī)生判斷.

2）KNN 算法是一種惰性學(xué)習(xí)算法，無(wú)需從一開(kāi)始進(jìn)行訓(xùn)練，而僅在待預(yù)測(cè)樣本到來(lái)時(shí)進(jìn)行預(yù)測(cè)，減少了訓(xùn)練模型的開(kāi)銷(xiāo).

3）KNN 算法是非參數(shù)的學(xué)習(xí)算法.這一特點(diǎn)使其對(duì)訓(xùn)練集的分布是否均勻并不敏感.然而，KNN 算法也存在以下不足：

1）KNN 算法最大的問(wèn)題是計(jì)算開(kāi)銷(xiāo)比較大.對(duì)于每一個(gè)待預(yù)測(cè)的樣本，KNN 算法都要將其與所有訓(xùn)練集中的樣本進(jìn)行距離計(jì)算以確定相似度.隨著歷史樣本的不斷積累，計(jì)算規(guī)模在不斷增加，時(shí)間與空間成本會(huì)顯著提升.有許多研究提出使用近似算法來(lái)優(yōu)化KNN 算法以達(dá)到計(jì)算準(zhǔn)確度與時(shí)間空間復(fù)雜度之間的折中，如文獻(xiàn)[2]使用邊界樹(shù)算法來(lái)優(yōu)化KNN 算法.

2）k值的選取也對(duì)KNN 算法的影響較大，因此成為有關(guān)KNN 算法研究的熱點(diǎn)[3].如何確定最優(yōu)的k值將影響預(yù)測(cè)結(jié)果，同時(shí)也影響一部分時(shí)間開(kāi)銷(xiāo).

近年來(lái)，許多研究者專(zhuān)注于改善KNN 的性能.文獻(xiàn)[4]提出了一種生成式度量學(xué)習(xí)方法，以增強(qiáng)KNN 算法的性能.為了在給定的數(shù)據(jù)集上選擇k的最佳值，文獻(xiàn)[5]中提出了一種通過(guò)簡(jiǎn)單而快速的過(guò)程來(lái)獲取本地k值的算法.

當(dāng)利用KNN 算法找出待預(yù)測(cè)樣本在歷史樣本中最相似的k個(gè)樣本后，如何進(jìn)行決策成為有關(guān)KNN 算法研究的熱點(diǎn)[6].其中一個(gè)最簡(jiǎn)單的方法就是采用投票原則：對(duì)于分類(lèi)問(wèn)題當(dāng)最鄰近的k個(gè)鄰居確定后，用其中數(shù)量最多的類(lèi)別作為決策結(jié)果來(lái)預(yù)測(cè)待分類(lèi)的樣本.基于投票原則的決策方法為

當(dāng)將KNN 算法應(yīng)用于回歸問(wèn)題時(shí)，對(duì)未知樣本的輸出不再是一個(gè)離散類(lèi)型的分類(lèi)，而應(yīng)該是一個(gè)連續(xù)值.此時(shí)，式(1)可改寫(xiě)為

在KNN 算法中，上述基于簡(jiǎn)單投票準(zhǔn)則的決策方法是一種易于理解與實(shí)現(xiàn)的方法，其核心的思想概括為“少數(shù)服從多數(shù)”.這種想法的假設(shè)是與待預(yù)測(cè)樣本最相似的k個(gè)樣本具有相同的權(quán)重，顯然，這種思想在一定程度上缺乏合理性.從直觀(guān)上看，距離較近的樣本，因其相似度更高而在最后的決策中應(yīng)該發(fā)揮更重要的作用；相反，距離較遠(yuǎn)的樣本，其相似度較低，因此在最后的決策中應(yīng)該發(fā)揮的作用較輕.關(guān)于決策過(guò)程優(yōu)化的探討，文獻(xiàn)[7-9]用模糊數(shù)學(xué)的理論來(lái)優(yōu)化決策過(guò)程，而文獻(xiàn)[10]采用Dempster Shafer 證據(jù)理論進(jìn)行決策.本文則針對(duì)樣本標(biāo)簽的不確定度來(lái)優(yōu)化決策過(guò)程.

2 基于邊界樹(shù)的KNN 算法

邊界樹(shù)由代表訓(xùn)練樣本的節(jié)點(diǎn)組成，在訓(xùn)練期間創(chuàng)建節(jié)點(diǎn)之間的邊.給定一個(gè)查詢(xún)點(diǎn)x和一棵邊界樹(shù)T，該算法從根節(jié)點(diǎn)開(kāi)始遍歷該樹(shù)并遞歸比較當(dāng)前節(jié)點(diǎn)及其子節(jié)點(diǎn)到查詢(xún)點(diǎn)的距離，然后再移動(dòng)到最接近的子節(jié)點(diǎn)上，除非當(dāng)前節(jié)點(diǎn)是最接近的且子節(jié)點(diǎn)少于k，它將返回當(dāng)前節(jié)點(diǎn).有限的k可以顯著地提高速度且性能成本低，因此邊界樹(shù)可實(shí)現(xiàn)高效KNN 查詢(xún).

邊界樹(shù)可用來(lái)進(jìn)行快速KNN 分類(lèi)、回歸、檢索，且它們的內(nèi)存需求隨著呈現(xiàn)數(shù)據(jù)量的增加而非常緩慢地增長(zhǎng)，本文介紹了將邊界樹(shù)算法應(yīng)用于分類(lèi)問(wèn)題的情況.

圖1 二分類(lèi)問(wèn)題邊界樹(shù)訓(xùn)練過(guò)程Figure 1 Training process in 2D classification problem

圖1展示了一個(gè)二分類(lèi)問(wèn)題的邊界樹(shù)訓(xùn)練過(guò)程.圖中著色區(qū)域的樣本標(biāo)簽是0，白色區(qū)域的樣本的標(biāo)簽是1.邊界樹(shù)以在線(xiàn)的方式隨著節(jié)點(diǎn)的輸入而不斷擴(kuò)大.開(kāi)始時(shí)選擇任意一個(gè)節(jié)點(diǎn)并將其設(shè)置為邊界樹(shù)的根節(jié)點(diǎn)（Root）.對(duì)于一個(gè)待預(yù)測(cè)分類(lèi)的節(jié)點(diǎn)（圖中藍(lán)色節(jié)點(diǎn)），以一個(gè)貪心的策略遍歷整個(gè)邊界樹(shù)：從根節(jié)點(diǎn)開(kāi)始找到當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)和節(jié)點(diǎn)本身之外的最近節(jié)點(diǎn)（根據(jù)距離函數(shù)），然后遞歸繼續(xù)遍歷直到最終到達(dá)葉子節(jié)點(diǎn)或停留在當(dāng)前節(jié)點(diǎn)（這意味著它比任何孩子節(jié)點(diǎn)更靠近查詢(xún)點(diǎn)）為止.本文使用與最終節(jié)點(diǎn)關(guān)聯(lián)的標(biāo)簽來(lái)生成樹(shù)的預(yù)測(cè)：在這種情況下，圖1中的Query 點(diǎn)將被預(yù)測(cè)將為紅色.如果預(yù)測(cè)錯(cuò)誤（即與最終節(jié)點(diǎn)關(guān)聯(lián)的標(biāo)簽與查詢(xún)點(diǎn)的標(biāo)簽不同），則向最終節(jié)點(diǎn)添加一個(gè)包含該查詢(xún)點(diǎn)作為子節(jié)點(diǎn)的新節(jié)點(diǎn).如果預(yù)測(cè)正確則丟棄查詢(xún)節(jié)點(diǎn).

按照上述算法生成的樹(shù)具有一個(gè)顯著的特點(diǎn)：樹(shù)上的每條邊都跨越了分類(lèi)的邊界，且樹(shù)中存儲(chǔ)的節(jié)點(diǎn)將傾向于靠近這些邊界，因此稱(chēng)其為邊界樹(shù).

3 面向不確定標(biāo)簽樣本的邊界樹(shù)KNN 算法

本節(jié)將介紹所提出的面向不確定標(biāo)簽樣本的邊界樹(shù)（uncertain label boundary tree,ULBT）算法.問(wèn)題的輸入定義如下：

在一個(gè)分類(lèi)問(wèn)題中，歷史樣本集可以被定義為N個(gè)p維訓(xùn)練樣本的集合，用X=表示，該數(shù)據(jù)集中的每一個(gè)樣本都屬于且僅屬于一個(gè)由M個(gè)類(lèi)別組成的類(lèi)別集合C={C1,···,CM}.歷史樣本中的每一個(gè)樣本都被以某種程度的不確定性標(biāo)注為集合C中的某一個(gè)分類(lèi).經(jīng)過(guò)標(biāo)注的數(shù)據(jù)集可以表示為一個(gè)二元關(guān)系(X,L)，其中L是標(biāo)簽集合，可以用來(lái)對(duì)新的待預(yù)測(cè)樣本分類(lèi).

邊界樹(shù)算法可以理解為一種基于貪心策略的KNN 算法，其最大的優(yōu)勢(shì)在于可以快速地找到待預(yù)測(cè)樣本的鄰近樣本集合.ULBT 對(duì)原始的邊界樹(shù)算法進(jìn)行了兩方面改進(jìn)：1）優(yōu)化了節(jié)點(diǎn)的轉(zhuǎn)移策略，將樣本標(biāo)簽的不確定度納入轉(zhuǎn)移評(píng)分的計(jì)算中；2）在轉(zhuǎn)移路徑確定后，用D-S 證據(jù)理論并結(jié)合標(biāo)簽不確性進(jìn)行決策.

一個(gè)完整的ULBT 算法分為4 個(gè)階段：初始化階段、遍歷階段、決策階段、結(jié)束階段.圖2的展示了ULBT 的一次執(zhí)行過(guò)程.

圖2 ULBT 算法流程Figure 2 Process of ULBT

設(shè)輸入的待預(yù)測(cè)節(jié)點(diǎn)為Query 節(jié)點(diǎn)（圖2中紅色圓圈），xs表示該樣本的特征向量.

步驟1初始化.首先在數(shù)據(jù)集中任意選取一點(diǎn)為邊界樹(shù)的根節(jié)點(diǎn)，如圖2中的A節(jié)點(diǎn)為根節(jié)點(diǎn).根節(jié)點(diǎn)是遞歸遍歷過(guò)程的起始節(jié)點(diǎn).

步驟2遍歷.每次都要決定是否發(fā)生轉(zhuǎn)移.轉(zhuǎn)移的目的是為了發(fā)現(xiàn)當(dāng)前遍歷到的節(jié)點(diǎn)與其孩子結(jié)點(diǎn)中與Query 節(jié)點(diǎn)距離最近的節(jié)點(diǎn)，本文同時(shí)考慮樣本標(biāo)簽不確定性對(duì)轉(zhuǎn)移策略的影響，綜合兩種因素后轉(zhuǎn)移評(píng)分如下：

設(shè)第i個(gè)節(jié)點(diǎn)的特征向量是xi，對(duì)標(biāo)簽的不同意見(jiàn)集合是OpSi，由節(jié)點(diǎn)xi轉(zhuǎn)移至xj的評(píng)分為

式中，S(xi→xj,y)表示在xi節(jié)點(diǎn)轉(zhuǎn)移到節(jié)點(diǎn)xj的評(píng)分.本次轉(zhuǎn)移終點(diǎn)節(jié)點(diǎn)xj可能是節(jié)點(diǎn)xi的所有孩子節(jié)點(diǎn)，也可能是節(jié)點(diǎn)xi本身（即本次轉(zhuǎn)移停留在該點(diǎn)），即xj ∈{child(xi)}∪x{i}.記OpSj為標(biāo)簽的意見(jiàn)集合，一般由專(zhuān)家給出.本文通過(guò)衡量它們的一致程度來(lái)度量標(biāo)簽不確定性，進(jìn)一步用信息熵作為一致性的度量指標(biāo).該評(píng)分由轉(zhuǎn)移終點(diǎn)xj與待預(yù)測(cè)樣本x之間的距離有關(guān)，也與樣本xj的標(biāo)簽集合OpSj有關(guān).d(xi,xs)表示樣本xi，xs之間的距離函數(shù)，此處采用歐幾里得距離進(jìn)行度量

按照上述方法，對(duì)邊界樹(shù)的遍歷在圖中終止于樣本E，根據(jù)遍歷過(guò)程可得到樣本集合的路徑Path.上例中，該集合中包括了A、B、C、D、E這5 個(gè)樣本點(diǎn).

步驟3決策.根據(jù)Path 進(jìn)行待預(yù)測(cè)樣本的目標(biāo)分類(lèi)確定.

將相似的歷史樣本及其標(biāo)簽看成證據(jù)，這樣就可以利用證據(jù)理論獲取結(jié)論.在基于D-S 證據(jù)理論的KNN 算法中，所有可能的類(lèi)別組成的集合構(gòu)成了識(shí)別框架，該識(shí)別框架用來(lái)預(yù)測(cè)一個(gè)沒(méi)有標(biāo)記的樣本xs.

對(duì)于未分類(lèi)的樣本xs而言，基于某種距離計(jì)算方法得到的k個(gè)最為相似的樣本構(gòu)成了集合Φs.Φs中的每一個(gè)相似的鄰居都為待預(yù)測(cè)樣本xs是否屬于類(lèi)別集合C中的分類(lèi)Cq提供了證據(jù)支撐.值得注意的是，根據(jù)D-S 證據(jù)理論的定義，該支撐證據(jù)的否定形式是完全未知的，也就是說(shuō)它無(wú)法表示C中子集不包含Cq的其他集合.用mass 函數(shù)來(lái)表示這個(gè)證據(jù)，可以得到如下關(guān)系：

式中，i=1,2,···,k，αq反映了鄰居樣本xi對(duì)于事件“待預(yù)測(cè)樣本xs的分類(lèi)為Cq”支持程度的強(qiáng)弱，可以用任意合理的單調(diào)遞減函數(shù)替代.

根據(jù)樣本與xs之間的距離，可以分別獲得ms,i({Cq}).為了最終確定xs屬于哪個(gè)類(lèi)別，首先根據(jù)D-S 證據(jù)組合規(guī)則將所有證據(jù)組合在一起，對(duì)于每個(gè)類(lèi)q可以得到如下關(guān)系：

式中，BPA 函數(shù)({Cq})度量了鄰居樣本中分類(lèi)為Cq的樣本的組合信度.

本文用αq表示待預(yù)測(cè)樣本xs的k個(gè)鄰居中類(lèi)別為Cq的樣本xi的BPA.然而實(shí)際情況下，標(biāo)簽的本身有一定的不確定性.在每個(gè)鄰近樣本的BPA被合并時(shí)，樣本中標(biāo)簽的不確定性也在不斷積累，這會(huì)導(dǎo)致最終的預(yù)測(cè)準(zhǔn)確度降低.因此，標(biāo)簽的不確定性不可忽略.這里，用UC表示標(biāo)簽不確定性，可以得到關(guān)于BPA函數(shù)的全新形式

類(lèi)似地，對(duì)于每個(gè)分類(lèi)q，根據(jù)D-S 理論證據(jù)融合規(guī)則可得

信息熵（information entropy，IE）是一種不確定性的量度，常用于數(shù)學(xué)、計(jì)算機(jī)科學(xué)等領(lǐng)域[11].本文用信息熵對(duì)OpSi的不一致性加以量化

式中，Pic為意見(jiàn)集合OpSi中分類(lèi)為c的樣本數(shù)量與OpSi總樣本數(shù)量的比值.則

式中，UC0和βμ為參數(shù).

在邊界樹(shù)上獲得Path 的基礎(chǔ)上，待分類(lèi)樣本的標(biāo)簽可以依據(jù)下式來(lái)確定：

式中，q表示某個(gè)分類(lèi)，UCi表示樣本i的標(biāo)簽不確定度.是集合Path 中分類(lèi)為q的樣本構(gòu)成的集合.

步驟4終止.如果對(duì)該算法的執(zhí)行發(fā)生在訓(xùn)練階段，即待預(yù)測(cè)樣本的標(biāo)簽已知，那么還要決定是否將待預(yù)測(cè)的節(jié)點(diǎn)納入到邊界樹(shù)中.如果該節(jié)點(diǎn)同時(shí)滿(mǎn)足下述兩個(gè)條件：1）對(duì)該節(jié)點(diǎn)的預(yù)測(cè)分類(lèi)與其實(shí)際分類(lèi)不一致，2）遍歷階段的終止節(jié)點(diǎn)的孩子的數(shù)量小于f；則將該節(jié)點(diǎn)納入到樹(shù)中，其直接前驅(qū)便是遍歷階段的終止節(jié)點(diǎn).f為邊界樹(shù)的規(guī)模因子，是邊界樹(shù)節(jié)點(diǎn)孩子數(shù)量最大值，在運(yùn)用算法前設(shè)置它限制邊界樹(shù)規(guī)模.

算法的過(guò)程如下：

在最復(fù)雜的情況下，一個(gè)節(jié)點(diǎn)需要與邊界樹(shù)中的所有節(jié)點(diǎn)計(jì)算轉(zhuǎn)移評(píng)分，因此其計(jì)算復(fù)雜度為樹(shù)的規(guī)模.

4 實(shí) 驗(yàn)

4.1 對(duì)比方法

BT：即文獻(xiàn)[2]中介紹的邊界樹(shù)算法，該算法的本質(zhì)在于快速找到邊界樹(shù)中距離帶預(yù)測(cè)樣本最近的節(jié)點(diǎn)并用其分類(lèi)作為預(yù)測(cè)結(jié)果.

UETKNN：基于不確定性與D-S 證據(jù)理論的KNN算法（uncertain evidence theory-based KNN，UETKNN）.該算法基于普通KNN 算法，在決策時(shí)考慮標(biāo)簽的不確定性，即第3 節(jié)中的步驟3.

ULBT：即本文提出的基于樣本標(biāo)簽不確定性與D-S 證據(jù)理論的邊界樹(shù)算法.相比于BT 算法，該算法預(yù)測(cè)時(shí)，優(yōu)化了樹(shù)上的轉(zhuǎn)移策略，同時(shí)利用UETKNN 算法優(yōu)化了決策過(guò)程.

4.2 評(píng)價(jià)指標(biāo)

邊界樹(shù)算法主要是為了優(yōu)化KNN 算法的計(jì)算效率.因此，無(wú)論是本文提出的算法還是對(duì)比算法，評(píng)價(jià)指標(biāo)都分為規(guī)模指標(biāo)和準(zhǔn)確性指標(biāo)兩大類(lèi).

單例比較次數(shù)（comparing times per instance，CTPI）是一個(gè)規(guī)模性指標(biāo)，描述的是對(duì)于當(dāng)前待預(yù)測(cè)的樣本t，將其輸入算法后，數(shù)據(jù)集內(nèi)所有樣本與該樣本發(fā)生比較的次數(shù).CTPI(t)的值越大，說(shuō)明計(jì)算第t個(gè)樣本的時(shí)間開(kāi)銷(xiāo)越大.值得注意的是，樣本t預(yù)測(cè)前算法已經(jīng)對(duì)前t ?1 個(gè)樣本都進(jìn)行了預(yù)測(cè).

累計(jì)比較次數(shù)（accumulative comparing times，ACT）是另一個(gè)規(guī)模性指標(biāo)，描述的是從第一個(gè)樣本預(yù)測(cè)到第t個(gè)樣本與訓(xùn)練數(shù)據(jù)集中的樣本發(fā)生比較的總次數(shù)

階段準(zhǔn)確率（stage accuracy，SA）是一個(gè)準(zhǔn)確性指標(biāo).SAN(t)表示以第t?N+1 個(gè)樣本到第t個(gè)樣本這N個(gè)樣本為測(cè)試集，前t ?N個(gè)樣本為訓(xùn)練集執(zhí)行算法的命中率（hit rate，HR）

式中，I(·)是指示函數(shù)，當(dāng)?shù)趇個(gè)樣本的預(yù)測(cè)分類(lèi)與其一致分類(lèi)相同時(shí)其值為1，否則為0.

僅針對(duì)邊界樹(shù)算法，用來(lái)衡量邊界樹(shù)本身的規(guī)模還有以下兩個(gè)指標(biāo)：

單例邊界樹(shù)深度（height per instance，HPI）是一個(gè)規(guī)模性指標(biāo)，描述的是對(duì)于當(dāng)前待預(yù)測(cè)的樣本t，將其輸入算法后邊界樹(shù)的深度.

單例邊界樹(shù)節(jié)點(diǎn)數(shù)（nodes per instace，NPI）是一個(gè)規(guī)模性指標(biāo)，描述的是對(duì)于當(dāng)前待預(yù)測(cè)的樣本t，將其輸入算法后邊界樹(shù)的節(jié)點(diǎn)總數(shù).

各評(píng)價(jià)指標(biāo)與類(lèi)型和適用算法對(duì)應(yīng)關(guān)系如表1所示.

表1 各評(píng)價(jià)指標(biāo)與類(lèi)型和適用算法對(duì)應(yīng)關(guān)系Table 1 Correspondence between metrics,type and algorithm

4.3 數(shù)據(jù)集

為了測(cè)試和評(píng)估本文提出的算法性能，首先在真實(shí)數(shù)據(jù)集上分別進(jìn)行計(jì)算效率實(shí)驗(yàn)與算法準(zhǔn)確性實(shí)驗(yàn).而考慮到真實(shí)數(shù)據(jù)集樣本數(shù)量有限的問(wèn)題，本文用窮舉算法生成了一個(gè)更大規(guī)模的隨機(jī)數(shù)據(jù)集來(lái)驗(yàn)證算法的計(jì)算效率.

實(shí)驗(yàn)的數(shù)據(jù)全部來(lái)自BCDB(breast cancer data base)系統(tǒng)[12].實(shí)驗(yàn)中獲取了1 455 個(gè)病例樣本形成數(shù)據(jù)集BCCD(breast cancer chemotherapy dataset)，每個(gè)樣本都有1 個(gè)意見(jiàn)集合OpS 記錄醫(yī)生對(duì)治療方案的投票信息.該數(shù)據(jù)集中的每個(gè)樣本可能分類(lèi)數(shù)量是8，分別對(duì)應(yīng)8 種不同的治療方案.

SD(stochastic dataset)是為了應(yīng)對(duì)真實(shí)數(shù)據(jù)集樣本數(shù)量不足而使用窮舉算法生成的一個(gè)數(shù)據(jù)集.該數(shù)據(jù)集中每個(gè)樣本的特征向量的維度是12，每個(gè)屬性的可能取值的集合是{0,1}，因此該數(shù)據(jù)集的樣本容量是212=4 096.每個(gè)樣本的可能分類(lèi)數(shù)量是5，取值隨機(jī)從集合{0,1,2,3,4,5}中選取一個(gè).

4.4 規(guī)模實(shí)驗(yàn)

圖3展示了在數(shù)據(jù)集BCCD 下，UETKNN 算法下CTPI 和ACT 隨樣本編號(hào)t的變化規(guī)律.該實(shí)驗(yàn)的設(shè)計(jì)是為了適應(yīng)歷史數(shù)據(jù)資源不斷積累的實(shí)際應(yīng)用場(chǎng)景.無(wú)論是UETKNN 算法、基于D-S 證據(jù)理論的EKNN 算法[13]，還是最典型的KNN 算法，最典型的特點(diǎn)都是算法會(huì)將一個(gè)有標(biāo)簽的樣本不加甄別地放到訓(xùn)練集合中形成歷史樣本，這將導(dǎo)致訓(xùn)練樣本不斷增大.由于對(duì)于任意待預(yù)測(cè)樣本，UETKNN 算法都要將其與所有歷史樣本比較.在這種情況下，CTPI(t)和ACT(t)的值僅與歷史樣本容量有關(guān)，而與具體使用了哪個(gè)數(shù)據(jù)集無(wú)關(guān)，即

圖3 UETKNN 算法的CTPI 和ACT 隨樣本編號(hào)t 的變化規(guī)律Figure 3 CTPI and ACT under UETKNN algorithm with the sample number t

本文算法在效率上與BT 算法相似，但準(zhǔn)確率比BT 算法高，與UETKNN 算法相比，本文算法利用BT 算法提升了效率.圖4和5 分別反映了在BCCD 數(shù)據(jù)集和在SD 數(shù)據(jù)集上不同f值時(shí)，ULBT 算法的CTPI 和ACT 隨樣本編號(hào)t改變的變化情況.在邊界樹(shù)算法下，任意待預(yù)測(cè)樣本的比較次數(shù)總是以邊界樹(shù)的節(jié)點(diǎn)總數(shù)為上限.可以看到，無(wú)論是在真實(shí)數(shù)據(jù)集上還是在隨機(jī)數(shù)據(jù)集上，相比于常規(guī)的KNN 算法，ULBT 極大地減小了運(yùn)算的規(guī)模.令規(guī)模因子f取值為25，在BCCD 和SD 數(shù)據(jù)集下最大單例比較次數(shù)分別僅為70 和62.另外，圖像也表明f值確實(shí)對(duì)CTPI 和ACT 的影響較大.由于f限制了邊界樹(shù)的規(guī)模：f值越大邊界樹(shù)的規(guī)模越大；反之亦然，f較大的情況下，CTPI 與ACT 隨樣本數(shù)量上升的速度也越快.類(lèi)似地，圖6和7 分別反映了在BCCD 數(shù)據(jù)集和在SD 數(shù)據(jù)集上不同f值時(shí)，ULBT 算法的NPI 和HPI 隨樣本編號(hào)t改變的變化情況，f值對(duì)NPI 和HPI 也有影響.

圖4 BCCD 數(shù)據(jù)集ULBT 算法的CTPI 和ACT 隨樣本編號(hào)t 的變化規(guī)律Figure 4 CTPI and ACT under the ULBT algorithm with the sample number t of BCCD dactaset

圖5 SD 數(shù)據(jù)集ULBT 算法的CTPI 和ACT 隨樣本編號(hào)t 的變化規(guī)律Figure 5 CTPI and ACT under the ULBT algorithm with the sample number t of SD dataset

圖6 SD 數(shù)據(jù)集和BCCD 數(shù)據(jù)集下ULBT 算法不同f 值下NPI 隨樣本編號(hào)t 的變化規(guī)律Figure 6 NPI of the algorithm under ULBT algorithm with the sample number t in SD dataset and BCCD dataset with different f

圖7 SD 數(shù)據(jù)集和BCCD 數(shù)據(jù)集下ULBT 算法不同f 值下HPI 隨樣本編號(hào)t 的變化規(guī)律Figure 7 HPI of the algorithm under ULBT algorithm with the sample number t in SD dataset and BCCD dataset with different f

4.5 準(zhǔn)確率實(shí)驗(yàn)

本文首先將UETKNN 與普通的KNN 決策方法（第1 節(jié)中介紹的方法）及基于D-S 證據(jù)理論的KNN 算法（evidenced KNN，EKNN）進(jìn)行比較，k取值為10.表2為3 次實(shí)驗(yàn)的數(shù)據(jù)設(shè)置，表3為算法的結(jié)果.

表2 3 次實(shí)驗(yàn)中每個(gè)子集的長(zhǎng)度Table 2 Length of each segment in three experiments

表3 KNN EKNN 和UETKNN 對(duì)比試驗(yàn)結(jié)果Table 3 Comparison results of KNN EKNN and UETKNN %

從實(shí)驗(yàn)結(jié)果可以看出，UETKNN 比普通KNN 決策方法和EKNN 具有更好的性能，這表明融合樣本標(biāo)簽不確定信息能夠提高預(yù)測(cè)的準(zhǔn)確性.

本文提出的ULBT 算法以及BT 算法是一種近似算法.它們的設(shè)計(jì)意圖都是要在較小的計(jì)算效率的前提下快速預(yù)測(cè)出樣本分類(lèi).為了對(duì)比UETKNN 算法、BT 算法、本文提出的算法ULBT，在真實(shí)數(shù)據(jù)集BCCD 上展開(kāi)了對(duì)比實(shí)驗(yàn)，結(jié)果如圖8所示.

圖8統(tǒng)計(jì)了N=200 時(shí)SA 隨樣本序號(hào)的變化規(guī)律.在UETKNN 算法下，SA 隨t逐漸增高，這是因?yàn)橛?xùn)練集越來(lái)越大，信息也越來(lái)越多.在BT 和ULBT 中，SA 隨t的變化也呈現(xiàn)不斷上升的趨勢(shì)，這是因?yàn)殡S著預(yù)測(cè)過(guò)程中不斷有新的節(jié)點(diǎn)加入到邊界樹(shù)中，邊界樹(shù)的信息越來(lái)越完善.

圖8 BCCD 數(shù)據(jù)集下UETKNN 算法、ULBT 算法、BT 算法在不同f 值下SA 隨樣本編號(hào)t 的變化規(guī)律Figure 8 SA of the UETKNN algorithm,ULBT algorithm and BT algorithm of the BCCD dataset with different f values

表4反映了UETKNN、BT、ULBT 算法下SA200隨f的變化規(guī)律，值得注意的是，UETKNN 與邊界樹(shù)規(guī)模因子f無(wú)關(guān)，列于表中僅為方便對(duì)比.對(duì)于ULBT 與BT 階段準(zhǔn)確率SA 而言，SA 與f值基本呈現(xiàn)正相關(guān)的變化規(guī)律且f值越大，f值的變化對(duì)SA 的影響越小.這與f值對(duì)NPI 與HPI 的影響情況一致.可以得出結(jié)論：當(dāng)f值大于某一閾值時(shí)，邊界樹(shù)的規(guī)模與預(yù)測(cè)準(zhǔn)確性基本沒(méi)有關(guān)系.

表4 UETKNN、BT、ULBT 算法下SA200 隨t 的變化規(guī)律Table 4 Variation of SA200 with t under UETKNN,BT,and ULBT algorithms

實(shí)驗(yàn)結(jié)果也表明，由于UETKNN 使用的數(shù)據(jù)集最全面，而B(niǎo)T 與ULBT 為了追求運(yùn)算速度而在預(yù)測(cè)能力上略低于UETKNN.對(duì)比BT 與ULBT，顯然ULBT 的有明顯的性能提升.這表明，ULBT 折中了預(yù)測(cè)準(zhǔn)確率與計(jì)算效率，在盡量保證預(yù)測(cè)精度的前提下，能夠極大地降低計(jì)算量.

5 結(jié) 語(yǔ)

本文研究了提升K-近鄰算法進(jìn)行決策的準(zhǔn)確性和加快決策速度的方法，主要討論了樣本標(biāo)簽不確定條件下利用KNN 進(jìn)行快速?zèng)Q策的相關(guān)問(wèn)題.文中針對(duì)歷史數(shù)據(jù)標(biāo)簽的不確定性的實(shí)際情況，在詳細(xì)研究邊界樹(shù)算法的前提下，介紹了一種全新的基于樣本標(biāo)簽不確定性與D-S 證據(jù)理論的ULBT 算法，該算法對(duì)樹(shù)遍歷的轉(zhuǎn)移策略和目標(biāo)分類(lèi)的決策方法進(jìn)行了優(yōu)化.通過(guò)全面的實(shí)驗(yàn)評(píng)估表明，考慮標(biāo)簽不確定性的方法提高了分類(lèi)的精度，而邊界樹(shù)加快了決策的速度，兩者的結(jié)合實(shí)現(xiàn)了精度和速度的兼顧.