基于PageRank的主動(dòng)學(xué)習(xí)算法

鄧思宇，劉福倫，黃雨婷，汪敏

（1. 西南石油大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，四川 成都 610500; 2. 西南石油大學(xué) 電氣信息學(xué)院，四川 成都 610500）

傳統(tǒng)的監(jiān)督學(xué)習(xí)算法，如 Na?ve Bayes[1]、One-R[2]和J48[3]等，其分類效果依賴于訓(xùn)練數(shù)據(jù)的有效性。通常情況下，使用已標(biāo)記的樣本作為訓(xùn)練集，學(xué)習(xí)算法以此訓(xùn)練出分類模型。然而，在真實(shí)的數(shù)據(jù)分析場(chǎng)景下，大量的無(wú)標(biāo)注樣本較易獲取，而已標(biāo)注樣本數(shù)量稀少且難以獲取。對(duì)海量數(shù)據(jù)進(jìn)行標(biāo)注是耗時(shí)、昂貴且困難的。在此情況下，半監(jiān)督學(xué)習(xí)(semi-supervised learning)[4]和主動(dòng)學(xué)習(xí)(active learning)[5]被提出并得到快速發(fā)展，已經(jīng)被廣泛地應(yīng)用在文本分類[6]、語(yǔ)音識(shí)別[7]和圖像分類[8]等領(lǐng)域。

主動(dòng)學(xué)習(xí)模擬一種人機(jī)交互場(chǎng)景，允許學(xué)習(xí)算法根據(jù)查詢策略，主動(dòng)獲取選取樣本的真實(shí)類標(biāo)簽，對(duì)主動(dòng)標(biāo)注的樣本進(jìn)行訓(xùn)練，不斷修正已有分類模型，從而提高分類器的泛化能力和分類精度。因此，主動(dòng)學(xué)習(xí)的主要挑戰(zhàn)是制定有效的樣本選擇策略。目前，比較常見(jiàn)的主動(dòng)學(xué)習(xí)方法有不確定抽樣(sampling uncertainty, UC)[9]，基于聚類(clustering-based approaches, CBA)[10]和基于委員會(huì)投票采樣法(query-by-committee, QBC)[11]。其中，不確定性抽樣方法選擇當(dāng)前分類器中不確定度最高的未標(biāo)注樣本進(jìn)行標(biāo)注，并將其添加到訓(xùn)練集中。由于單一分類器存在分類偏好，使得泛化能力產(chǎn)生定式，而QBC通過(guò)多種同質(zhì)或異質(zhì)分類器共同參與分類，一般選取沖突性(不一致性)最高的未標(biāo)注樣本進(jìn)行標(biāo)注?；诰垲惖臉颖具x擇方法旨在通過(guò)分析樣本間的內(nèi)在相似性，對(duì)樣本進(jìn)行劃簇，而后從每簇中選擇代表樣本進(jìn)行標(biāo)注。

PageRank[12]建立在隨機(jī)沖浪模型上，通過(guò)計(jì)算網(wǎng)頁(yè)的PageRank分值，解決了互聯(lián)網(wǎng)搜索引擎的網(wǎng)頁(yè)排名問(wèn)題。PageRank理論基于兩個(gè)簡(jiǎn)單的假設(shè)：1)較重要的網(wǎng)頁(yè)被更多的網(wǎng)頁(yè)鏈接；2)PageRank分值越高的網(wǎng)頁(yè)將傳遞更高的權(quán)重。本文結(jié)合PageRank理論，將PageRank分值作為樣本信息量的度量指標(biāo)，同時(shí)充分考慮樣本的分布信息，提出一種基于PageRank的主動(dòng)學(xué)習(xí)算法(PageRank-based active learning algorithm, PAL)，為主動(dòng)學(xué)習(xí)算法中樣本的選擇問(wèn)題提供一種可行的方案。

實(shí)驗(yàn)在8個(gè)公開(kāi)數(shù)據(jù)集上進(jìn)行，通過(guò)設(shè)置不同規(guī)模的訓(xùn)練集，測(cè)試PAL算法的分類性能。實(shí)驗(yàn)結(jié)果表明，PAL 算法較 Na?ve Bayes、J48、kNN[13]和One-R等經(jīng)典分類算法，通常能得到更高的分類精度，且與 QBC、KQBC[14]和 MADE[15]等主動(dòng)學(xué)習(xí)算法相比，有更好的分類性能。

1 數(shù)據(jù)模型

