2012年5月17日 星期四

全文檢索、資料採擷、推薦引擎系列6---基於KMean的文本自動演算法


對一系列文章進行自動聚類可以做為基於內容的推薦引擎的基礎，如果要實現文本的自動聚類，首先按照本系列5中所介紹的，對文章進行分詞，然後計算得出文章的術語向量表示，即求文章中每個不同的單詞以其所對應的TF*IDF，具體計算方法如5中所示。目前文本自動聚類演算法中，用得最多是KMean演算法，本文中就介紹KMean演算法的應用。當然，KMean演算法可以通過調用Mahout或WEKA這兩個開源的機器學習演算法庫來實現，但是在這類演算法中需要準備比較複雜的輸入檔，預處理過程比較複雜，還有一點，我們可能在實際應用中要對KMean演算法進行調整，這樣自己編寫KMean演算法重加有助於我們對文本聚類演算法的理解。
我們首先定義術語向量類，用來表示每篇文章的術語向量，還包括文檔編號和類別編號，具體代碼如下所示：
public class SepaTermVector {
 public SepaTermVector() {
  termVector = new Vector<TermInfo>();
 }
 public Vector<TermInfo> getTermVector() {
  return termVector;
 }
 public void setTermVector(Vector<TermInfo> termVector) {
  this.termVector = termVector;
 }
 public int getDocId() {
  return docId;
 }
 public void setDocId(int docId) {
  this.docId = docId;
 }
 public int getClusterId() {
  return clusterId;
 }
 public void setClusterId(int clusterId) {
  this.clusterId = clusterId;
 }

 /**
  * 在使用文章的術語向量時，我們不希望在自動聚類過程中破壞文章的術語向量，所以需要完體複
  * 制一份術語向量給自動聚類演算法
  */
 @Override
 public SepaTermVector clone() {
  SepaTermVector obj = new SepaTermVector();
  obj.setDocId(docId);
  obj.setClusterId(clusterId);
  Vector<TermInfo> vt = new Vector<TermInfo>();
  for (TermInfo item : termVector) {
   vt.add(item);
  }
  obj.setTermVector(vt);
  return obj;
 }
 private Vector<TermInfo> termVector = null; 
 private int docId = -1; // 所屬的文章編號
 private int clusterId = -1; // 所屬的聚類編號
}
然後我們定義文本聚類的類，在該類中保存聚類編號，聚類的中心（本身是該聚類中所有文章術語向量的一個並集）和聚類中所包含的術語向量（每個術語向量代表一篇文章）。代碼如下所示：
public class TextClusterInfo {
 public TextClusterInfo(int clusterId) {
  this.clusterId = clusterId;
  items = new Vector<SepaTermVector>(); // 考慮執行緒安全性而犧牲部分性能
 }

 public void addItem(SepaTermVector item) {
  items.add(item);
 }

 public void clearItems() {
  items.clear();
 }

 /**
  * 計算本類型的中心點
  */
 public void computeCenter() {
  if (items.size() <= 0) {
   return ;
  }
  for (SepaTermVector item : items) {
   if (null == center) {
    center = item;
   } else {
    center = DocTermVector.calCenterTermVector(item, center);
   }
  }
 }

 public int getClusterId() {
  return clusterId;
 }
 public void setClusterId(int clusterId) {
  this.clusterId = clusterId;
 }
 public SepaTermVector getCenter() {
  return center;
 }
 public void setCenter(SepaTermVector center) {
  this.center = center;
 }
 public List<SepaTermVector> getItems() {
  return items;
 }
 public void setItems(List<SepaTermVector> items) {
  this.items = items;
 }
 private int clusterId = 0;
 private SepaTermVector center = null;
 private List<SepaTermVector> items = null;
}
接下來就是KMean自動聚類演算法的工具類了，這裡需要注意的是標準KMean自動聚類演算法中，只需要指定初始的聚類數，然後由演算法自動隨機選擇聚類中心，然後進行反覆運算，最終找出自動聚類結果。為了降低演算法計算強度，我們在實際中不但給出了聚類數量，還給出了每個聚類的中心術語向量，即在大量文本中，找出每個聚類中的一篇代表性文章，作為參數傳給自動聚類演算法，在我們的實驗資料中，可以很快達到收斂的效果，並且準確性很高。
KMean算分為下列幾步：
  1. 根據所給出的聚類中心初始化聚類
  2. 清空每個聚類中屬於該聚類的術語向量列表
  3. 針對每篇文章的術語向量，求出與其最近的聚類，將該術語向量加入到該聚類，如果上次迴圈中求出的聚類和本次不同，則表明還需繼續運行聚類演算法
  4. 計算加入新術語向量後的聚類新的中心
  5. 判斷是否還需要運行自動聚類演算法，若需要則回到2
