基于圖和K近鄰的文本分類(lèi)算法

吳宗卓

(陜西國(guó)防工業(yè)職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)與軟件學(xué)院， 陜西 西安 710300)

0 引言

文本分類(lèi)是指在預(yù)先定義的主題或類(lèi)別中，將每一個(gè)文本分類(lèi)為其相關(guān)主題或類(lèi)別的過(guò)程[1-2]。作為初步任務(wù)，預(yù)先定義了有限數(shù)量的類(lèi)別，并準(zhǔn)備用一個(gè)或一些預(yù)先定義的類(lèi)別標(biāo)記的示例文本[3]。在學(xué)習(xí)過(guò)程中，利用樣本標(biāo)記文本構(gòu)造分類(lèi)能力。后續(xù)文本是從樣本標(biāo)記文本中分離出來(lái)的文本，被歸類(lèi)為泛化過(guò)程。在本研究中，即使有其他的方法，如人工規(guī)則學(xué)習(xí)和其他啟發(fā)式方法，也假設(shè)使用有監(jiān)督的學(xué)習(xí)算法[4-5]。

然而，將文本編碼成數(shù)值向量會(huì)導(dǎo)致諸如大維數(shù)和稀疏分布等問(wèn)題[6]。圖成為知識(shí)或信息的普遍代表，稱(chēng)為本體論或詞網(wǎng)[7-8]。因?yàn)楸倔w是用來(lái)將知識(shí)表示為圖的，所以在以前的工作中，有很多處理圖的算法。因此，基于這些動(dòng)機(jī)，將文本編碼成圖，并將機(jī)器學(xué)習(xí)算法修改成接收?qǐng)D作為輸入數(shù)據(jù)的版本。本研究采用鄰接矩陣來(lái)表示每一個(gè)圖。通過(guò)避免將文本編碼成數(shù)值向量的問(wèn)題，希望所提出的算法比傳統(tǒng)的K近鄰(K-Nearest Neighbor，KNN)算法有更好的性能。由于圖是比數(shù)值向量更多的符號(hào)文本表示，所以期望在編碼中有更多的透明度。為了更有效地處理文本，并使得文本的表示更加緊湊。因此，本研究的目標(biāo)是實(shí)現(xiàn)滿(mǎn)足效益的文本分類(lèi)。

1 背景知識(shí)

1.1 文本編碼

將文本編碼成圖的過(guò)程，如圖1所示。

圖1 文本編碼成圖的過(guò)程

將圖分解為兩組：頂點(diǎn)集和邊集。頂點(diǎn)和邊分別對(duì)應(yīng)于單詞及其語(yǔ)義關(guān)系。在本研究中，將表示文字的圖作為加權(quán)無(wú)向圖。因此，在本節(jié)中，將詳細(xì)描述把文本表示為圖的過(guò)程。

在將文本編碼到圖中之前，需要構(gòu)造一個(gè)索引列表，其中每個(gè)文本都鏈接到一個(gè)單詞列表。直接從語(yǔ)料庫(kù)中生成文本列表。每個(gè)文本都被索引到一個(gè)單詞列表中，并與它自己包含的單詞列表相關(guān)聯(lián)。每個(gè)單詞都有其權(quán)重，并將信息作為其與文本的關(guān)系發(fā)布。文本的索引基本上有三個(gè)步驟：標(biāo)記化、詞干化和停止字刪除。

在將文本編碼成圖的過(guò)程中，需要定義頂點(diǎn)后接邊。頂點(diǎn)對(duì)應(yīng)于文本中包含的單詞列表。其中一些是通過(guò)其作為頂點(diǎn)的權(quán)重選擇的,如式(1)。

D(v)={vi1,vi2,…,vim}

(1)

考慮通過(guò)對(duì)文本進(jìn)行排序來(lái)選擇固定數(shù)量的文本的排序選擇，以及選擇權(quán)重大于或等于閾值的文本的基于分?jǐn)?shù)的排序選擇作為選擇方案。通過(guò)索引提取一組表示單詞的頂點(diǎn)。

需要定義邊集和頂點(diǎn)集，以便將一個(gè)詞表示成一個(gè)圖。計(jì)算所有可能的頂點(diǎn)對(duì)的相似度來(lái)表示單詞。因此構(gòu)造了一個(gè)相似度矩陣，其條目是來(lái)自語(yǔ)料庫(kù)的詞之間的相似度。選擇相似度大于給定閾值的詞對(duì)，并定義由以下邊組成的集，如式(2)。

D(e)={ei1,ei2,…,ein}

(2)

