改進(jìn)的聚類分析算法在科研立項管理中的應(yīng)用研究

姜丹 張曉雯 周麗

摘 要：針對目前的科研項目管理信息系統(tǒng)僅對科研項目進(jìn)行低水平管理，無法區(qū)分、甄別科研內(nèi)容等問題，對k-means聚類分析技術(shù)進(jìn)行改進(jìn)，并進(jìn)一步將該項技術(shù)應(yīng)用于科研立項管理中，通過對科研立項申報書進(jìn)行聚類分析，得出立項申請中相似的項目和創(chuàng)新的項目，為科研立項提供智能型的決策支持，避免了重復(fù)立項和重復(fù)研究，使得計算機應(yīng)用技術(shù)更好地服務(wù)于科研項目管理。

關(guān)鍵詞：聚類分析；k-means聚類算法；科研項目管理

中圖分類號：TP391 文獻(xiàn)標(biāo)識碼：A

文章編號：2096-1472（2016）-06-13-04

Abstract：For current low-level management of scientific research project information and incapability to distinguish or identify the contents of research projects，the paper improves the k-means clustering analysis technique，and further applies this technique into research project initialization management.Through clustering analysis of research project initialization declaration documents，decision-makers can find out the repetitive studies and the innovative projects.It intelligently supports the decision-making in project initialization by avoiding repetitive projects and studies，and makes it possible for computer application technology to better serve scientific research project management.

Keywords：clustering analysis；k-means clustering algorithm；scientific research project management

1 引言（Introduction）

隨著計算機應(yīng)用技術(shù)的飛速發(fā)展，計算機信息系統(tǒng)已經(jīng)滲透到人們生活、工作的各個方面，但是在科研管理中計算機信息系統(tǒng)的應(yīng)用程度還僅僅停留在對科研項目進(jìn)行查詢、刪除、維護(hù)等基本操作上。而實際應(yīng)用中，隨著科研項目數(shù)目的日益龐大，研究內(nèi)容的日益繁復(fù)，如何對科研項目的內(nèi)容進(jìn)行深度分析，以避免在科研中普遍存在的重復(fù)立項和低水平重復(fù)研究等問題，是對計算機信息系統(tǒng)提出的更高要求。

聚類分析技術(shù)是數(shù)據(jù)挖掘中最常用的工具，可以對大量數(shù)據(jù)進(jìn)行聚類，考察數(shù)據(jù)間的相似度或相異度。若將聚類分析技術(shù)應(yīng)用于科研項目管理的計算機信息系統(tǒng)中，在科研立項環(huán)節(jié)對立項申請書進(jìn)行聚類分析，找到眾多申請項目中的相似性項目和創(chuàng)新性項目，避免重復(fù)立項和重復(fù)研究，為科研項目管理系統(tǒng)提供科學(xué)的、合理的立項決策支持，使得科研項目管理信息系統(tǒng)更加智能、功能更加強大，是一個亟待研究的課題。

2 聚類分析技術(shù)（Clustering）

2.1 聚類分析概述

聚類分析技術(shù)是數(shù)據(jù)挖掘領(lǐng)域最為常見的技術(shù)之一，用于發(fā)現(xiàn)數(shù)據(jù)庫中未知的對象類，其核心是聚類[1]。所謂聚類即“物以類聚”，首先考察對象之間的相似度或相異度，然后將相似的對象劃分在同一個組內(nèi)，相異的對象劃分在不同的組內(nèi)，保證同一組內(nèi)的數(shù)據(jù)對象盡可能的相似，不同組內(nèi)的數(shù)據(jù)對象盡可能的相異，最終形成若干個類（或者簇）[2，3]。

聚類分析的定義如下：給定數(shù)據(jù)集合V{vi|i=1，2，…，n}，vi為數(shù)據(jù)對象，根據(jù)數(shù)據(jù)對象vi間的相似度或者相異度，將數(shù)據(jù)集合V{vi|i=1，2，…，n}分成k組Cj（j=1，2，…，k），并滿足：

該過程稱為聚類分析，Cj（j=1，2，…，k）稱為簇（類）[4，5]。

2.2 k-means聚類分析算法

聚類分析的方法有層次聚類方法、劃分聚類方法、基于密度的聚類方法、基于網(wǎng)格的聚類方法等。其中劃分聚類中k-means算法具有算法思想簡單、收斂速度快、可伸縮性好等優(yōu)點，應(yīng)用非常廣泛。

