改進的聚類分析算法在科研立項管理中的應用研究

姜丹 張曉雯 周麗

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

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

中圖分類號：TP391 文獻標識碼：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）

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

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

2 聚類分析技術（Clustering）

2.1 聚類分析概述

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

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

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

2.2 k-means聚類分析算法

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

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

算法的基本步驟包括：

（1）人為設定簇的個數k值。

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

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

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

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

（5）重復步驟（3）和步驟（4），直至簇的質心不再變化或達到終止條件為止。

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

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

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

3.1 基本思想

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

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

然后計算每個網格單元的密度和密度閥值，根據密度閥值區分高密度網格單元和低密度網格單元，密度閥值Minpt定義為：

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

再后將相鄰的高密度網格單元合并形成簇，稱為“中間聚類”，將低密度網格單元中的數據對象標記為“自由數據”。

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

3.2 算法流程

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

3.3 算法評價

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

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

綜上所述，理論分析及實驗證明了改進的算法優于傳統的k-means算法。

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

4.1 基本思想

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

4.2 基本流程

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

4.3 關鍵技術

（1）文本預處理

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

然后是詞性標記。文本當中有些詞性比如助詞、嘆詞等對文本表示不起決定性作用，反思卻對聚類結果產生影響，所以應該對分詞形成的詞進行詞性標記，在聚類前將其過濾掉，比較成熟的有中科院開發的ICTCLAS系統。

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

（2）文本的表示模型

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

其中，Ti代表某個特征項，Dj表示其所在的文本，TF（Ti，Dj）表示特征項Ti在文本Dj中出現的頻率，稱為詞頻，|D|表示集合中文本的總數目，|DF（Ti）|為包含特征項Ti的文本的數目，即文檔頻率。特征項Ti在文本Dj中出現的頻率（詞頻）越大，則該項對于文本Dj的內容越有代表性，并且在其他文本中出現的頻率（文檔頻率）越大，對文本Dj的內容越沒有代表性。

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

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

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

（3）文本的相似度計算

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

文本D1和D2之間的向量之間的內積公式為：

（4）簇的特征詞提取

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

4.4 系統模型設計

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

5 結論（Conclusion）

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

參考文獻（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] 羅可，李蓮，周博翔.一種蜜蜂交配優化聚類算法[J].電子學報，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] 姜丹，周麗，唐紅杰.聚類分析技術在教學指導中的應用研 究[J].湖北：軟件導刊，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-平均算法的文本聚類系統研究與實現[D].武漢理工大學，2009：10-12.

作者簡介：

姜 丹（1982-），女，碩士，講師.研究領域：數據挖掘.

張曉雯（1978-），女，碩士，講師.研究領域：數據庫系統.

周 麗（1981-），女，碩士，實驗師.研究領域：物理實驗教學.