當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

文本分类与聚类(text categorization and clustering)

發布時間：2025/3/15 编程问答 34 豆豆

生活随笔收集整理的這篇文章主要介紹了文本分类与聚类(text categorization and clustering) 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

1. 概述

廣義的分類（classification或者categorization）有兩種含義：一種含義是有指導的學習（supervised learning）過程，另一種是無指導的學習（unsupervised learning）過程。通常前者稱為分類，后者稱為聚類（clustering），后文中提到的分類都是指有指導的學習過程。

給定分類體系，將文本集中的每個文本分到某個或者某幾個類別中，這個過程稱為文本分類（text categorization）。將文本集合分組成多個類或簇，使得在同一個簇中的文本內容具有較高的相似度，而不同簇中的文本內容差別較大，這個過程稱為文本聚類（text clustering）。

[Berry, 2003]詳細描述了文本挖掘技術。[Sebastiani, 2002]提供了對文本分類的綜述。[Xu & Wunsch, 2005]對聚類算法做了全面的描述，[He, 1999]則重點講述了聚類算法在IR中的應用。

2. 文本分類

文本分類過程可以分為手工分類和自動分類。前者最著名的實例是yahoo的網頁分類體系，是由專家定義了分類體系，然后人工將網頁分類。這種方法需要大量人力，現實中已經采用的很少了。自動文本分類（automatic text categorization）算法大致可以分為兩類：知識工程（knowledge engineering）方法和機器學習（machine learning）方法。知識工程方法指的是由專家為每個類別定義一些規則，這些規則代表了這個類別的特征，自動把符合規則的文檔劃分到相應的類別中。這方面最著名的系統是CONSTRUE。上個世紀90年代之后，機器學習方法成為主導。機器學習方法與知識工程方法相比，能夠達到相似的精確度，但是減少了大量的人工參與。我們下面主要介紹基于機器學習方法的文本分類。

2.1 文本分類的步驟

典型的文本分類過程可以分為三個步驟：

1. 文本表示（Text Representation）
這一過程的目的是把文本表示成分類器能夠處理的形式。最常用的方法是向量空間模型，即把文本集表示成詞－文檔矩陣，矩陣中每個元素代表了一個詞在相應文檔中的權重。選取哪些詞來代表一個文本，這個過程稱為特征選擇。常見的特征選擇方法有文檔頻率、信息增益、互信息、期望交叉熵等等，[Yang & Pedersen , 1997 ]對這幾種方法做了比較。為了降低分類過程中的計算量，常常還需要進行降維處理，比如LSI。
2. 分類器構建（Classifier Construction）
這一步驟的目的是選擇或設計構建分類器的方法。沒有一種通用的方法可以適用所有情況。不同的方法有各自的優缺點和適用條件，要根據問題的特點來選擇一個分類器。我們會在后面專門講述常用的方法。選定方法之后，在訓練集上為每個類別構建分類器，然后把分類器應用于測試集上，得到分類結果。
3. 效果評估（Classifier Evaluation）
在分類過程完成之后，需要對分類效果進行評估。評估過程應用于測試集（而不是訓練集）上的文本分類結果，常用的評估標準由IR領域繼承而來，包括查全率、查準率、F1值等等。對于某一類別i，查全率r_i=l_i/n_i，其中n_i為所有測試文檔中，屬于第i類的文檔個數；l_i是經分類系統輸出分類結果為第i類且結果正確的文檔個數。查準率p_i=l_i/m_i，其中m_i是經分類系統輸出分類結果為第i類的文檔個數，l_i是經分類系統輸出分類結果為第i類且結果正確的文檔個數。F1值為查全率和查準率的調和平均數，即：。
相對于最簡單的訓練集－測試集評估方法而言，還有一種稱為k-fold cross validation的方法，即把所有標記的數據劃分成k個子集，對于每個子集，把這個子集當作訓練集，把其余子集作為測試集；這樣執行k次，取各次評估結果的平均值作為最后的評估結果。