衡量術語向量與聚類的相似度採用點積形式，就是術語向量與聚類中心所代表的術語向量相同單詞權值之和，值越大代表二者越相像，具體代碼如下所示：

 public static double getDotProdTvs(SepaTermVector stv1, SepaTermVector stv2) {
  double dotProd = 0.0;
  Hashtable<String, Double> dict = new Hashtable<String, Double>();
  for (TermInfo info : stv2.getTermVector()) {
   dict.put(info.getTermStr(), info.getWeight());
  }
  for (TermInfo item : stv1.getTermVector()) {
   if (dict.get(item.getTermStr())!= null) {
    dotProd += item.getWeight() * dict.get(item.getTermStr()).doubleValue();
   }
  }
  return dotProd;
 }
下面KMean演算法實現類的代碼：
public class TextKMeanCluster {
 /**
  * 在通常情況下，我們需要將待分類文本分出大致的類別來，即確定numClusters。在有些情況下，還可以指定某個類別中
  * 的一篇文章。這樣可以避免演算法不收斂時聚類的品質問題。
  * @param docTermVectors 需要進行聚類的術語向量
  * @param numClusters 聚類數量
  */
 public TextKMeanCluster(List<SepaTermVector> docTermVectors, int numClusters) {
  this.docTermVectors = docTermVectors;
  this.numClusters = numClusters;
 }

 /**
  * 對文章進行聚類
  * @param initCenters 聚類的中心點
  * @return 聚類結果
  */
 public List<TextClusterInfo> cluster(List<SepaTermVector> initCenters) {
  if (docTermVectors.size() <= 0) {
   return null;
  }
  initClusters(initCenters);
  boolean hadReassign = true;
  int runTimes = 0;
  while ((runTimes<=MAX_KMEAN_RUNTIMES) && (hadReassign)) {
   System.out.println("runTimes=" + runTimes + "!");
   clearClusterItems();
   hadReassign = reassignClusters();
   computeClusterCenters();
   runTimes++;
  }
  return clusters;
 }

 /**
  * 本演算法中採用給定聚類中心的方式，但是在標準KMean演算法中是隨機選擇聚類中心的，隨機選擇收斂較慢。
  */
 public void initClusters(List<SepaTermVector> initCenters) {
  clusters = new Vector<TextClusterInfo>();
  TextClusterInfo cluster = null;
  int i = 0;
  for (SepaTermVector stv : initCenters) {
   cluster = new TextClusterInfo(i++);
   cluster.setCenter(stv);
   clusters.add(cluster);
  }
 }

 /**
  * 求出所有文章術語向量的新聚類，如果與上次求出的聚類不同，則表明需要繼續運行
  * @return 真時代表需要繼續運行自動聚類演算法
  */
 public boolean reassignClusters() {
  int numChanges = 0;
  TextClusterInfo newCluster = null;
  for (SepaTermVector termVector : docTermVectors) {
   newCluster = getClosetCluster(termVector);
   if ((termVector.getClusterId()<0) || termVector.getClusterId() != newCluster.getClusterId()) {
    numChanges++;
    termVector.setClusterId(newCluster.getClusterId());
   }
   newCluster.addItem(termVector);
   //System.out.println("reassignCluster:cid=" + newCluster.getClusterId() + ":size=" + 
     //newCluster.getItems().size());
  }
  return (numChanges>0);
 }

 /**
  * 求出加入新述語向量後聚類的新中心
  */
 public void computeClusterCenters() {
  for (TextClusterInfo cluster : clusters) {
   cluster.computeCenter();
  }
 }

 /**
  * 清除該聚類的術語向量列表
  */
 public void clearClusterItems() {
  for (TextClusterInfo cluster : clusters) {
   cluster.clearItems();
  }
 }

 /**
  * 在標準KMean演算法中隨機抽取聚類中心的演算法，在本類中該方法暫時未使用
  * @param usedIndex
  * @return
  */
 private SepaTermVector getTermVectorAtRandom(Hashtable<Integer, Integer> usedIndex) {
  boolean found = false;
  int index = -1;
  while (!found) {
   index = (int)Math.floor(Math.random() * docTermVectors.size());
   while (usedIndex.get(index) != null) {
    index = (int)Math.floor(Math.random() * docTermVectors.size());
   }
   usedIndex.put(index, index);
   return docTermVectors.get(index).clone(); // 重新複製一份，不破壞原來的拷貝
  }
  return null;
 }