在本節(jié)中，主要介紹決策信息系統(tǒng)、PageRank理論等基本概念。

1.1 決策信息系統(tǒng)

定義1 決策信息系統(tǒng)[16]。決策信息系統(tǒng)定義成一個(gè)三元組：

式中：U代表一個(gè)非空樣本集合，也稱論域；C代表一個(gè)非空條件屬性集合；d指的是樣本的決策U={x0,x1,x2,···,x15}C={a1,a2,a3,a4}屬性。表1是1個(gè)決策信息系統(tǒng)， ，。

表 1 決策信息系統(tǒng)Table 1 Example of decision system

定義2 曼哈頓距離。向量 x = [a1a2···am] 與y=[b1b2···bm]的曼哈頓距離為

式(2)表示在多維空間中兩個(gè)點(diǎn)之間的距離。信息表的樣本可以用向量表示。相應(yīng)地，可以定義任意一組樣本的相似度。

定義3 相似度。給定一個(gè)決策信息系統(tǒng)S =(U,C,d)， 任 意 x , y ∈U 的相似度記為

根據(jù)式(2)、式(3)，可計(jì)算表1的決策信息系統(tǒng)中 s i m (x0,x6)=0.13， s i m (x3,x12)=0.127。

定義4 鄰域。對(duì)于任意的樣本 x ∈ U，可以通過(guò)設(shè)置相似度閾值θ的方式確定其鄰域，樣本的鄰域定義為

相似度閾值θ越小，樣本的鄰域越大。根據(jù)表1所示的決策信息系統(tǒng)可以計(jì)算出n(x0,0.5)={x1,x2,x3,x4}。

1.2 PageRank模型

Web中的網(wǎng)頁(yè)通過(guò)超鏈接相互鏈接，Page-Rank算法計(jì)算每個(gè)網(wǎng)頁(yè)的PageRank分值。Page-Rank分值可作為網(wǎng)頁(yè)重要程度的度量指標(biāo)。圖1表示一個(gè)Web超鏈接圖。

圖 1 超鏈接網(wǎng)絡(luò)Fig. 1 Hyperlink network

定義5 PageRank分值。將互聯(lián)網(wǎng)中的網(wǎng)頁(yè)抽象成一個(gè)有向圖 G =(V,E)。E是網(wǎng)頁(yè)超鏈接集合，V是網(wǎng)頁(yè)集合。設(shè) n = |V|，網(wǎng)頁(yè)i的PageRank分值point(i)定義為

式中Oj表示網(wǎng)頁(yè)j的出度。此時(shí)，PageRank分值的n維行向量可用P表示，即

有向圖G的鄰接矩陣可以用 A =(aij)n×n表示，其中：

根據(jù)式(6)、式(7)可定義n維方程組為

式(8)是循環(huán)定義式。迭代求得分值向量P，即P不再顯著變化或者趨近收斂時(shí)，停止迭代。初始情況下，所有網(wǎng)頁(yè)的排名是相同的，即P0=[1 1···1]。極小值ε是人工設(shè)定的收斂閾值，用于驗(yàn)證向量P是否收斂。每輪迭代結(jié)束后，若則認(rèn)為達(dá)到收斂條件。

在有向圖G中，存在沒(méi)有出度的網(wǎng)頁(yè)v，稱之為懸掛網(wǎng)頁(yè)，如圖1中的V5。懸掛網(wǎng)頁(yè)導(dǎo)致排名下沉，PageRank分值向量P在經(jīng)過(guò)i次迭代后，其值均為0。將Web圖用馬爾可夫鏈[17]進(jìn)行建?？梢越鉀Q上述問(wèn)題。

將網(wǎng)頁(yè)看作馬爾可夫鏈的狀態(tài)，超鏈接表示狀態(tài)轉(zhuǎn)移。這樣，Web沖浪將表示成一種隨機(jī)過(guò)程。狀態(tài)轉(zhuǎn)移矩陣T必須滿足3個(gè)條件：隨機(jī)矩陣、不可約、非周期。因此，將鄰接矩陣A進(jìn)行如下修訂：

式中：γ是阻尼系數(shù)，一般情況下γ∈(0, 1)；E是一個(gè)n×n階且元素全為1的矩陣；E /n表示一網(wǎng)頁(yè)鏈接其他網(wǎng)頁(yè)的隨機(jī)概率，即1/n。

2 問(wèn)題與算法

2.1 問(wèn)題描述

