K近鄰算法在政府采購數(shù)據(jù)挖掘中的研究與應用

王宏 門博 雷娜

摘 要：隨著政府采購信息化水平的不斷提升，政府部門在履行職責過程中沉淀了大量的政府采購數(shù)據(jù)。本文分析了政府采購中標信息的要素，在研究有監(jiān)督機器學習方法和文本數(shù)據(jù)處理流程的基礎上，選取K近鄰分類算法將其應用于文本分類中，形成政府采購項目領域模型之后，再對各中標公司在各領域的出現(xiàn)情況進行分析，并研究在取不同K值情況下分類的準確率。

關鍵詞： 政府采購數(shù)據(jù);文本數(shù)據(jù)處理;有監(jiān)督的機器學習;K近鄰分類算法;領域模型

文章編號： 2095-2163（2019）03-0269-04 中圖分類號： TP311 文獻標志碼： A

0 引 言

近幾年，國家將“政府信息公開”提升為“政府數(shù)據(jù)開放”。數(shù)據(jù)的開放使得政府積累的數(shù)據(jù)可以更好地被利用和分析，也意味著，這些數(shù)據(jù)可以公開獲得并可以進行研究。政府采購就是指國家各級政府為從事日常的政務活動或為了滿足公共服務的目的，利用國家財政性資金和政府借款購買貨物、工程和服務的行為，政府部門在長期的采購過程中沉淀了大量的各類數(shù)據(jù)，這些數(shù)據(jù)涉及到政府采購的各個方面，包括采購人、招標機構(gòu)、中標人和采購項目信息等，這其中隱藏著各方面之間的千絲萬縷的關聯(lián)關系，只有通過挖掘才能得到有價值的信息[1]。

在數(shù)據(jù)挖掘中，分類是一種很重要的工具。本文將采用K近鄰分類算法對政府采購的中標信息進行分析，以獲取一些關聯(lián)信息。

1 分類介紹

分類是一種有監(jiān)督的學習方法，包括了對文本的分類。文本分類能根據(jù)預先定義的主題類別， 按照一定規(guī)則將文檔集合中未知類別的文本自動分為一個或幾個類別的過程[2]?；蛘哒f能夠根據(jù)已被分類的訓練文本集， 通過特征選擇、特征提取等方法得到特征項，也可以通過訓練得到文本分類器， 然后以此分類器對待分類文本集進行文本分類[3]。目前，經(jīng)典的分類算法有：貝葉斯分類法、決策樹、K近鄰分類算法、支持向量機等[4]。對此可做研究闡述如下。

1.1 K近鄰分類算法

K近鄰分類算法是一個理論上比較成熟的分類算法，其核心思想是：如果一個樣本在特征空間中的K個最相似的樣本中的大部分屬于某一類，則該樣本也屬于這一類，K近鄰算法的分類決策規(guī)則依據(jù)少數(shù)服從多數(shù)的思想。在類的決策上，將只依靠一個或幾個近鄰的點來判定待分類點的類別。

1.2 算法描述

（1）選定訓練數(shù)據(jù)，選定的數(shù)據(jù)不能太多，也不宜過少。

（2）計算待分類數(shù)據(jù)與各個訓練數(shù)據(jù)之間的距離（采用歐式距離）。

（3）選取與該數(shù)據(jù)點距離最小的K個點，K一般為奇數(shù)。

（4）統(tǒng)計這K個點所出現(xiàn)類別的頻率。

（5）選取K個點中出現(xiàn)頻率最高的類作為待分類數(shù)據(jù)的類。

K近鄰算法流程如圖1所示。

1.3 K近鄰算法的優(yōu)缺點

K近鄰算法優(yōu)點如下：

（1）算法易實現(xiàn)。

（2）對數(shù)據(jù)噪音有較強的忍耐能力。

（3）分類時只依賴于最相鄰的K個點，因此只需要選擇合適的K值。

K近鄰近算法缺點如下：

（1）K近鄰分類算法使用惰性學習方法，沒有主動的學習。

（2）不同的K值會導致K近鄰算法的精度有差距[5]。

2 政府采購數(shù)據(jù)處理

政府部門在履行職責過程中沉淀了大量的數(shù)據(jù)[6]，通過網(wǎng)絡爬蟲已經(jīng)可以在各省的政府采購網(wǎng)站上獲取到公開的采購數(shù)據(jù)，包括中標公告（結(jié)果公告）等。如圖2所示。圖2中，描述的是已經(jīng)獲得的中標結(jié)果公告表的部分信息。其中，第一列代表著中標項目，第二列代表著中標公司。

對中標信息分析的總體思路是：首先按領域?qū)φ少彅?shù)據(jù)中標項目進行分類，分析出每個項目屬于哪一個領域，得到分類結(jié)果，因為每條記錄中包含了中標項目與中標公司，一個中標公司對應一個或多個項目，項目屬于哪個領域則相當于該中標公司出現(xiàn)于哪個領域中。也就是通過對項目的領域?qū)傩缘姆诸悾云讷@得各中標公司關注點主要放在那些領域的結(jié)論。