接著，需要考慮如何在實(shí)現(xiàn)層將圖表示為其結(jié)構(gòu)化形式。這里有三種方法，第一種方法主要采用的是鄰接矩陣，其中頂點(diǎn)對(duì)應(yīng)于其行和列，條目指示邊權(quán)重。把頂點(diǎn)作為節(jié)點(diǎn)、邊作為指針的鏈表看作是圖的另一種表示形式。第三種方式為一個(gè)圖被表示成一個(gè)邊的列表，這些邊被作為一對(duì)頂點(diǎn)標(biāo)識(shí)符給出，并且每個(gè)權(quán)重都與它自己的權(quán)重相關(guān)聯(lián)。在本研究中，采用第三種方案，即圖被表示成一組邊。

1.2 圖

本節(jié)討論圖運(yùn)算及其實(shí)現(xiàn)的基礎(chǔ)。它由兩部分組成，相似度矩陣及其運(yùn)算。

(1) 相似度矩陣：本小節(jié)關(guān)注相似度矩陣作為對(duì)字符串向量執(zhí)行語(yǔ)義操作的基礎(chǔ)。相似度矩陣的每一行和每一列對(duì)應(yīng)于語(yǔ)料庫(kù)中的一個(gè)單詞。所有可能的詞對(duì)的相似度都是以0和1之間的標(biāo)準(zhǔn)化值給出的。從語(yǔ)料庫(kù)中構(gòu)造的相似矩陣，該矩陣是對(duì)稱(chēng)元素和對(duì)角元素為1的N×N方陣。在本小節(jié)中，將正式描述相似矩陣的定義和特征。

相似度矩陣的每個(gè)條目都表示兩個(gè)對(duì)應(yīng)單詞之間的相似度。這兩個(gè)詞ti和tj被視為兩組文本。這兩個(gè)詞之間的相似性，由式(3)計(jì)算。

(3)

其中,|Ti|為集合的基數(shù)Ti。相似度總是以0和1之間的標(biāo)準(zhǔn)化值給出；如果兩個(gè)文檔彼此完全相同，則相似度變?yōu)?，如式(4)。

(4)

如果兩個(gè)單詞沒(méi)有共享的文本，那么Ti∩Tj=?的相似度為0，如式(5)。

(5)

在下一步的研究中將考慮更先進(jìn)的相似度計(jì)算方案。

從文本集合中，構(gòu)建了N×N方陣，如式(6)。

(6)

集合N中包含的單個(gè)單詞對(duì)應(yīng)于矩陣的行和列。條目sij由式(3)計(jì)算，如式(7)。

sij=sim(ti,tj)

(7)

式(3)中的分母防止了文本長(zhǎng)度的高估或低估。對(duì)于文本數(shù)N，構(gòu)建上述矩陣需要二次復(fù)雜度O(N2)。

用數(shù)學(xué)方法來(lái)描述上面的相似矩陣。由于每一列和每一行在矩陣的對(duì)角線(xiàn)位置對(duì)應(yīng)其相同的文本，所以對(duì)角線(xiàn)元素總是由式(3)給出1。在矩陣的非對(duì)角位置，由于式(3)中的0≤2|Ti∩Ti|≤|Ti|+|Tj|，這些值總是作為介于0和1之間的標(biāo)準(zhǔn)化值給出。證明了相似矩陣是對(duì)稱(chēng)的，如式(8)。

(8)

因此，該矩陣被描述為由0到1之間的歸一化值組成的對(duì)稱(chēng)矩陣。

相似矩陣可以從語(yǔ)料庫(kù)中自動(dòng)構(gòu)造。語(yǔ)料庫(kù)中包含的N個(gè)文本作為輸入，每一個(gè)文本都被索引成一個(gè)單詞表。生成所有可能的詞對(duì)，并通過(guò)式(1)計(jì)算它們之間的相似性。通過(guò)計(jì)算它們，構(gòu)造了由相似性組成的方陣。一旦建立了相似度矩陣，它將繼續(xù)作為對(duì)字符串向量執(zhí)行操作的基礎(chǔ)。

(2) 圖之間的相似度：本節(jié)涉及計(jì)算兩個(gè)圖之間相似度的方案。單詞被編碼成圖，其中頂點(diǎn)是文本標(biāo)識(shí)符，邊是文本之間的相似性。假設(shè)每一個(gè)圖都是一組邊，并考慮計(jì)算圖之間相似性的三種情況：都重合，只有一個(gè)重合，以及無(wú)重合。圖之間的相似度是通過(guò)平均邊之間的相似度來(lái)計(jì)算的，并且總是以0到1之間的標(biāo)準(zhǔn)值給出。因此，本節(jié)旨在正式描述計(jì)算圖之間相似度的過(guò)程。

