65.9K
CodeProject 正在变化。 阅读更多。
Home

使用 K-Means 算法进行文本聚类

Samir Kunwar
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.92/5 (39投票s)

2012 年 8 月 14 日

CPOL

6分钟阅读

viewsIcon

296691

downloadIcon

15206

使用 K-Means 聚类算法的文本文档聚类。


引言

聚类可被视为最重要的无监督学习问题；因此，与所有此类问题一样，它处理的是在未标记数据集合中寻找结构。聚类的一个宽松定义可以是“将对象组织成组的过程，这些组的成员在某种程度上是相似的”。因此，一个簇是内部连贯，但与其他簇中的对象明显不同的对象集合。

在这种情况下，我们很容易识别出数据可以分为的 3 个簇；相似性准则是距离：如果两个或更多对象根据给定距离（在这种情况下是几何距离）“接近”，则它们属于同一个簇。这称为基于距离的聚类，这里我将处理的是基于距离的聚类。另一种聚类是概念聚类：如果两个或更多对象属于同一个簇，则该簇定义了一个对所有这些对象都通用的概念。换句话说，对象根据其对描述性概念的契合度进行分组，而不是根据简单的相似性度量进行分组。

分类

聚类算法可分类如下

  1. 扁平聚类（创建一组簇，它们之间没有明确的结构，这被称为独占聚类）
  2. 分层聚类（创建簇的层次结构）
  3. 硬聚类（将每个文档/对象精确地分配给一个簇）
  4. 软聚类（将文档/对象分布到所有簇中）
算法
  1. 聚合（分层聚类）
  2. K-Means（扁平聚类，硬聚类）
  3. EM 算法（扁平聚类，软聚类）

分层聚合聚类（HAC）和 K-Means 算法已直接应用于文本聚类。通常，它使用归一化的、TF-IDF 加权的向量和余弦相似度。在这里，我使用 n 维向量空间中的一组点来说明用于文本聚类的 k-means 算法。

K-Means 算法

k-means 聚类算法以高效聚类大型数据集而闻名。该聚类算法由 MacQueen 开发，是最简单且最著名的无监督学习算法之一，解决了众所周知的聚类问题。K-Means 算法旨在根据对象的属性/特征将其划分为 k 个簇，其中 k 是预定义或用户定义的常数。主要思想是定义 k 个质心，每个簇一个。簇的质心以这样一种方式形成：它与该簇中的所有对象密切相关（在相似性函数方面；相似性可以通过不同的方法测量，例如余弦相似性、欧几里得距离、扩展 Jaccard）。

基本 K-Means 算法

  1. 选择要确定的 k 个簇的数量
  2. 随机选择 k 个对象作为初始簇中心
  3. 重复  
3.1. 将每个对象分配给其最近的簇
3.2. 计算新簇，即计算平均点。 
    4. 直到 
        4.1. 簇中心没有变化（即质心不再改变位置）或
        4.2. 没有对象改变其簇（我们也可以定义停止标准） 

残差平方和

RSS 是衡量质心如何很好地代表其簇成员的指标，即每个向量与其质心的平方距离，对所有向量求和。

然后算法在空间中移动簇中心以最小化 RSS

终止条件

我们可以应用以下终止条件之一。

  • 已完成固定数量的迭代 I。此条件限制了聚类算法的运行时间，但在某些情况下，由于迭代次数不足，聚类质量会很差。
  • 迭代之间文档到簇的分配没有变化。除了局部最小值不佳的情况外，这会产生良好的聚类，但运行时间可能过长。
  • 质心在迭代之间没有变化。这相当于当 RSS 低于阈值时不停。此标准确保聚类在终止后具有所需的质量。实际上，我们需要将其与迭代次数的限制相结合，以保证终止。
  • 当 RSS 的下降低于阈值 t 时终止。对于小的 t，这表明我们接近收敛。同样，我们需要将其与迭代次数的限制相结合，以防止运行时间过长。

初始种子选择不当