這里，將對中標項目進行分類，但K近鄰算法只能對數(shù)值型數(shù)據(jù)進行處理，所以需要把文本數(shù)據(jù)轉(zhuǎn)換成數(shù)值型數(shù)據(jù)。對中標項目名稱進行文本處理，將文本數(shù)據(jù)轉(zhuǎn)化為數(shù)值型數(shù)據(jù)，使其可以使用K近鄰算法進行分類。具體的文本數(shù)據(jù)處理流程如圖3所示。

對文本數(shù)據(jù)進行數(shù)據(jù)清理，主要是達到格式標準化與重復數(shù)據(jù)清除的目標。

接下來，對政府采購數(shù)據(jù)項目文本數(shù)據(jù)進行分詞并移除停用詞。采用Python語言編寫程序，使用jieba分詞對文檔進行分詞，針對實際的數(shù)據(jù)設置需要移除的停用詞。如：“陜西省”、“咸陽市”、“西安市”等地區(qū)名，這些詞在大部分數(shù)據(jù)中都會出現(xiàn)，并不能代表該文本。實際操作中對“陜西省安康市8個縣土地承包登記正射影像圖制作項目”與“陜西省衛(wèi)生宣傳教育中心健康公益宣傳片拍攝制作項目”進行分詞并移除停用詞得到結(jié)果：[土地 承包 登記 正 射影 像圖 制作]，[ 衛(wèi)生 宣傳教育 中心 健康 公益 宣傳片 拍攝 制作]。

對得到的分詞結(jié)果分別按順序計算TF、IDF，最后得到TF-IDF。其中，TF、IDF以及TF-IDF的含義可分述如下。

（1）詞頻TF：在一份給定的文檔里，詞頻指的是某一個給定的詞語在該文檔中出現(xiàn)的次數(shù)。這個屬性是對詞數(shù)的歸一化，以防止其偏向長的文檔[7]。對于在某一個文檔里的詞語來說，其重要性可用如下公式來表示：

其中，ni， j分子是該詞在文檔中的出現(xiàn)次數(shù)，而∑knk， j則是在文檔中所有字詞的出現(xiàn)次數(shù)之和。

（2）逆向文檔頻率IDF：逆向文檔頻率是一個詞語普遍重要性的度量。某一特定詞語的IDF，可以由總文檔數(shù)目除以包含該詞語的文檔數(shù)目，再將得到的商取對數(shù)，由此得到如下公式：

其中，|D|表示語料庫中的文檔總數(shù)，j：ti∈dj表示包含詞語的文檔數(shù)目，如果該詞語不在語料庫中，就會導致分母為零，因此一般情況下使用1+j：ti∈dj作為分母。

（3）TF-IDF[8]權值：TF與IDF的乘積。TF-IDF是一種用于信息檢索與數(shù)據(jù)挖掘的常用加權技術，是一種統(tǒng)計方法，用來確定一個詞對于一個文本的重要程度。詞的重要性隨著該詞在文本中的出現(xiàn)正比例增加，而隨著其在語料庫中的出現(xiàn)而下降。對此可做出如下公式表示：

得到TFIDF之后，已經(jīng)將文本數(shù)據(jù)轉(zhuǎn)化成數(shù)值型數(shù)據(jù)，此時的數(shù)值數(shù)據(jù)有著高維度的特性，不利于計算和可視化展示。比如K近鄰算法中存在著“維度災難”的問題，即隨著維度的增加，看似相近的2個點之間的距離卻越來越大，將多維數(shù)據(jù)轉(zhuǎn)化成二維或三維數(shù)據(jù)更利于數(shù)據(jù)的使用。主要的降維方法有：主成分分析法、線性判別分析法等降維方法[9]，本文選用主成分分析法進行數(shù)據(jù)降維。主成分分析（PDA）最初是在二十世紀初由Karl Pearson對非隨機變量引入，又稱簡單K-L變換的理論與方法，這是一種對數(shù)據(jù)進行分析與處理的統(tǒng)計學算法，旨在利用降維的思想，將多指標轉(zhuǎn)化成幾個綜合指標，其中每個綜合指標都能反映原始指標的大部分信息，且所含信息互不重復[10]。

使用Python語言有一個好處就是會有很多可以方便使用的工具包，比如此處進行數(shù)據(jù)降維可以使用sklearn包下的PCA（主成分分析法）工具模塊，使用PCA對得到的TF-IDF數(shù)據(jù)進行降維，得到數(shù)據(jù)如：

[0.117 543 596 857 529，0.010 702 118 710 152]，[0.176 951 967 884 651 2，0.008 137 108 014 717]。此時第一個數(shù)據(jù)代表著“陜西省衛(wèi)生宣傳教育中心健康公益宣傳片拍攝制作項目”文本數(shù)據(jù)，第二個則代表“陜西省衛(wèi)生宣傳教育中心健康公益宣傳片拍攝制作項目”。