需要考慮由sim(ei,ej)表示的兩個(gè)獨(dú)立邊ei和ej之間的相似性，每個(gè)加權(quán)邊由兩個(gè)節(jié)點(diǎn)組成，其權(quán)重如式(9)。

ei={vi1,vi2,wi}

(9)

邊權(quán)用w(ei)=wi表示。如果沒(méi)有節(jié)點(diǎn)被兩條邊(A,B,0.2)和(C,D,0.4)共享，則相似度為零。如果(A,B,0.2)和(B,C,0.4)這樣的兩條邊只共享一個(gè)節(jié)點(diǎn)，則相似度變成兩個(gè)權(quán)重的乘積，具體如式(10)。

sim(ei,ej)=w(ei)w(ej)

(10)

如果兩個(gè)節(jié)點(diǎn)都共享，則相似度將成為兩個(gè)權(quán)重的平均值,如式(11)。

(11)

假設(shè)邊之間的每一個(gè)權(quán)重總是作為0到1之間的標(biāo)準(zhǔn)化值給出。

兩個(gè)圖G1和G2表示為兩組,如式(12)。

(12)

并且假設(shè)兩個(gè)圖的邊數(shù)相同。所有可能的邊對(duì)都是由這兩個(gè)圖生成的。對(duì)于一個(gè)圖中的每一條邊，計(jì)算其與另一條圖中的邊的相似度，得到其中的最大值作為邊與圖之間的相似度為式(13)。

(13)

兩個(gè)圖之間的相似性是通過(guò)對(duì)邊與另一個(gè)圖之間的最大相似性進(jìn)行平均來(lái)設(shè)置的，如式(14)。

(14)

由于邊的權(quán)值總是作為規(guī)范化值給出的，所以圖之間的相似度總是如此。

接下來(lái)，從數(shù)學(xué)上描述計(jì)算圖之間相似性的操作。如果兩個(gè)圖G1和G2彼此相同，并且所有邊都用1值加權(quán)，即?i,w(e1i)=1,w(e2i)=1，則兩個(gè)圖之間的相似性變?yōu)?，如式(15)。

(15)

如果兩個(gè)圖G1和G2具有不同的權(quán)重，則兩個(gè)圖之間的相似性是兩個(gè)圖的平均權(quán)重，如式(16)。

(16)

如果兩個(gè)圖之間沒(méi)有共享邊，則相似度為零，如式(17)。

(17)

從數(shù)學(xué)刻畫(huà)可以證明，兩個(gè)圖之間的相似性總是一個(gè)介于0和1之間的標(biāo)準(zhǔn)化值。

2 改進(jìn)的KNN算法

傳統(tǒng)的KNN算法如圖2所示。

圖2 傳統(tǒng)KNN示意圖

用正類(lèi)或負(fù)類(lèi)標(biāo)記的樣本詞被編碼成數(shù)值向量。用歐幾里德距離或余弦相似性計(jì)算表示新樣本的數(shù)值向量與已有樣本的數(shù)值向量之間的相似性。選取K個(gè)最相似的樣本詞作為K個(gè)最近鄰，通過(guò)投票決定新樣本的標(biāo)簽。但是，請(qǐng)注意，傳統(tǒng)的KNN版本在計(jì)算非常稀疏的數(shù)值向量之間的相似性方面非常脆弱。

與傳統(tǒng)的分類(lèi)方法不同，改進(jìn)后的KNN算法的分類(lèi)過(guò)程,如圖3所示。

圖3 改進(jìn)的KNN示意圖

用正類(lèi)或負(fù)類(lèi)標(biāo)記的樣本文本通過(guò)第1.1節(jié)中描述的過(guò)程編碼成圖。兩個(gè)圖之間的相似性通過(guò)第1.2節(jié)中描述的方案計(jì)算。與傳統(tǒng)版本相同，在提出的版本中，選擇K個(gè)最相似的樣本，并通過(guò)對(duì)樣本實(shí)體的投票決定新樣本的標(biāo)簽。由于圖中的稀疏分布在本質(zhì)上是不可得的，因此本研究一定能克服稀疏分布的差分性，并且還可以繼續(xù)優(yōu)化，如可以將不同的權(quán)重分配給選定的鄰居，而不是相同的鄰居：最大的權(quán)重分配給第一個(gè)最近的鄰居，最小的權(quán)重分配給最后一個(gè)鄰居。與固定數(shù)量的近鄰不同，選擇了一個(gè)已給定的新樣本為中心的超球體內(nèi)任意數(shù)量的訓(xùn)練樣本作為近鄰。分類(lèi)分?jǐn)?shù)是根據(jù)訓(xùn)練樣本的相似性按比例計(jì)算的，而不是選擇最近的鄰居。還可以考慮兩個(gè)以上的變體組合在一起的變體。