在 K-Means 算法中，不幸的是无法保证达到目标函数的全局最小值，如果文档集包含许多异常值（与其他任何文档都相距甚远，因此不适合任何簇的文档），这是一个特殊问题。通常，如果将异常值选为初始种子，则在后续迭代中不会将其他向量分配给它。因此，我们最终会得到一个单例簇（只有一个文档的簇），即使可能存在一个 RSS 更低的聚类。

有效的种子选择启发式方法包括

  1. 从种子集中排除异常值
  2. 尝试多个起始点并选择成本最低的聚类；以及
  3. 从其他方法（如分层聚类）获取种子。

深入代码

文档表示

使用向量空间模型将每个文档表示为一个向量。向量空间模型也称为词向量模型，是一种将文本文档（或一般而言的任何对象）表示为标识符向量的代数模型。例如，TF-IDF 权重。

这里我定义了 DocumentVector 类，其实例包含文档及其在向量空间中的相应表示。

public class DocumentVector
{
    //Content represents the document(or any other object) to be clustered
    public string Content { get; set; }
    //represents the tf*idf of  each document
    public float[] VectorSpace { get; set; }
}

DocumentCollection 的实例表示所有要聚类的文档

class DocumentCollection
{
    public  List<String> DocumentList { get; set; }
}
TF-IDF

TF-IDF 代表词频-逆文档频率，是一种数值统计量，反映了单词在集合或语料库中对文档的重要性，它是向量空间模型中用于描述文档最常见的加权方法，特别是在信息检索问题中。

一个词在文档中出现的次数称为其词频。我们可以将一个词的词频计算为该词在文档中出现的次数与文档中总词数的比率。

逆文档频率衡量该词在所有文档中是常见还是罕见。它通过将文档总数除以包含该词的文档数，然后取该商的对数来获得。

文档 d 中词 t 的 tf*idf 计算如下

//Calculates TF-IDF weight for each term t in document d
private static float FindTFIDF(string document, string term)
{
   float tf = FindTermFrequency(document, term);
   float idf = FindInverseDocumentFrequency(term);
   return tf * idf;
}
 
private static float FindTermFrequency(string document, string term)
{
   int count = r.Split(document).Where(s => s.ToUpper() == term.ToUpper()).Count();
   //ratio of no of occurance of term t in document d to the total no of terms in the document
   return (float)((float)count / (float)(r.Split(document).Count()));
}
 
private static float FindInverseDocumentFrequency(string term)
{
   //find the  no. of document that contains the term in whole document collection
   int count = documentCollection.ToArray().Where(s => r.Split(
       s.ToUpper()).ToArray().Contains(term.ToUpper())).Count();
   /*
    * log of the ratio of  total no of document in the collection to the no. of document containing the term
    * we can also use Math.Log(count/(1+documentCollection.Count)) to deal with divide by zero case; 
    */
    return (float)Math.Log((float)documentCollection.Count() / (float)count);
}
查找相似度分数

我使用余弦相似度来识别文档的相似度分数。方法 FindCosineSimilarity 接受两个参数 vecA 和 vecB，它们是文档 A 和 B 的向量表示，并返回介于 1 和 0 之间的相似度分数，分别表示文档 A 和 B 完全相似和不相似。

 public static float FindCosineSimilarity(float[] vecA, float[] vecB)
 {
       var dotProduct = DotProduct(vecA, vecB);
       var magnitudeOfA = Magnitude(vecA);
       var magnitudeOfB = Magnitude(vecB);
       float result = dotProduct / (magnitudeOfA * magnitudeOfB);
       //when 0 is divided by 0 it shows result NaN so return 0 in such case.
       if (float.IsNaN(result))
           return 0;
        else
           return (float)result;
  }
K-Means 算法实现

为了实现 K-Means 算法，我定义了一个 Centroid 类，在聚类过程中文档被分配到其中。