k-means聚類算法的基本思想是：以數(shù)據(jù)對象之間的歐式距離作為相似度或者相異度來考察數(shù)據(jù)對象，距離越近的數(shù)據(jù)對象其相似性就越大，距離越遠(yuǎn)的數(shù)據(jù)對象其相異度越大，相應(yīng)的簇是由離得近的數(shù)據(jù)對象組成。

算法的基本步驟包括：

（1）人為設(shè)定簇的個數(shù)k值。

（2）隨機選取k個對象作為這k個類的初始聚類中心。

（3）計算其他對象到k個初始聚類中心的距離，然后按照就近原則分配對象。

（4）根據(jù)公式1重新計算每個類的質(zhì)心，若給定簇Ki={ti1，ti2，…，tim}，則簇的質(zhì)心定義為：

其中，m代表簇Ki中數(shù)據(jù)對象的個數(shù)，代表第j個對象到簇Ki的聚類中心的距離[6]。

（5）重復(fù)步驟（3）和步驟（4），直至簇的質(zhì)心不再變化或達(dá)到終止條件為止。

k-means算法思想簡單，可伸縮性好，收斂速度快，適用于處理龐大的樣本數(shù)據(jù)。但從k-means聚類算法存在著比較顯著的缺點，其一，算法的第一步需人為設(shè)定簇的數(shù)目k，很顯然k值很難在聚類前估計，對聚類結(jié)果影響也比較大；其二，算法隨機選取k個初始聚類中心，一旦初始聚類中類中心選擇不當(dāng)，很難得到令人滿意的聚類結(jié)果。

3 改進(jìn)的k-means聚類分析算法（The improvement of clustering algorithm）

針對上述問題，引進(jìn)網(wǎng)格和密度兩個概念，提出一種改進(jìn)的聚類分析算法——GBKM算法。

3.1 基本思想

首先對樣本空間劃分網(wǎng)格單元，劃分方法為：設(shè)在第i維上數(shù)據(jù)空間取值范圍為（li，hi），i=1，2，…，n，采用公式（3）將其劃分為p個等長、不相交、左閉右開的區(qū)間。

數(shù)據(jù)空間被分割成pn個不相交的、大小相等的網(wǎng)格單元。第i維上的第j個網(wǎng)單元可由公式（4）得出。

然后計算每個網(wǎng)格單元的密度和密度閥值，根據(jù)密度閥值區(qū)分高密度網(wǎng)格單元和低密度網(wǎng)格單元，密度閥值Minpt定義為：

其中，Denc（Ci），i=1，2，…，n為網(wǎng)格單元的密度的降序排列，如果Denc（Ci）與Denc（Ci+1）發(fā)生明顯跳變，則N=i。

再后將相鄰的高密度網(wǎng)格單元合并形成簇，稱為“中間聚類”，將低密度網(wǎng)格單元中的數(shù)據(jù)對象標(biāo)記為“自由數(shù)據(jù)”。

最后處理自由數(shù)據(jù)，計算每個簇的質(zhì)心及自由數(shù)據(jù)到質(zhì)心的距離，將自由數(shù)據(jù)分配到最近的簇中，重復(fù)此過程，直到聚類中心不再移動為止完成聚類[7]。

3.2 算法流程

算法的基本流程如圖1所示。

3.3 算法評價

改進(jìn)的算法形成的初始聚類能夠很好地捕獲樣本數(shù)據(jù)的原始分布情況，可以自動確定聚類過程所需要的k值及k個初始聚類中心，克服了k-means聚類算法人為確定k值，以及隨機選擇初始聚類中心這兩大缺陷。

簇的純度pij定義為簇Ci與第j類交集的大小，簇的純度越高代表該算法的性能越好。使用Iris數(shù)據(jù)集進(jìn)行多次試驗，結(jié)果如表1所示。顯而易見，改進(jìn)的算法要明顯優(yōu)于傳統(tǒng)的k-means聚類分析算法。由于改進(jìn)的算法首先對高密度區(qū)域的數(shù)據(jù)進(jìn)行聚類，再對低密度區(qū)域的數(shù)據(jù)進(jìn)行聚類，聚類過程的迭代次數(shù)明顯減少，時間上更加高效。表2為五次的實驗結(jié)果，可以看出改進(jìn)的算法在聚類所需時間明顯小于傳統(tǒng)的k-means聚類算法。

綜上所述，理論分析及實驗證明了改進(jìn)的算法優(yōu)于傳統(tǒng)的k-means算法。

4 改進(jìn)聚類分析算法在科研立項管理中的應(yīng)用（The application of the improve clustering algorithm in the project management）

4.1 基本思想