3 實(shí)驗(yàn)與評(píng)估

3.1 實(shí)驗(yàn)環(huán)境

本研究的實(shí)驗(yàn)環(huán)境主要是基于Ubuntu 14.04的Linux操作系統(tǒng)，采用Intelcore I7 2.5 GHz的CPU，16 GB的內(nèi)存，使用的編程語(yǔ)言為Python 2.7, 在Pycharm下運(yùn)行。在所有實(shí)驗(yàn)中使用的數(shù)據(jù)來(lái)源為路透社公開(kāi)的分類(lèi)語(yǔ)料庫(kù)[9]。在實(shí)驗(yàn)中從語(yǔ)料庫(kù)中選擇了相當(dāng)數(shù)量的數(shù)據(jù)作為訓(xùn)練集，并同時(shí)選取了對(duì)應(yīng)的作為測(cè)試集。分類(lèi)類(lèi)別包括了計(jì)算機(jī)、政治、教育、藝術(shù)、環(huán)境、歷史。整個(gè)訓(xùn)練集共有3 283個(gè)樣本，其中每一小類(lèi)的樣本數(shù)量不小于400篇。測(cè)試集共有2 942個(gè)樣本，其中每一小類(lèi)的樣本數(shù)量不小于500篇。

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

評(píng)價(jià)文本分類(lèi)算法性能主要是通過(guò)準(zhǔn)確率P，召回率R，以及與這兩個(gè)值相關(guān)的F1值。具體計(jì)算式如式(18)。

(18)

式中，a代表實(shí)例正確分配到正類(lèi)中的數(shù)目;b代表分配到正類(lèi)中的誤分實(shí)例;c代表屬于被分到負(fù)類(lèi)中原本屬于正類(lèi)的實(shí)例的數(shù)量。

因?yàn)檎倩芈屎蜏?zhǔn)確率是相互互補(bǔ)的。所以為了綜合考慮這兩個(gè)因素，通過(guò)計(jì)算F1值得到相關(guān)結(jié)果，如式(19)。

(19)

3.3 結(jié)果評(píng)估

為了體現(xiàn)提出算法的性能，將本研究與傳統(tǒng)KNN算法，LLKNN(Locally LinearK-Nearest Neighbor)算法[10]以及TextCNN(Textconvolutional neural networks)算法[11]進(jìn)行對(duì)比。結(jié)果如表1所示。

表1 數(shù)據(jù)集對(duì)比結(jié)果(%)

從表1結(jié)果可以知道，本研究相比KNN、TextCNN以及LLKNN算法，本研究提出的算法的性能較好，平均能達(dá)到92%左右，尤其是相對(duì)于原始的KNN算法，結(jié)果提高了將近6%。從細(xì)節(jié)上看，提出算法的P值在環(huán)境這一小類(lèi)中達(dá)到最大為98.98%，在計(jì)算機(jī)分類(lèi)中，達(dá)到最大，為99.35%。同樣的在計(jì)算機(jī)分類(lèi)中，F(xiàn)1也是最大的，為96.53%。綜上所述，提出的改進(jìn)算法具有較好的性能。

4 總結(jié)

所提出的研究成果可以應(yīng)用于醫(yī)學(xué)或工程學(xué)等特定領(lǐng)域的技術(shù)文獻(xiàn)分類(lèi)，而不是單單限于不同領(lǐng)域的新聞文章。通過(guò)在表示文本的圖上用數(shù)學(xué)方法定義和刻畫(huà)更高級(jí)的運(yùn)算，使用更復(fù)雜的操作，將更先進(jìn)的機(jī)器學(xué)習(xí)算法修改為基于圖的算法。采用該方法，將文本分類(lèi)系統(tǒng)作為一個(gè)系統(tǒng)模塊或一個(gè)獨(dú)立的軟件來(lái)實(shí)現(xiàn)。

未來(lái)還需要在圖上定義更多的操作，以便將其他機(jī)器學(xué)習(xí)算法修改為基于圖的版本。在本研究中，只有定義圖之間的相似度，才能修正KNN算法。為了修改K均值算法，需要再定義一個(gè)操作，在這些操作之間建立一個(gè)具有代表性的原型圖。對(duì)于輸入和權(quán)重都以圖的形式給出的感知器或多層感知器，還需要圖的更新規(guī)則。為了在圖上定義更高級(jí)的運(yùn)算，未來(lái)還需要在圖論的基礎(chǔ)上對(duì)運(yùn)算做更多的理論研究。