2.2 常見的文本分類方法

1. Rocchio方法
每一類確定一個中心點（centroid），計算待分類的文檔與各類代表元間的距離，并作為判定是否屬于該類的判據。Rocchio方法最早由[Hull, 1994]引入文本分類領域，后來又有很多文章進行了改進。Rocchio方法的特點是容易實現，效率高。缺點是受文本集分布的影響，比如計算出的中心點可能落在相應的類別之外[Sebastiani, 2002]。

2. 樸素貝葉斯（na?ve bayes）方法
將概率論模型應用于文檔自動分類，是一種簡單有效的分類方法。使用貝葉斯公式，通過先驗概率和類別的條件概率來估計文檔對某一類別的后驗概率，以此實現對此文檔所屬類別的判斷。[Lewis, 1998]介紹了樸素貝葉斯方法的發展和各種變體及特點。

3. K近鄰(K-Nearest Neightbers, KNN)方法
從訓練集中找出與待分類文檔最近的k個鄰居（文檔），根據這k個鄰居的類別來決定待分類文檔的類別。KNN方法的優點是不需要特征選取和訓練，很容易處理類別數目多的情況，缺點之一是空間復雜度高。KNN方法得到的分類器是非線性分類器。此方法最早由[Yang & Chute, 1994]提出。

4. 支持向量機（SVM）方法
對于某個類別，找出一個分類面，使得這個類別的正例和反例落在這個分類面的兩側，而且這個分類面滿足：到最近的正例和反例的距離相等，而且是所有分類面中與正例（或反例）距離最大的一個分類面。SVM方法最早由[Joachims, 1998]引入到文本分類中。SVM方法的優點是使用很少的訓練集，計算量小；缺點是太依賴于分類面附近的正例和反例的位置，具有較大的偏執。

其他常用的方法還包括決策樹方法和神經網絡方法，詳見文獻[Sebastiani, 2002]。

2.3 常用源碼和數據集

Weka是一個開源的機器學習軟件，集成了數據預處理、機器學習算法、可視化功能，實現了大部分常見的機器學習算法，包括分類。Weka是國外著名教材《Data Mining: Practical Machine Learning Tools and Techniques (Second Edition)》所采用的實驗平臺。

與Weka相競爭的另一個開源的機器學習軟件是Yale，自稱實現了Weka的所有算法，兼容Weka的數據格式。現在已經商業化。

與Weka和Yale不同，Bow是專門為文本處理設計的開源包。Bow包含三個部分：Rainbow（文本分類）、Arrow（文本檢索）和Crossbow（文本聚類）。

文本分類常用的數據集有REUTERS,20NEWSGROUP,OHSUMED等語料庫。

3. 文本聚類

文本聚類有很多應用，比如提高IR系統的查全率，導航/組織電子資源，等等。www.vivisimo.com是一個成熟的文本聚類系統。

根據聚成的簇的特點，聚類技術通常分為層次聚類（hierarchical clustering）和劃分聚類（partitional clustering）。前者比較典型的例子是凝聚層次聚類算法，后者的典型例子是k-means算法。近年來出現了一些新的聚類算法，它們基于不同的理論或技術，比如圖論，模糊集理論，神經網絡以及核技術（kernel techniques）等等。

3.1 文本聚類的步驟

與文本分類類似，文本聚類過程可以分為3個步驟：

1. 文本表示（Text Representation）
把文檔表示成聚類算法可以處理的形式。所采用的技術請參見文本分類部分。
2. 聚類算法選擇或設計（Clustering Algorithms）
算法的選擇，往往伴隨著相似度計算方法的選擇。在文本挖掘中，最常用的相似度計算方法是余弦相似度。聚類算法有很多種，但是沒有一個通用的算法可以解決所有的聚類問題。因此，需要認真研究要解決的問題的特點，以選擇合適的算法。后面會有對各種文本聚類算法的介紹。
3. 聚類評估（Clustering Evaluation）
因為沒有訓練文檔集合，所以評測聚類效果是比較困難的。常用的方法是：選擇人工已經分好類或者做好標記的文檔集合作為測試集合，聚類結束后，將聚類結果與已有的人工分類結果進行比較。常用評測指標也是查全率、查準率及F1值。