在主動(dòng)學(xué)習(xí)應(yīng)用場(chǎng)景中，算法標(biāo)注最具信息量的樣本來(lái)構(gòu)建高精度分類器?？晒┎樵兊臉?biāo)簽數(shù)量N是輸入?yún)?shù)之一。

式中：|Ur|是訓(xùn)練集大??；|Ut|是測(cè)試集大??；error是誤分類樣本數(shù)量。若可供查詢的標(biāo)簽數(shù)量為N，則

2.2 PAL算法描述

PAL算法可以細(xì)分為3個(gè)子算法，分別是PageRank排名計(jì)算算法、二叉樹(shù)生成算法和二叉樹(shù)聚類算法。偽代碼符號(hào)定義如表2。

表 2 符號(hào)定義Table 2 Symbol definitions

2.2.1 PageRank排名計(jì)算算法

利用PageRank計(jì)算每個(gè)樣本的分值，該分值可作為樣本信息量的度量標(biāo)準(zhǔn)，即分值越大樣本所含信息量越高。

給定決策信息類系統(tǒng) S =(U,C,d)，對(duì)于任意的 x , x′∈ U ， 且 x ∈ n (x′,θ) 。根據(jù)式(4)、式(5)計(jì)算樣本x在PageRank模型下所獲得的分?jǐn)?shù)point(x)：

算法1描述了樣本的排名向量的計(jì)算過(guò)程。1)～7)通過(guò)計(jì)算樣本間的相似度，確定每個(gè)樣本的鄰域； 10)根據(jù)式(9)計(jì)算狀態(tài)轉(zhuǎn)移矩陣T；11)定義初始分值向量P0；12)～15)計(jì)算收斂條件下分值矩陣P；16)對(duì)分值矩陣P進(jìn)行降序排序。

2.2.2 二叉樹(shù)生成算法

主動(dòng)學(xué)習(xí)階段在二叉樹(shù)上進(jìn)行，為了避免離群點(diǎn)對(duì)該階段標(biāo)簽查詢、預(yù)測(cè)的影響，保證查詢到的樣本均具有較高的信息量，僅利用排名前R的代表樣本去構(gòu)建二叉樹(shù)。同時(shí)，樹(shù)形結(jié)構(gòu)能夠充分體現(xiàn)數(shù)據(jù)的層次關(guān)系，便于數(shù)據(jù)分析，從而得到更好的聚類結(jié)果。

二叉樹(shù)生成算法是一個(gè)典型遞歸算法。其構(gòu)建過(guò)程分為兩步：尋找孩子節(jié)點(diǎn)，根據(jù)孩子節(jié)點(diǎn)劃分集合。根結(jié)點(diǎn)root的孩子節(jié)點(diǎn)是U′中最不相似的兩個(gè)樣本，其余節(jié)點(diǎn)x的左孩子是當(dāng)前集合中與x最相似的樣本xl，右節(jié)點(diǎn)是當(dāng)前集合中與xl最不相似的節(jié)點(diǎn)xr。

3)～5)尋找 root的孩子節(jié)點(diǎn)，即 U′中最不相似的一對(duì)樣本；7)～10)尋找非root節(jié)點(diǎn)的孩子節(jié)點(diǎn)；12)定義 xl和 xr的樣本集合；13)～19)通過(guò)比較集合U′中樣本與xl、x相似度大小，實(shí)現(xiàn)集合的劃分；20)～21)遞歸調(diào)用算法 2。

2.2.3 二叉樹(shù)聚類算法

一般來(lái)說(shuō)，聚類簇?cái)?shù)K與聚類質(zhì)量關(guān)系密切，然而大多數(shù)聚類算法只能通過(guò)經(jīng)驗(yàn)或者試湊指定簇?cái)?shù)K。本文采用一種執(zhí)行邊緣分離的聚類策略，不需要將K作為輸入，而是根據(jù)二叉樹(shù)的內(nèi)部結(jié)構(gòu)自然地分簇。

通過(guò)計(jì)算二叉樹(shù)節(jié)點(diǎn)間的相似度，將二叉樹(shù)的邊劃分為分割邊或者非分割邊。假設(shè)兩節(jié)點(diǎn)足夠相似，可將該連邊定義成非分割邊，反之定義為分割邊。這種邊界劃分方式基于一個(gè)閾值。第一輪迭代時(shí)，閾值是二叉樹(shù)相連節(jié)點(diǎn)間相似度的最小值。

