گام 1 - معرفی الگوریتم

معرفی الگوریتم

خوشه بندی و کلاسترینگ یک روش هوش مصنوعی برای حل مسائل است. از این روش می توان برای یادگیری نیز استفاده نمود. داده هایی که فاقد برچسب هستند یا داده هایی نامعلومی هستند را می توان با این روش شناسایی و دسته بندی نمود. بر اساس تعریف، کلاسترینگ یه روش برای ایجاد مجموعه های منتخب است که به صورت مفهومی و داخلی (محتوی آنها) با هم مرتبط هستند.

طبقه بندی

خوشه بندی یا همان کلاسترینگ به شکل های زیر قابل انجام است:

  1. کلاسترینگ مسطح  Flat clustering : ایجاد دسته ها بدون هیچ گونه ساختار صریح و مشخص انجام می گردد.
  2. کلاسترینگ یا خوشه بندی سلسله مراتبی Hierarchical clustering : ایجاد خوشه بندی سلسله مراتبی انجام میدهد.
  3. کلاسترینگ یا خوشه بندی سخت Hard clustering : هر سند را به صورت صریح به یک دسته مرتبط می کند.
  4. کلاسترینگ یا خوشه بندی نرم Soft clustering: اسناد را در تمام خوشه ها توزیع می کند.

الگوریتم های کلاسترینگ

  1. Agglomerative (Hierarchical clustering
  2. K-Means (Flat clustering, Hard clustering
  3. EM Algorithm (Flat clustering, Soft clustering
معرفی الگوریتم

الگوریتم K-Means به عنوان موثرترین روش در خوشه بندی مجمعه داده های بزرگ شناخته میشود که توسط مک کویین ابداع شده است.

در این قسمت الگوریتم پایه K-Means برای شما معرفی میگردد:

  1. مشخص کردن k به عنوان تعداد کلاسترهایی که باید تعیین شوند.
  2. انتخاب k عنصر تصادفی برای مجموع شروع
  3. قدم تکرار
  4. هر عنصر را به نزدیک ترین خوشه خود انتساب نمایید.
  5. کلاستر ها را محاسبه نمایید و نقطه میانی (mean point) را مشخص کنید.
  6. رفتن به قدم تکرار
  7. تغییری در نقاط مرکزی کلاستر ها ایجاد نکنید.
  8. هیچ عنصری کلاستر را تغییر نمیدهد.

گام 2 - کدنویسی

کد نویسی C# برای خوشه بندی اسناد متنی

ساخت کلاس ها و توابع مورد نیاز به زبان C# به شرح زیر میباشد.

 

public class DocumentVector
{
    //محتوی سند یا عنصری که قرار است خوشهبندی گردند
    public string Content { get; set; }
    // tf*idf برای هر سند
    public float[] VectorSpace { get; set; }
}

class DocumentCollection
{
    public  List<String> DocumentList { get; set; }
}
// محاسبه وزن TF-IDF 
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)
{
   //محاسبه تعداد تکرار واژه در تمام اسناد
   int count = documentCollection.ToArray().Where(s => r.Split(
       s.ToUpper()).ToArray().Contains(term.ToUpper())).Count();
   /*
    * لگاریتم تکرار واژه در اسناد
    * Math.Log(count/(1+documentCollection.Count)) از این رابطه نیز می توان استفاده نمود
    */
    return (float)Math.Log((float)documentCollection.Count() / (float)count);
}
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;
 }
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;

}
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);
  }
} 
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;
}

گام 3 - فایل و کد های پروژه

فایل و کد های پروژه

پروژه کلاسترینگ متنی

برای در یافت پروژه کلاسترینگ متنی کلیک نمایید: TextClustering