3.2 常見的文本聚類算法

1．層次聚類方法
層次聚類可以分為兩種：凝聚（agglomerative）層次聚類和劃分（divisive）層次聚類。凝聚方法把每個文本作為一個初始簇，經過不斷的合并過程，最后成為一個簇。劃分方法的過程正好與之相反。劃分方法在現實中采用較少，有關論述請見[Kaufman & Rousseeuw, 1990]。層次聚類可以得到層次化的聚類結果，但是計算復雜度比較高，不能處理大量的文檔。近年來出現了新的層次聚類算法，包括CURE[Guha, Rastogi & Shim, 1998], ROCK[Guha, Rastogi & Shim, 2000], Chameleon[Karypis, Han & V. Kumar, 1999]和BIRCH[Zhang, Ramakrishnan & Livny, 1996]。

2．劃分方法
k-means算法是最常見的劃分方法。給定簇的個數k，選定k個文本分別作為k個初始簇，將其他的文本加入最近的簇中，并更新簇的中心點，然后再根據新的中心點對文本重新劃分；當簇不再變化時或經過一定次數的迭代之后，算法停止。k-means算法復雜度低，而且容易實現，但是對例外和噪聲文本比較敏感。另外一個問題是，沒有一個好的辦法確定k的取值。相關文獻參見[Forgy, 1965][Xu & Wunsch, 2005]。

3．基于密度的方法
為了發現任意形狀的聚類結果，提出了基于密度的方法。這類方法將簇看作是數據空間中被低密度區域分割開的高密度區域。常見的基于密度的方法有DBSCAN, OPTICS, DENCLUE等等，參考文獻見[Han & Kamber, 2006]。

4．神經網絡方法
神經網絡方法將每個簇描述為一個標本，標本作為聚類的"原型"，不一定對應一個特定的數據,根據某些距離度量，新的對象被分配到與其最相似的簇中。比較著名的神經網絡聚類算法有:競爭學習（competitive learing）和自組織特征映射（self-organizing map）[Kohonen, 1990]。神經網絡的聚類方法需要較長的處理時間和復雜的數據復雜性，所以不適用于大型數據的聚類。

其他常見的方法包括基于圖論的聚類算法[Jain & Dubes, 1988]、基于核的聚類算法[Müller, Mika, R?tsch, et. al, 2001]、模糊聚類算法[H?ppner, Klawonn & Kruse, 1999]，等等。

3.3 常用的源碼包和數據集

前面介紹的Weka、Yale、Bow這三個工具已經包含了常用的聚類算法，下面再介紹幾個專門的聚類軟件：

Scipy: http://www.scipy.org/

The open source clustering softwares: http://bonsai.ims.u-tokyo.ac.jp/~mdehoon/software/cluster/software.htm

MICMOD: http://www-math.univ-fcomte.fr/mixmod/index.php

The Semantic Indexing Project: http://www.knowledgesearch.org/

JUNG: http://jung.sourceforge.net/

CompLearn: http://complearn.org/

目前還沒有專門為文本聚類設計的數據集，一般可以采用文本分類的數據集（前面有介紹）。

轉自：http://fusion.grids.cn/wiki/pages/viewpage.action?pageId=1033

參考文獻

[Berry, 2003]Michael W. Berry, "Survey of Text Mining：Clustering, Classification, and Retrieval", Springer, 2003
[Forgy, 1965] E. Forgy, "Cluster analysis of multivariate data: Efficiency vs. interpretability of classifications," Biometrics, vol. 21, 1965.
[Guha, Rastogi & Shim, 1998] S. Guha, R. Rastogi, and K. Shim, "CURE: An efficient clustering algorithm for large databases," in Proc. ACM SIGMOD Int. Conf. Management of Data, 1998, pp. 73-84.