將改進(jìn)的聚類分析算法應(yīng)用與科研立項管理的基本是：首先將科研立項申報書作為輸入，然后采用改進(jìn)的k-means聚類算法進(jìn)行聚類，然后對聚類結(jié)果進(jìn)行分析，將分析結(jié)果作為輸出，輸出包括兩方面的內(nèi)容：（1）創(chuàng)新性項目有哪些；（2）相似的項目有哪些。

4.2 基本流程

由于聚類的對象——科研立項申報書屬于中文文本，對中文文本的聚類與傳統(tǒng)的聚類有很大的區(qū)別，主要在于文本是一種非結(jié)構(gòu)化的數(shù)據(jù)，不能夠直接進(jìn)行聚類，必須經(jīng)過一系列的預(yù)處理生成文本集合之后才可以聚類，聚類結(jié)束后對簇分析時也需要進(jìn)行一系列的操作，所以對科研立項申報書進(jìn)行聚類的基本流程如圖2所示。

4.3 關(guān)鍵技術(shù)

（1）文本預(yù)處理

首先是分詞。所謂分詞就是把句子按照詞的含義劃分?；谧址ヅ涞姆衷~技術(shù)是目前最常用的分詞技術(shù)，也稱為機械分詞，首先按照一定的策略將待分析的字符串與詞庫中的詞條進(jìn)行匹配，直到找到一個詞匹配成功，否則重新匹配。

然后是詞性標(biāo)記。文本當(dāng)中有些詞性比如助詞、嘆詞等對文本表示不起決定性作用，反思卻對聚類結(jié)果產(chǎn)生影響，所以應(yīng)該對分詞形成的詞進(jìn)行詞性標(biāo)記，在聚類前將其過濾掉，比較成熟的有中科院開發(fā)的ICTCLAS系統(tǒng)。

接著是停用詞過濾。首先使用停用詞表，然后依次判斷文本中的詞是否停用，盡量減少文本的詞量，以減輕聚類算法的負(fù)擔(dān)，得到更優(yōu)的聚類結(jié)果。

（2）文本的表示模型

通過上面的處理，得到的特征詞語仍然數(shù)量龐大，很可能導(dǎo)致數(shù)據(jù)的維數(shù)過高，以至于無法聚類，所以需要進(jìn)一步對文本進(jìn)行特征選擇。主要的特征選擇方法有文檔頻率、單詞權(quán)、單詞熵、信息增益、互信息等，本文采取文檔頻率方法，該方法基于統(tǒng)計的思想，不但要考慮詞在文本中出現(xiàn)的頻率，還要考慮這個詞在文本集合中出現(xiàn)的頻率，文本集中有多少個文本包含了這個詞即文檔頻率越高，這個詞的對于所在文本的標(biāo)識能力就越弱，就越不重要，權(quán)重就應(yīng)該越低。特征項的權(quán)值采用經(jīng)典的TF-IDF方法來計算，特征Ti在文本Dj中的權(quán)重值的計算公式如下：

其中，Ti代表某個特征項，Dj表示其所在的文本，TF（Ti，Dj）表示特征項Ti在文本Dj中出現(xiàn)的頻率，稱為詞頻，|D|表示集合中文本的總數(shù)目，|DF（Ti）|為包含特征項Ti的文本的數(shù)目，即文檔頻率。特征項Ti在文本Dj中出現(xiàn)的頻率（詞頻）越大，則該項對于文本Dj的內(nèi)容越有代表性，并且在其他文本中出現(xiàn)的頻率（文檔頻率）越大，對文本Dj的內(nèi)容越?jīng)]有代表性。

文本作為非結(jié)構(gòu)化的數(shù)據(jù)必須轉(zhuǎn)化成計算機能夠識別的數(shù)學(xué)模型，文本表示的數(shù)學(xué)模型有布爾模型、概率檢索模型、向量空間模型等多種方法，本文采用向量空間模型，Vector Space Model，簡稱VSM模型[8]。

D（T1，T2，…，Tn）是文本D的特征項集合，Tk要求互異又不要求先后順序，Wk是特征項Tk的權(quán)值，表示該特征項在文本D中的重要程度，文本D可以表示成向量D（T1，W1；T2，W2；…；

Tn，Wn），稱為文本的特征向量，基本上可以完全代表文本的特性。

（3）文本的相似度計算

經(jīng)過上述步驟的處理，生成文本向量集后可以采取聚類算法進(jìn)行聚類，聚類過程需要衡量文本之間的相似度或者相異度。文本的相似度對于文本聚類有著直接且重要的影響，常用的度量方法有：歐氏距離、內(nèi)積距離、向量余弦距離，綜合考慮。本文采用向量內(nèi)積方法，內(nèi)積值越大，相似度就越大。