算法3詳細(xì)描述了基于二叉樹(shù)的聚類過(guò)程。通過(guò)遍歷樹(shù)的節(jié)點(diǎn)，同時(shí)用數(shù)組cn記錄節(jié)點(diǎn)的簇號(hào)，實(shí)現(xiàn)聚類。lc表示左孩子，同理rc表示右孩子。count用于記錄遞歸過(guò)程中最大簇?cái)?shù)。1)定義聚類函數(shù)；2)記錄節(jié)點(diǎn)的簇號(hào)；3)～9)根據(jù)相似度關(guān)系判斷簇邊界，如當(dāng)前節(jié)點(diǎn)與它的孩子節(jié)點(diǎn)的相似度小于閾值threshold，count自增后進(jìn)行下一次遞歸；14)～21)整理 cn得到分塊信息表bl。該方法可以解決聚類算法需要人工設(shè)定K值的問(wèn)題。

2.2.4 主動(dòng)學(xué)習(xí)

主動(dòng)學(xué)習(xí)階段，利用二叉樹(shù)聚類算法生成的信息塊bl對(duì)代表樣本進(jìn)行標(biāo)記和預(yù)測(cè)。

1)如bli中存在未分類樣本，則查詢bli中PageRank值較高的一部分樣本的標(biāo)簽。

2)如bli中已分類的樣本數(shù)量足夠大(Pi≥且標(biāo)簽一致，則可預(yù)測(cè)該塊中剩余樣本的標(biāo)簽。

3)增大閾值threshold，進(jìn)行下一輪聚類、標(biāo)記和預(yù)測(cè)。達(dá)到標(biāo)簽查詢上限后，對(duì)不純的塊，采取投票的方式確定剩余未標(biāo)記代表樣本的標(biāo)簽。

主動(dòng)學(xué)習(xí)階段結(jié)束時(shí)，代表樣本均已獲得標(biāo)簽。將代表樣本作為訓(xùn)練集，采用kNN算法對(duì)其他樣本進(jìn)行分類。

2.3 樣例分析

提供一個(gè)樣例分析來(lái)進(jìn)一步清楚說(shuō)明PAL算法。使用表1的決策信息系統(tǒng)，允許查詢的最大標(biāo)簽數(shù)N =7。設(shè)置阻尼γ=0.95，ε=0.01。圖2和圖3展示兩次迭代聚類之后查詢標(biāo)簽的情況。bl4中 x0被標(biāo)記為 is。所以 x1、x2、x3、x4和 x5被標(biāo)記為is。

圖 2 第一次迭代Fig. 2 First iteration of the running example

圖 3 第二次迭代Fig. 3 Second iteration of the running example

在本例中，查詢7個(gè)樣本的標(biāo)簽，預(yù)測(cè)4個(gè)樣本的標(biāo)簽，5個(gè)樣本通過(guò)投票獲得標(biāo)簽。無(wú)樣本被錯(cuò)誤標(biāo)記，因此，精度為100%。

3 實(shí)驗(yàn)及分析

在本節(jié)中，通過(guò)實(shí)驗(yàn)將PAL算法與傳統(tǒng)的分類算法、主動(dòng)學(xué)習(xí)算法進(jìn)行比較，并回答以下問(wèn)題：

1) PAL算法選擇代表樣本是否具有可靠性，尤其不同二叉樹(shù)比例R的設(shè)置對(duì)精度的影響；2) PAL算法是否比其他監(jiān)督學(xué)習(xí)算法更精確；3) PAL算法是否比主動(dòng)學(xué)習(xí)算法的分類效果好。

3.1 實(shí)驗(yàn)步驟

實(shí)驗(yàn)結(jié)合Weka，在macOS Sierra操作系統(tǒng)下運(yùn)行，其硬件配置為：2.6 GHz Intel Core i5處理器，8 GB 1600 MHz DDR3。

實(shí)驗(yàn)采用8個(gè)公開(kāi)的數(shù)據(jù)集，并將PAL算法與 J48、kNN、Na?ve Bayes、One-R 和 Logistics[18]這5種傳統(tǒng)的監(jiān)督學(xué)習(xí)算法進(jìn)行比較，同時(shí)與QBC、KQBC和MADE這3種主動(dòng)學(xué)習(xí)算法作對(duì)比。實(shí)驗(yàn)采用分類精度accuracy作為評(píng)估指標(biāo)。