public class Centroid
{
    public List<DocumentVector> GroupedDocument { get; set; }
}
准备文档簇 
public static List<Centroid> PrepareDocumentCluster(int k, 
          List<DocumentVector> documentCollection,ref int _counter)
{
   globalCounter = 0;
   //prepares k initial centroid and assign one object randomly to each centroid
   List<Centroid> centroidCollection = new List<Centroid>();
   Centroid c;
        
   /*
    * Avoid repeation of random number, if same no is generated 
    * more than once same document is added to the next cluster 
    * so avoid it using HasSet collection
    */
    HashSet<int> uniqRand = new HashSet<int>();
    GenerateRandomNumber(ref uniqRand,k,documentCollection.Count);
        
    foreach(int pos in uniqRand) 
    {
        c = new Centroid();                
        c.GroupedDocument = new List<DocumentVector>();
        c.GroupedDocument.Add(documentCollection[pos]);
        centroidCollection.Add(c);                
    }

    Boolean stoppingCriteria;
    List<Centroid> resultSet;
    List<Centroid> prevClusterCenter;
        
    InitializeClusterCentroid(out resultSet, centroidCollection.Count);

    do
    {
         prevClusterCenter = centroidCollection;

         foreach (DocumentVector obj in documentCollection)
         {
             int index = FindClosestClusterCenter(centroidCollection, obj);
             resultSet[index].GroupedDocument.Add(obj);
         }
         InitializeClusterCentroid(out centroidCollection, centroidCollection.Count());
         centroidCollection = CalculateMeanPoints(resultSet);
         stoppingCriteria = CheckStoppingCriteria(prevClusterCenter, centroidCollection);
         if (!stoppingCriteria)
         {   
             //initialize the result set for next iteration
              InitializeClusterCentroid(out resultSet, centroidCollection.Count);
         }

    } while (stoppingCriteria == false);

    _counter = counter;
    return resultSet;

}
初始化簇中心

为下一次迭代初始化簇中心，这里 count 变量保存用户定义的初始簇中心的值。

private static void InitializeClusterCentroid(out List<Centroid> centroid,int count)
{
  Centroid c;
  centroid = new List<Centroid>();
  for (int i = 0; i < count; i++)
  {
       c = new Centroid();
       c.GroupedDocument = new List<DocumentVector>();
       centroid.Add(c);
  }
}
查找最近的簇中心

此函数返回每个文档最近簇中心的索引，我使用余弦相似度来识别文档的接近度。数组 similarityMeasure 包含文档 obj 与每个簇中心的相似度分数，具有最大分数的索引被视为给定文档的最近簇中心。

private static int FindClosestClusterCenter(List<Centroid> clusterCenter,DocumentVector obj)
{
  float[] similarityMeasure = new float[clusterCenter.Count()];

  for (int i = 0; i < clusterCenter.Count(); i++)
  {
       similarityMeasure[i] = 
         SimilarityMatrics.FindCosineSimilarity(
         clusterCenter[i].GroupedDocument[0].VectorSpace, obj.VectorSpace); 
  }

  int index = 0;
  float maxValue = similarityMeasure[0];
  for (int i = 0; i < similarityMeasure.Count(); i++)
  {
       //if document is similar assign the document
       //to the lowest index cluster center to avoid the long loop
       if (similarityMeasure[i] >maxValue)
       {
           maxValue = similarityMeasure[i];
           index = i;
       }
   }
   return index;
}
确定簇中心的新位置

在将每个文档分配给其最近的簇中心后，我们重新计算每个簇中心的均值，这表示簇中心（质心）的新位置。

private static List<Centroid> CalculateMeanPoints(List<Centroid> _clusterCenter)
{
 for (int i = 0; i < _clusterCenter.Count(); i++)
 {
      if (_clusterCenter[i].GroupedDocument.Count() > 0)
      {
         for (int j = 0; j < _clusterCenter[i].GroupedDocument[0].VectorSpace.Count(); j++)
         {
              float total = 0;
                    
              foreach (DocumentVector vSpace in _clusterCenter[i].GroupedDocument)
              {
                   total += vSpace.VectorSpace[j];
              }
              //reassign new calculated mean on each cluster center,
              //It indicates the reposition of centroid
              _clusterCenter[i].GroupedDocument[0].VectorSpace[j] = 
                                  total / _clusterCenter[i].GroupedDocument.Count();
          }
      }
  }
  return _clusterCenter;
}
© . All rights reserved.