3 政府采購數(shù)據(jù)應用分析

領域是對所屬行業(yè)的一個劃分，根據(jù)中國的行業(yè)分類并結(jié)合所獲得政府采購數(shù)據(jù)實際的情況，本次研究將所有項目劃分為5個領域、即：專業(yè)服務、電子電工、醫(yī)藥衛(wèi)生、信息產(chǎn)業(yè)以及建筑建材。

3.1 領域分類

對降維后得到的數(shù)據(jù)，使用K近鄰算法進行分類。首先K近鄰分類算法需要一些訓練數(shù)據(jù)集，從降維后的數(shù)據(jù)中選取訓練數(shù)據(jù)集，添加上領域分類標簽，對其可表述如下：

[0.207 055 796 653 806 83，0.058 263 573 135 836 28]專業(yè)服務，

[0.169 101 780 998 629 58，0.008 371 312 576 148 626]電子電工，

[0.133 684 676 453 191 18，0.024 987 790 298 132 31]醫(yī)藥衛(wèi)生，

[0.259 447 879 333 501 83，0.010 690 718 265 212 179]信息產(chǎn)業(yè)，……

訓練集中數(shù)值部分代表已分類的文本數(shù)據(jù)，后面則是按領域分類的標簽。按照算法描述步驟計算待分類數(shù)據(jù)與各個訓練數(shù)據(jù)之間的歐式距離，選取與該數(shù)據(jù)點距離最小的K個點;按少數(shù)服從多數(shù)原則，這K個點大部分屬于信息工程領域類，則將該數(shù)據(jù)分類為信息工程領域，依次重復，直到數(shù)據(jù)分類結(jié)束。其中，K的取值不同，分類效果也有差異。當取不同K值時，研究得到的分類準確率結(jié)果見表1。

可以看出，選取K值為5準確率最高，并繪制出散點圖，如圖4所示。圖4中，“+”點代表建筑建材領域，五角星代表醫(yī)藥衛(wèi)生領域，三角形代表專業(yè)服務領域，六邊形代表電子電工領域，奔馳形狀代表信息產(chǎn)業(yè)領域。

3.2 中標公司在各領域出現(xiàn)情況分析

通過檢索數(shù)據(jù)庫，查詢每一個中標公司所對應的項目，通過該項目的領域分類來判斷中標公司所參與的領域。經(jīng)由分析得出：醫(yī)院只出現(xiàn)于醫(yī)藥衛(wèi)生領域，電子科技類公司多數(shù)出現(xiàn)于信息產(chǎn)業(yè)領域，少部分則出現(xiàn)在電子電工領域。中標公司所出現(xiàn)的領域與公司自身的性質(zhì)相同，比如保潔服務公司只出現(xiàn)于專業(yè)服務領域。但有些公司可能出現(xiàn)于2個領域，比如電子科技類公司。

4 結(jié)束語

本文使用K近鄰分類算法對政府采購數(shù)據(jù)進行項目領域的研究分類，通過不斷地適配K值來得出較好分類結(jié)果，討論了變量在算法調(diào)優(yōu)中的重要作用。并且為今后針對政府采購數(shù)據(jù)各要素關聯(lián)性分析中應用K近鄰算法提供了途徑。

參考文獻

[1]全姣. 政府采購資金使用數(shù)據(jù)挖掘研究[D]. 重慶：重慶理工大學，2011.

[2] 陸旭. 文本挖掘中若干關鍵問題研究[M]. 合肥：中國科學技術大學出版社， 2008.

[3] 王仁武. Python與數(shù)據(jù)科學[M]. 上海：華東師范大學出版社， 2016.

[4] 李榮陸，胡運發(fā). 基于密度的kNN文本分類器訓練樣本裁剪方法[J]. 計算機研究與發(fā)展，2004，41（4）：539-545.

[5] 皮亞宸. K近鄰分類算法的應用研究[J]. 通訊世界，2019（1）：286-287.

[6] 萬如意. 大數(shù)據(jù)分析在政府采購領域中的應用：數(shù)據(jù)、技術與案例[J]. 中國政府采購，2015（12）：52-56.

[7]? 徐戈，王厚峰. 自然語言處理中主題模型的發(fā)展[J]. 計算機學報，2011，34（8）：1423-1436.

[8] 朱曉霞，宋嘉欣，孟建芳. 基于主題—情感挖掘模型的微博評論情感分類研究[J/OL]. 情報理論與實踐：1-11[2018-12-21]. https：//kns.cnki.net/kcms/detail/11.1762.G3.20181219.1124.006.html.

[9] 呂皓，周曉紀. 基于主題模型的技術預見文本分析[J]. 情報探索，2018（10）：52-59.

[10]葉凌箭，王朗，馬修水，等. 基于主元分析的最優(yōu)狀態(tài)檢測技術[J]. 計算機與應用化學，2014，31（1）：15-18.