與傳統(tǒng)的監(jiān)督學(xué)習(xí)分類算法的比較實(shí)驗(yàn)中，針對(duì)每個(gè)數(shù)據(jù)集，實(shí)驗(yàn)設(shè)置訓(xùn)練集以1%為步長(zhǎng)，規(guī)模由1%增加到10%。在訓(xùn)練集規(guī)模不同的情況下，觀察分類精度的變化。在與主動(dòng)學(xué)習(xí)算法的比較實(shí)驗(yàn)中，訓(xùn)練集規(guī)模均設(shè)置為10%。

設(shè)置二叉樹(shù)比例R∈[20%, 50%]，阻尼因子γ∈[0.65, 0.95]，極小值ε=0.01。為了降低實(shí)驗(yàn)的隨機(jī)性誤差，采用相同參數(shù)設(shè)置進(jìn)行10次重復(fù)實(shí)驗(yàn)，取得平均值作為實(shí)驗(yàn)結(jié)果。

實(shí)驗(yàn)所用數(shù)據(jù)集詳細(xì)信息如表3所示。

表 3 數(shù)據(jù)集描述Table 3 Description of experimental datasets

3.2 參數(shù)R對(duì)分類效果的影響

在本節(jié)中，將回答問(wèn)題1)。討論不同的二叉樹(shù)比例R對(duì)實(shí)驗(yàn)精度的影響。表4展現(xiàn)了在訓(xùn)練集規(guī)模是數(shù)據(jù)集的10%的情況下，所得精度隨R的變化情況。

表 4 PAL算法在不同二叉樹(shù)構(gòu)建比例R下分類精度的比較Table 4 Classification accuracy comparisons of PAL based on different Binary Tree ratios R

由表4可以看出，對(duì)于不同的數(shù)據(jù)集，最佳的二叉樹(shù)比例取值存在差異。但從整體來(lái)看，最佳取值都集中在[20, 50]區(qū)間。

實(shí)驗(yàn)結(jié)果符合數(shù)據(jù)集樣本的分布規(guī)律，信息量較高的樣本所占的比例較小。二叉樹(shù)比例取值越大時(shí)，越多的信息量低的樣本參與到二叉樹(shù)的構(gòu)建，一些離群點(diǎn)、邊界點(diǎn)影響聚類結(jié)果，而導(dǎo)致分類錯(cuò)誤。同時(shí)表明，將PageRank分值作為樣本信息量的度量指標(biāo)具有可靠性。

Iris、Seeds、Twonorm 數(shù)據(jù)集樣本均勻，不存在樣本傾斜問(wèn)題，二叉樹(shù)聚類算法能夠獲得很好的分簇效果，因此二叉樹(shù)比例取值較小時(shí)，能夠保證查詢到的樣本都具有高信息量，反而分類精度更高。

較大數(shù)據(jù)集，如Twonorm、Aggregation，R比例較小，所選代表樣本構(gòu)成的樹(shù)形結(jié)構(gòu)也能很好地表現(xiàn)樣本的層次結(jié)構(gòu)，因此對(duì)分類精度不會(huì)有較大影響。

在本文后續(xù)的研究討論中，R當(dāng)作經(jīng)驗(yàn)參數(shù)參與二叉樹(shù)的構(gòu)建。

3.3 與經(jīng)典算法對(duì)比

在本節(jié)中，將回答第二個(gè)問(wèn)題。PAL在8個(gè)數(shù)據(jù)集上與 J48、Na?ve Bayes、kNN、One-R 和 Logistics經(jīng)典算法做了對(duì)比。圖4展示了PAL算法

圖 4 與經(jīng)典算法對(duì)比Fig. 4 Comparison with classical algorithms

以及對(duì)比算法在不同訓(xùn)練集比例下的分類精度變化趨勢(shì)。

實(shí)驗(yàn)結(jié)果表明，本文提出的PAL算法在Iris、Flame、Ecoli、Seeds、Aggregation和 Jain數(shù)據(jù)集上，分類精度高于對(duì)比的經(jīng)典算法，尤其是Flame數(shù)據(jù)集，在實(shí)驗(yàn)所選的訓(xùn)練集比例下，分類精度均高于經(jīng)典分類算法。在Twonorm數(shù)據(jù)集上也能取得較好的分類精度，分類精度達(dá)到97%，僅略低于 Na?ve Bayes算法。在 Diabetes數(shù)據(jù)集上優(yōu)勢(shì)不明顯，尤其是在Diabetes數(shù)據(jù)集上，PAL算法分類精度高于kNN、J48和One-R，但是低于 Na?ve Bayes和 Logistics。