[Guha, Rastogi & Shim, 2000]S. Guha, R. Rastogi, and K. Shim, "ROCK: A robust clustering algorithm for categorical attributes," Inf. Syst., vol. 25, no. 5, pp. 345-366, 2000.

[Han & Kamber, 2006] J Han, M Kamber, "Data Mining: Concepts and Techniques", version 2, 2006

[He, 1999] Q He,A review of clustering algorithms as applied in IR, Univ. Illinois at Urbana-Champaign, Tech. Rep. 1999

[H?ppner, Klawonn & Kruse, 1999] F. H?ppner, F. Klawonn, and R. Kruse, Fuzzy Cluster Analysis: Methods for Classification, Data Analysis, and Image Recognition. New York: Wiley, 1999.

[Hull, 1994] D. HULL, Improving text retrieval for the routing problem using latent semantic indexing. In Proceedings of SIGIR-94, 17th ACM International Conference on Research and Development in Information Retrieval (Dublin, Ireland, 1994), 282-289.

[Jain & Dubes, 1988] A. Jain and R. Dubes,? Algorithms for Clustering Data. Englewood Cliffs, NJ: Prentice-Hall, 1988.

[Joachims, 1998] T. Joachims, Text categorization with support vector machines: learning with many relevant features. In Proceedings of ECML-98, 10th European Conference on Machine Learning (Chemnitz, Germany, 1998), 137-142.

[Karypis, Han & V. Kumar, 1999] G. Karypis, E. Han, and V. Kumar, "Chameleon: Hierarchical clustering using dynamic modeling," IEEE Computer, vol. 32, no. 8, pp. 68-75, Aug. 1999.

[Kaufman & Rousseeuw, 1990]L. Kaufman and P. Rousseeuw, Finding Groups in Data: An Introductionto Cluster Analysis: Wiley, 1990.

[Kohonen, 1990]T. Kohonen, "The self-organizing map," Proc. IEEE, vol. 78, no. 9, pp. 1464-1480, Sep. 1990.

[Lewis, 1998] D.D.Lewis,? Naive (Bayes) at forty: The independence assumption in information retrieval. In Proceedings of ECML-98, 10^th European Conference on Machine Learning,1998

[Müller, Mika, R?tsch, et. al, 2001]K. Müller, S. Mika, G. R?tsch, K. Tsuda, and B. Sch?lkopf, "An introduction to kernel-based learning algorithms," IEEE Trans. Neural Netw.,vol. 12, no. 2, pp. 181-201, Mar. 2001.

[Sebastiani, 2002] F Sebastiani, "Machine learning in automated text categorization", ACM Computing Surveys (CSUR), 2002

[Steinbach, Karypis & Kumar, 2000]M Steinbach, G Karypis, V Kumar, "A comparison of document clustering techniques",? KDD Workshop on Text Mining, 2000

[Xu & Wunsch, 2005] R Xu, D Wunsch, Survey of clustering algorithms,? IEEE Transactions on Neural Networks, 2005

[Yang & Chute, 1994] Y. Yang, C. G. Chute. An example-based mapping method for text categorization and retrieval. ACM Trans. Inform. Syst. 12, 3, 252-277.

[Yang & Pedersen , 1997 ] Y. Yang, J.O.Pedersen. A Comparative Study on Feature Selection in Text Categorization Proceedings of the Fourteenth International Conference on Machine Learning (ICML'97), 1997.

[Zhang, Ramakrishnan & Livny, 1996]T. Zhang, R. Ramakrishnan, and M. Livny, "BIRCH: An efficient data clustering method for very large databases," in Proc. ACM SIGMOD Conf. Management of Data, 1996, pp. 103-114.

總結

以上是生活随笔為你收集整理的文本分类与聚类(text categorization and clustering)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。