文本D1和D2之間的向量之間的內(nèi)積公式為：

（4）簇的特征詞提取

對于聚類后形成的文本簇，對其進(jìn)行特征詞提取，取得一些能夠代表該簇的特征項，用于標(biāo)識這個文本簇。簇的特征詞提取方法為在采用文本向量空間模型的基礎(chǔ)上，運用權(quán)重計算公式得出文本簇的向量矩陣，再進(jìn)一步對權(quán)重進(jìn)行排序，輸出權(quán)重最高的五個特征詞來代表該簇。

4.4 系統(tǒng)模型設(shè)計

科研立項管理信息系統(tǒng)主要分成文本預(yù)處理模塊、文本表示模塊、文本聚類模塊、簇特征分析模塊、立項決策輸出模塊等五大模塊，如圖3所示。文本預(yù)處理模塊主要是將科研立項書進(jìn)行分詞、詞性過濾、生成詞條集合。文本表示模塊主要對詞條集合進(jìn)行特征項選擇，特征項權(quán)值計算，構(gòu)建文本向量集合。文本聚類模塊采用改進(jìn)的聚類分析算法對前面生成的文本向量集合進(jìn)行聚類，生成聚類結(jié)果。簇特征分析模塊主要是對生成的簇進(jìn)行特征提取及分析，并通過立項決策支持輸出模塊將創(chuàng)新性項目和相似性項目進(jìn)行輸出。

5 結(jié)論（Conclusion）

本文將傳統(tǒng)的k-means聚類算法進(jìn)行改進(jìn)，并基于改進(jìn)的聚類算法進(jìn)一步研究中文文本聚類方法，在此基礎(chǔ)上設(shè)計了科研立項管理信息系統(tǒng)。該系統(tǒng)使用改進(jìn)的聚類算法對大量的科研立項申報書進(jìn)行文本聚類，并對聚類結(jié)果進(jìn)一步分析，從中發(fā)現(xiàn)相似的或創(chuàng)新性的項目，為科研立項提供了更加科學(xué)的、合理的決策支持，避免了科研中出現(xiàn)重復(fù)立項和低水平重復(fù)研究等問題。本文的研究成果不僅是對聚類分析技術(shù)的改進(jìn)，也是對計算機應(yīng)用技術(shù)的創(chuàng)新應(yīng)用，不僅具有較高的學(xué)術(shù)價值，還具有較高的經(jīng)濟(jì)價值和實用價值。

參考文獻(xiàn)（References）

[1] Hua Yuan，et al.From Trajectories to Path Network：An Endpoints-Based GPS Trajectory Partition and Clustering Framework（C）.The 15th International Conference on Web-Age Information Management （WAIM'2014），Macau，China，June 16-18，2014：740-743.

[2] Huaping Zhang，Ruiqi Zhang，Yanping Zhao.Big Data Modeling and Analysis of Microblog Ecosystem[J].International Journal of Automation and Computing，2014，11（2）：119-127.

[3] 羅可，李蓮，周博翔.一種蜜蜂交配優(yōu)化聚類算法[J].電子學(xué)報，2014（12）：145-149.

[4] Jiawei Han，Micheline Kamber.Data Mining：Concepts and Techniques（Second Edition）[M].San Francisco：Morgan Kaufmann Publisher，2006：383-385.

[5] Anil K.Jain，Richard C.Dubes.Algorithms for Clustering Data[M].New Jersey：Prentice Hall，2006：402-403.

[6] 姜丹，周麗，唐紅杰.聚類分析技術(shù)在教學(xué)指導(dǎo)中的應(yīng)用研 究[J].湖北：軟件導(dǎo)刊，2014，13（10）：135-138.

[7] Sushmita Mitra，Haider Banka.Collaborative Rough Clustering [J].Lecture Notes in Computer Science，2005，376（1）：768-773.

[8] 鄭韞旸.基于K-平均算法的文本聚類系統(tǒng)研究與實現(xiàn)[D].武漢理工大學(xué)，2009：10-12.

作者簡介：

姜 丹（1982-），女，碩士，講師.研究領(lǐng)域：數(shù)據(jù)挖掘.

張曉雯（1978-），女，碩士，講師.研究領(lǐng)域：數(shù)據(jù)庫系統(tǒng).

周 麗（1981-），女，碩士，實驗師.研究領(lǐng)域：物理實驗教學(xué).