圖4(b)、(d)、(f)顯示，在實(shí)驗(yàn)所選的所有訓(xùn)練集規(guī)模下，對(duì)應(yīng)數(shù)據(jù)集上PAL算法分類精度均高于 kNN 算法；圖 (a)、(c)、(e)、(g)、(h)顯示，在多數(shù)訓(xùn)練集規(guī)模下，對(duì)應(yīng)數(shù)據(jù)集上PAL算法分類精度高于kNN算法。PAL對(duì)代表樣本采用主動(dòng)學(xué)習(xí)算法進(jìn)行標(biāo)記和預(yù)測(cè)，而對(duì)于剩余樣本則采用kNN進(jìn)行預(yù)測(cè)。因此，當(dāng)二叉樹(shù)比例R=0時(shí)，PAL算法將退化成KNN算法。該結(jié)果表明，PAL的樣本選擇策略和主動(dòng)學(xué)習(xí)算法具有可行性。

圖 4(a)、(b)、(d)、(e)、(h)顯示，在訓(xùn)練集規(guī)模極小的情況下，如R=10%時(shí)，PAL較其他經(jīng)典算法能取得較好的分類精度；圖 4(a)、(b)、(e)、(g)顯示，訓(xùn)練集規(guī)模為30%之前，PAL算法的分類精度快速地上升，逐漸趨于穩(wěn)定，說(shuō)明PageRank分值作為樣本信息量的度量指標(biāo)具有可靠性，結(jié)合聚類算法，利用樣本的分布信息能夠有效地進(jìn)行樣本選擇。

圖 4(a)、(b)、(e)、(f)顯示，在 Iris、Flame、Seeds數(shù)據(jù)集上分類時(shí)，訓(xùn)練集的規(guī)模對(duì)PAL分類精度影響不明顯，是因?yàn)閿?shù)據(jù)集太小，訓(xùn)練集比例對(duì)分類效果影響較低。在Twonorm數(shù)據(jù)集上，訓(xùn)練集的規(guī)模對(duì)所有算法的分類精度影響均不明顯，說(shuō)明在該數(shù)據(jù)集上數(shù)據(jù)分布較為均勻。

3.4 與主動(dòng)學(xué)習(xí)算法對(duì)比

將PAL算法與流行的3種主動(dòng)算法進(jìn)行比較。表5展現(xiàn)了在訓(xùn)練集規(guī)模是數(shù)據(jù)集的10%，R設(shè)置為40%的情況下，QBC、KQBC、MADE和PAL的分類精度。為了更清晰地展示各個(gè)算法的性能差異，設(shè)計(jì)以排名為衡量標(biāo)準(zhǔn)的評(píng)估方法。

從總體上看，本文提出的PAL算法與其他主動(dòng)學(xué)習(xí)算法比較平均排名靠前。PAL算法在Iris、Flame、Seeds、Diabetes和 Twonorm 數(shù)據(jù)集上，分類精度高于其他對(duì)比的主動(dòng)學(xué)習(xí)算法，尤其在Flame數(shù)據(jù)集上，分類精度達(dá)到98%。在Ecoli、Jain和Aggregation數(shù)據(jù)集上也有很好的分類表現(xiàn)。

表 5 PAL與3種主動(dòng)學(xué)習(xí)算法的比較Table 5 Accur acies of PAL and thr ee active lear ning algorithms

4 結(jié)束語(yǔ)

本文提出了一種基于PageRank的主動(dòng)學(xué)習(xí)算法，為樣本的選擇問(wèn)題提供了一種可行的方案。利用PageRank理論發(fā)現(xiàn)信息量較高的代表樣本，從而在該集群上構(gòu)建二叉樹(shù)，用來(lái)表示樣本的層次結(jié)構(gòu)。在二叉樹(shù)上進(jìn)行迭代聚類，標(biāo)記和預(yù)測(cè)，能夠保證查詢到的樣本分布均勻，同時(shí)避免離群點(diǎn)的影響。用代表對(duì)象訓(xùn)練得到分類模型，采用kNN算法處理剩余樣本。實(shí)驗(yàn)結(jié)果表明，PAL算法相比于Na?ve Bayes和J48等傳統(tǒng)分類算法，能得到更高的分類精度，且與QBC等主動(dòng)學(xué)習(xí)算法相比，分類效果更好。