基于聚類的內容分類方法范文

本站小編為你精心準備了基于聚類的內容分類方法參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

《電腦與信息技術雜志》2014年第三期

1基于改進的K-Means聚類算法的內容分類方法

1.1K-Means聚類算法K-Means算法首先選取初始聚類中心，然后對所有數據點進行分類，最后計算每個聚類的平均值，在每次循環中不斷的調整聚類中心，最終使類內對象相似性最大，類間對象相似性最小[7]。其具體的算法步驟有如下五步:（1）從數據樣本中隨機選取K個對象，作為初始聚類中心；（2）計算其他數據到初始聚類中心的距離，將其與距其最近的聚類中心劃為一類；（3）對于每一類，計算所有對象的均值，選取最接近均值的點為新的聚類中心；（4）重新對數據進行聚類；（5）若聚類中心及對象不再變化時，即達到最終聚類狀態時，結束。否則轉至第3步。傳統的K-Means算法對密集海量數據可以達到較好的效果[8]，但仍然具有以下三個問題：（1）算法中的K值為根據經驗值設定，忽略了實際數據本身的分部特點和聚類數目，有可能會導致最終聚類結果不準確；（2）傳統的K-Means算法中初始聚類中心為隨機選取，有可能會與實際聚類中心又較大偏差，最終導致聚類結果的隨機性和不穩定性；（3）由于采用迭代更新的方法，當初始聚類中心落在局部最小值附近時容易產生局部最優解。

1.2改進的K-Means算法針對傳統的K-Means算法的不足，本文針對K值以及初始聚類中心的選取作出改進，提出了一種改進的K-Means算法。本算法的主要思想是在選取K值時，首先對待聚類的樣本進行初步劃分，將其劃分的類數作為K，并在選取的類中以基于密度的方法選取密度最大的對象作為初始聚類中心，然后結合標準的K-Means算法，完成對聚類樣本的分類。具體來講，本算法主要分為兩個階段：第一階段為初始化階段，在此階段，通過計算類間平均距離的方法對樣本進行簡單劃分，將其初始化為K個初始類，并計算各類中每個對象的密度，選取密度最大的對象作為初始聚類中心；第二階段為標準的K-Means算法階段，在此階段采用標準的K-Means算法，使用第一階段產生的K值和初始聚類中心進行聚類劃分，最終得到完整的分類。為便于描述，本文采用二維空間模型對本文算法進行描述，其理論推演至多維模型與其類似。下面以二維空間的樣本分布模型為例闡述如何通過類間平均距離對樣本進行簡單劃分。在二維樣本空間X={x1，x2，x3…xn}中，記樣本xn的坐標為（xnx，xny），每一個樣本對象距離與其他對象的距離可以通過它們在X軸和Y軸的映射坐標來表示，如樣本x1與x2的橫向距離為|x1x-x2x|，縱向距離為|x1y-x2y|。因此，對于樣本空間X，其平均橫向類間樣本距離dx與平均縱向類間樣本距離dy分別為|xnx-x1x|（/p－1）與|yny-y1y|（/q－1），其中p為橫坐標不重復的樣本個數，q為縱坐標不重復的樣本個數，xnx、x1x為x軸方向距離最遠的兩個點的橫坐標，yny、y1y為y軸方向距離最遠的兩個點的縱坐標。具體的樣本劃分方法主要有以下幾步：（1）首先計算出樣本對象的平均橫向和縱向樣本距離dx、dy；（2）分別從橫向與縱向依次求出每兩個對象之間的樣本距離，若其樣本距離小于d<￡dx，則該對象應位于同一類別，其中￡為閾值，可用于調整樣本分類精度，￡應取1-2之間的任意值，￡值越小，分類精度越大；朱青等：基于聚類的內容分類方法的研究與應用分析•5•（3）對于橫向與縱向同時在二維空間中作出劃分之后，屬于同一劃分區域的類別即為初始化之后的類別。如圖1、圖2所示，其中圖1為初始樣本空間，圖2為劃分之后的樣本空間。如圖2所示，初始的9個樣本空間被初步劃分為3個區域，即3個類別。在對樣本進行劃分之后，K值已經確定，接下來在各個劃分區域通過計算每個樣本的密度來確定初始聚類中心。本文中通過如下方法計算樣本Xn的密度ρXn：（1）計算各類別中樣本的平均距離，即平均歐幾里得幾何距離，如計算樣本x1的平均歐幾里得幾何距離，其計算公式為d＝(d2+…+dt)（/t-1），其中t為該區域中樣本的個數，di為該樣本x1與所在區域中點xi的距離。2）以樣本的平均歐幾里得幾何距離為半徑，對于類中的每一個樣本畫圓，計算該圓中包括的樣本個數M；3）樣本Xn的密度ρXn即為以Xn為圓心，以d為半徑的圓中的樣本個數與圓的面積之比，即：ρXn=M/πd2。各類別種的樣本密度計算完畢之后，選取密度最大的樣本為各類別的初始聚類中心，之后利用標準K-Means算法進行聚類劃分，即可得到最終分類結果。