 /**
  * 對術語向量和所有聚類中心所代表的術語向量做點積，取值最大的聚類為該文檔的聚類
  * @param termVector 術語向量
  * @return 與該術語向量最接近的聚類
  */
 private TextClusterInfo getClosetCluster(SepaTermVector termVector) {
  TextClusterInfo closetCluster = null;
  double dotProd = -1.0;
  double maxDotProd = -2.0;
  double dist = -1.0;
  double smallestDist = Double.MAX_VALUE;
  for (TextClusterInfo cluster : clusters) {
   //dist = DocTermVector.calTermVectorDist(cluster.getCenter(), termVector);
   dotProd = DocTermVector.getDotProdTvs(cluster.getCenter(), termVector);
   //System.out.println("getClosetCluster:dotProd=" + dotProd + "[" + maxDotProd + "] docId="
     //+ termVector.getDocId() + "!");
   //if (dist < smallestDist) {
   if (dotProd > maxDotProd) {
    //smallestDist = dist;
    maxDotProd = dotProd;
    closetCluster = cluster;
   }
  }
  return closetCluster;
 }

 public final static int MAX_KMEAN_RUNTIMES = 1000;

 private List<SepaTermVector> docTermVectors = null; // 所有文章的術語向量
 private List<SepaTermVector> centers = null;
 private List<TextClusterInfo> clusters = null; // 所有聚類
 private int numClusters = 0;
}
具體的調用方法如下所示：
DocTermVector.init();
  // 技術類
  int doc1Id = FteEngine.genTermVector(-1, "Java語言程式設計技術詳解", "", "", "", "");
  int doc2Id = FteEngine.genTermVector(-1, "C++語言程式設計指南", "", "", "", "");
  int doc4Id = FteEngine.genTermVector(-1, "Python程式設計教程", "", "", "", "");
  // 同性戀
  int doc3Id = FteEngine.genTermVector(-1, "同性戀網站變身電子商務網站", "", "", "", "");
  int doc5Id = FteEngine.genTermVector(-1, "同性戀網站大全", "", "", "", "");
  int doc6Id = FteEngine.genTermVector(-1, "男同性戀特點", "同性戀", "", "", "");
  // 天使投資
  int doc7Id = FteEngine.genTermVector(-1, "天使投資社交網路", "", "", "", "");
  int doc8Id = FteEngine.genTermVector(-1, "天使投資發展概況", "", "", "", "");
  int doc9Id = FteEngine.genTermVector(-1, "著名天使投資人和天使投資機構", "", "", "", "");
  // 環境保護
  int doc10Id = FteEngine.genTermVector(-1, "環境保護技術分析", "", "", "", "");
  int doc11Id = FteEngine.genTermVector(-1, "環境保護與碳關稅分析", "", "", "", "");
  int doc12Id = FteEngine.genTermVector(-1, "環境保護與我國經濟發展趨勢", "", "", "", "");
 
  FteEngine.genTermVector(-1, "VB程式設計指南", "", "", "", "");
  FteEngine.genTermVector(-1, "天使投資社區天使街正式上線運行", "", "", "", "");
  FteEngine.genTermVector(-1, "年度程式設計語言評選活動", "", "", "", "");
List<SepaTermVector> centers = new Vector<SepaTermVector>();
  centers.add(DocTermVector.getDocTermVector(0));
  centers.add(DocTermVector.getDocTermVector(3));
  centers.add(DocTermVector.getDocTermVector(6));
  centers.add(DocTermVector.getDocTermVector(9));
  TextKMeanCluster tkmc = new TextKMeanCluster(DocTermVector.getDocTermVectors(), 4);
  List<TextClusterInfo> rst = tkmc.cluster(centers);
  String lineStr = null;
  for (TextClusterInfo info : rst) {
   lineStr = "" + info.getClusterId() + "(" + info.getItems().size() + "):";
   for (SepaTermVector tvItem : info.getItems()) {
    lineStr += " " + tvItem.getDocId();
   }
   lineStr += "^_^";
   System.out.println(lineStr);
  }
運行的結果為：
0(5): 0 1 2 12 14^_^
1(3): 3 4 5^_^
2(4): 6 7 8 13^_^
3(3): 9 10 11^_^
由上面的結果來看，實現了基本正確的聚類。

張貼者： 於
標籤：

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)