姜丹 張曉雯 周麗

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

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

中圖分類號：TP391 文獻標(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)用程度還僅僅停留在對科研項目進行查詢、刪除、維護等基本操作上。而實際應(yīng)用中，隨著科研項目數(shù)目的日益龐大，研究內(nèi)容的日益繁復(fù)，如何對科研項目的內(nèi)容進行深度分析，以避免在科研中普遍存在的重復(fù)立項和低水平重復(fù)研究等問題，是對計算機信息系統(tǒng)提出的更高要求。

聚類分析技術(shù)是數(shù)據(jù)挖掘中最常用的工具，可以對大量數(shù)據(jù)進行聚類，考察數(shù)據(jù)間的相似度或相異度。若將聚類分析技術(shù)應(yīng)用于科研項目管理的計算機信息系統(tǒng)中，在科研立項環(huán)節(jié)對立項申請書進行聚類分析，找到眾多申請項目中的相似性項目和創(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ù)對象其相似性就越大，距離越遠的數(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ì)心不再變化或達到終止條件為止。

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

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

針對上述問題，引進網(wǎng)格和密度兩個概念，提出一種改進的聚類分析算法——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 算法評價

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

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

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

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

4.1 基本思想

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

4.2 基本流程

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

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

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

首先是分詞。所謂分詞就是把句子按照詞的含義劃分。基于字符串匹配的分詞技術(shù)是目前最常用的分詞技術(shù)，也稱為機械分詞，首先按照一定的策略將待分析的字符串與詞庫中的詞條進行匹配，直到找到一個詞匹配成功，否則重新匹配。

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

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

（2）文本的表示模型

通過上面的處理，得到的特征詞語仍然數(shù)量龐大，很可能導(dǎo)致數(shù)據(jù)的維數(shù)過高，以至于無法聚類，所以需要進一步對文本進行特征選擇。主要的特征選擇方法有文檔頻率、單詞權(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)過上述步驟的處理，生成文本向量集后可以采取聚類算法進行聚類，聚類過程需要衡量文本之間的相似度或者相異度。文本的相似度對于文本聚類有著直接且重要的影響，常用的度量方法有：歐氏距離、內(nèi)積距離、向量余弦距離，綜合考慮。本文采用向量內(nèi)積方法，內(nèi)積值越大，相似度就越大。

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

（4）簇的特征詞提取

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

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

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

5 結(jié)論（Conclusion）

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

參考文獻（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é).