1.3基于改進K-Means算法的內容分類方法基于改進的K-Means算法，本文所提出的內容分類的方法的具體步驟有如下4步：（1）提取內容特征，采取向量空間模型來表示所要分類的內容，采用向量集合X表示所有內容；（2）對于內容集合X中的任一內容，采用如3.2節所描述的方法計算其樣本間距離，并進行初始劃分；（3）計算各個樣本類之中的樣本密度，使樣本密度最大的樣本為初始聚類中心；（4）以第2步和第3步計算出來的K值和初始聚類中心為參數，運行標準K-Means算法，對所有樣本進行分類。通過上述4個步驟，可以實現對內容的有效分類。

2內容分類方法的應用研究

內容分類作為內容管理的重要手段，可以應用在各個方面。本文針對內容管理的特點，結合聚類分析分類類別的無目標性，能夠有效組織內容管理系統中的數據，實現對數據處理的高效性，成為一種高效的內容管理和分類方法，可應用于多種場景。（1）在內容的展示方面，為了方便用戶對搜索結果的瀏覽，采用聚類算法對搜索結果文檔進行聚類，根據分組情況，輸出每個分組的描述信息，分類呈現給客戶[9]，使客戶縮小檢索范圍，快速定位到所感興趣的主題，同時為用戶的二次搜索提供信息。（2）在內容[10]方面，內容管理系統中的個性化設計[11]是其突出的特點，此內容管理方法在個性化方面不僅表現為可以使用戶自行定義操作界面，而且可以對不同用戶提供感興趣的內容推薦，提高用戶體驗。通過用戶提交興趣方向或者根據用戶的歷史訪問挖掘用戶的興趣。通過對用戶感興趣的文檔進行聚類分析，發現用戶的興趣，把用戶分為不同的興趣小組，根據用戶的興趣，把聚類后的文檔快速給相應興趣小組的用戶。（3）在新聞的方面，自動根據不同主題，通過聚類提供最近相關信息的自動匯編。便于用戶對同一主題信息的瀏覽，實現對新聞信息的歸類呈現和管理。（4）在對海量數據進行有效的管理方面，采用聚類分析算法，改善文檔分類結果，便于對文檔的歸類組織、管理、存儲。

3結論

本文針對傳統的K-Means算法的不足進行了相應的改進，提高了K值和初始聚類中心選擇的準確性，并在此基礎上提出了基于改進的K-Means聚類算法的內容分類方法。這種基于聚類算法的內容分類方法比傳統的基于固定分類的內容分類方法更能刻畫內容的具體特征，能夠實現對內容的有效分類組織，可以靈活的應用在包括內容、內容搜索和內容展示等各個方面，具有十分重要的研究意義。

作者：朱青牛志慧張曉凌單位：北京工業大學軟件學院