青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

chenglong7997

教你文本聚類(轉)

教你文本聚類

2009-08-23 18:32 189人閱讀 評論(0) 收藏 舉報

摘 要:文本聚類是搜索引擎和語義web的基本技術,這次本蛙和大家一起學習一下簡單的文本聚類算法,可能不能直接用于實際應用中,但對于想學搜索技術的初學 者還是有一定入門作用的。這里會用到TF/IDF權重,用余弦夾角計算文本相似度,用方差計算兩個數據間歐式距離,用k-means進行數據聚類等數學和 統計知識。關于這些概念可以去google,或者參考文本后的參考鏈接。

思路:計算兩篇文檔的相似度,最簡單的做法就是用提取文檔的TF/IDF權重,然后用余弦定理計算兩個多維向量的距離。能計算兩個文本間的距離后,用標準的k-means算法就可以實現文本聚類了。

測試:首先我們準備以下數據
===================
奧運 拳擊 入場券 基本 分罄 鄒市明 奪冠 對手 浮出 水面
股民 要 清楚 自己 的 目的
印花稅 之 股民 四季
杭州 股民 放 鞭炮 慶祝 印花稅 下調 
殘疾 女 青年 入圍 奧運 游泳 比賽 創 奧運 歷史 兩 項 第一
介紹 一 個 ASP.net MVC 系列 教程
在 asp.net 中 實現 觀察者 模式 ,或 有 更 好 的 方法 (續)
輸 大錢 的 股民 給 我們 啟迪
Asp.Net 頁面 執行 流程 分析
運動員 行李 將 “后 上 先 下” 奧運 相關 人員 行李 實名制
asp.net 控件 開發 顯示 控件 內容
奧運 票務 網上 成功 訂票 后 應 及時 到 銀行 代售 網點 付款
某 心理 健康 站 開張 后 首 個 咨詢 者 是 位 新 股民
ASP.NET 自定義 控件 復雜 屬性 聲明 持久性 淺析
==================
很明顯以上數據可以分為三類:asp.net,奧運和股民,我們就寫程序來實現它,各種算法的原理網上都有,我就大概只貼代碼,聲明一下,部分代碼是從網 上直接抄的,k-means代碼是我從一篇文章的java示例代碼轉換過來的,我給代碼加了不少注釋,希望能幫助大家理解。

以下是入口函數

 static   void  Main( string [] args)
 
{
     
 // 1、獲取文檔輸入 
 
     string [] docs  =  getInputDocs( " input.txt " );
     
 if  (docs.Length  <   1 )
     
 {
         Console.WriteLine(
 " 沒有文檔輸入 " );
         Console.Read();
         
 return ;
     }
 

 
     
 // 2、初始化TFIDF測量器,用來生產每個文檔的TFIDF權重 
 
    TFIDFMeasure tf  =   new  TFIDFMeasure(docs,  new  Tokeniser());
 
     
 int  K  =   3  // 聚成3個聚類
 
     
 // 3、生成k-means的輸入數據,是一個聯合數組,第一維表示文檔個數,
     
 // 第二維表示所有文檔分出來的所有詞 
 
     double [][] data  =   new   double [docs.Length][];
     
 int  docCount  =  docs.Length;  // 文檔個數 
 
     int  dimension  =  tf.NumTerms; // 所有詞的數目 
 
     for  ( int  i  =   0 ; i  <  docCount; i ++ )
     
 {
         
 for  ( int  j  =   0 ; j  <  dimension; j ++ )
         
 {
             data[i] 
 =  tf.GetTermVector2(i);  // 獲取第i個文檔的TFIDF權重向量 
 
        } 

     }
 

 
     
 // 4、初始化k-means算法,第一個參數表示輸入數據,第二個參數表示要聚成幾個類 
 
    WawaKMeans kmeans  =   new  WawaKMeans(data, K);
     
 // 5、開始迭代 
 
    kmeans.Start();
 
     
 // 6、獲取聚類結果并輸出 
 
    WawaCluster[] clusters  =  kmeans.Clusters;
     
 foreach  (WawaCluster cluster  in  clusters)
     
 {
         List
 < int >  members  =  cluster.CurrentMembership;
         Console.WriteLine(
 " ----------------- " );
         
 foreach  ( int  i  in  members)
         
 {
             Console.WriteLine(docs[i]);
         }
 

 
     }
 

     Console.Read();
 }
 

 


以下是分詞器的主要代碼

 ///   <summary> 
 
///  以空白字符進行簡單分詞,并忽略大小寫,
 
///  實際情況中可以用其它中文分詞算法
 
///   </summary> 
 
///   <param name="input"></param> 
 
///   <returns></returns> 

 public  IList < string >  Partition( string  input)
 
{
  Regex r
 = new  Regex( " ([ //t{}():;. /n]) " );  
  input
 = input.ToLower() ;
 
  String [] tokens
 = r.Split(input);          
 
  List
 < string >  filter = new   List < string > () ;
 
  
 for  ( int  i = 0 ; i  <  tokens.Length ; i ++ )
  
 {
   MatchCollection mc
 = r.Matches(tokens[i]);
   
 if  (mc.Count  <=   0   &&  tokens[i].Trim().Length  >   0        
    
 &&   ! StopWordsHandler.IsStopword (tokens[i]) )        
    filter.Add(tokens[i]) ;
         }
 

  
  
 return  filter.ToArray();
 }
 

 


以下是kmeans算法的基本代碼

 public   class  WawaKMeans
 
{
     
 ///   <summary> 
     
 ///  數據的數量
     
 ///   </summary> 

      readonly   int  _coordCount;
     
 ///   <summary> 
     
 ///  原始數據
     
 ///   </summary> 

      readonly   double [][] _coordinates;
     
 ///   <summary> 
     
 ///  聚類的數量
     
 ///   </summary> 

      readonly   int  _k;
     
 ///   <summary> 
     
 ///  聚類
     
 ///   </summary> 

      private   readonly  WawaCluster[] _clusters;
 
     
 internal  WawaCluster[] Clusters
     
 {
         
 get    return  _clusters; } 
     }
 
 
 
     
 ///   <summary> 
     
 ///  定義一個變量用于記錄和跟蹤每個資料點屬于哪個群聚類
     
 ///  _clusterAssignments[j]=i;// 表示第 j 個資料點對象屬于第 i 個群聚類
     
 ///   </summary> 

      readonly   int [] _clusterAssignments;
     
 ///   <summary> 
     
 ///  定義一個變量用于記錄和跟蹤每個資料點離聚類最近
     
 ///   </summary> 

      private   readonly   int [] _nearestCluster;
     
 ///   <summary> 
     
 ///  定義一個變量,來表示資料點到中心點的距離,
     
 ///  其中—_distanceCache[i][j]表示第i個資料點到第j個群聚對象中心點的距離;
     
 ///   </summary> 

      private   readonly   double [,] _distanceCache;
     
 ///   <summary> 
     
 ///  用來初始化的隨機種子
     
 ///   </summary> 

      private   static   readonly  Random _rnd  =   new  Random( 1 );
 
     
 public  WawaKMeans( double [][] data,  int  K)
     
 {
         _coordinates 
 =  data;
         _coordCount 
 =  data.Length;
         _k 
 =  K;
         _clusters 
 =   new  WawaCluster[K];
         _clusterAssignments 
 =   new   int [_coordCount];
         _nearestCluster 
 =   new   int [_coordCount];
         _distanceCache 
 =   new   double [_coordCount,data.Length];
         InitRandom();
     }
 

 
     
 public   void  Start()
     
 {
         
 int  iter  =   0 ;
         
 while  ( true )
         
 {
             Console.WriteLine(
 " Iteration  "   +  (iter ++  +   "  " );
             
 // 1、重新計算每個聚類的均值 
 
             for  ( int  i  =   0 ; i  <  _k; i ++ )
             
 {
                 _clusters[i].UpdateMean(_coordinates);
             }
 

 
             
 // 2、計算每個數據和每個聚類中心的距離 
 
             for  ( int  i  =   0 ; i  <  _coordCount; i ++ )
             
 {
                 
 for  ( int  j  =   0 ; j  <  _k; j ++ )
                 
 {
                     
 double  dist  =  getDistance(_coordinates[i], _clusters[j].Mean);
                     _distanceCache[i,j] 
 =  dist;
                 }
 

             }
 

 
             
 // 3、計算每個數據離哪個聚類最近 
 
             for  ( int  i  =   0 ; i  <  _coordCount; i ++ )
             
 {
                 _nearestCluster[i] 
 =  nearestCluster(i);
             }
 

 
             
 // 4、比較每個數據最近的聚類是否就是它所屬的聚類
             
 // 如果全相等表示所有的點已經是最佳距離了,直接返回; 
 
             int  k  =   0 ;
             
 for  ( int  i  =   0 ; i  <  _coordCount; i ++ )
             
 {
                 
 if  (_nearestCluster[i]  ==  _clusterAssignments[i])
                     k
 ++ ;
 
             }
 

             
 if  (k  ==  _coordCount)
                 
 break ;
 
             
 // 5、否則需要重新調整資料點和群聚類的關系,調整完畢后再重新開始循環;
             
 // 需要修改每個聚類的成員和表示某個數據屬于哪個聚類的變量 
 
             for  ( int  j  =   0 ; j  <  _k; j ++ )
             
 {
                 _clusters[j].CurrentMembership.Clear();
             }
 

             
 for  ( int  i  =   0 ; i  <  _coordCount; i ++ )
             
 {
                 _clusters[_nearestCluster[i]].CurrentMembership.Add(i);
                 _clusterAssignments[i] 
 =  _nearestCluster[i];
             }
 

             
         }
 

 
     }
 

 
     
 ///   <summary> 
     
 ///  計算某個數據離哪個聚類最近
     
 ///   </summary> 
     
 ///   <param name="ndx"></param> 
     
 ///   <returns></returns> 

      int  nearestCluster( int  ndx)
     
 {
         
 int  nearest  =   - 1 ;
         
 double  min  =  Double.MaxValue;
         
 for  ( int  c  =   0 ; c  <  _k; c ++ )
         
 {
             
 double  d  =  _distanceCache[ndx,c];
             
 if  (d  <  min)
             
 {
                 min 
 =  d;
                 nearest 
 =  c;
             }
 

       
         }
 

         
 if (nearest ==- 1 )
         
 {
             ;
         }
 

         
 return  nearest;
     }
 

     
 ///   <summary> 
     
 ///  計算某數據離某聚類中心的距離
     
 ///   </summary> 
     
 ///   <param name="coord"></param> 
     
 ///   <param name="center"></param> 
     
 ///   <returns></returns> 

      static   double  getDistance( double [] coord,  double [] center)
     
 {
         
 // int len = coord.Length;
         
 // double sumSquared = 0.0;
         
 // for (int i = 0; i < len; i++)
         
 // {
         
 //     double v = coord[i] - center[i];
         
 //     sumSquared += v * v;  // 平方差
         
 // }
         
 // return Math.Sqrt(sumSquared);
 
         
 // 也可以用余弦夾角來計算某數據離某聚類中心的距離 
 
         return   1 -  TermVector.ComputeCosineSimilarity(coord, center);
 
     }
 
 
     
 ///   <summary> 
     
 ///  隨機初始化k個聚類
     
 ///   </summary> 

      private   void  InitRandom()
     
 {
         
 for  ( int  i  =   0 ; i  <  _k; i ++ )
         
 {
             
 int  temp  =  _rnd.Next(_coordCount);
             _clusterAssignments[temp] 
 =  i;  // 記錄第temp個資料屬于第i個聚類 
 
            _clusters[i]  =   new  WawaCluster(temp,_coordinates[temp]);
         }
 

     }
 

 }
 

 


以下是聚類實體類的定義

 internal   class  WawaCluster
 
{
     
 public  WawaCluster( int  dataindex, double [] data)
     
 {
         CurrentMembership.Add(dataindex);
         Mean 
 =  data;
     }
 

 
     
 ///   <summary> 
     
 ///  該聚類的數據成員索引
     
 ///   </summary> 

      internal  List < int >  CurrentMembership  =   new  List < int > ();
     
 ///   <summary> 
     
 ///  該聚類的中心
     
 ///   </summary> 

      internal   double [] Mean;
     
 ///   <summary> 
     
 ///  該方法計算聚類對象的均值 
     
 ///   </summary> 
     
 ///   <param name="coordinates"></param> 

      public   void  UpdateMean( double [][] coordinates)
     
 {
         
 //  根據 mCurrentMembership 取得原始資料點對象 coord ,該對象是 coordinates 的一個子集;
         
 // 然后取出該子集的均值;取均值的算法很簡單,可以把 coordinates 想象成一個 m*n 的距陣 ,
         
 // 每個均值就是每個縱向列的取和平均值 ,  // 該值保存在 mCenter 中 
 

         
 for  ( int  i  =   0 ; i  <  CurrentMembership.Count; i ++ )
         
 {
             
 double [] coord  =  coordinates[CurrentMembership[i]];
             
 for  ( int  j  =   0 ; j  <  coord.Length; j ++ )
             
 {
                 Mean[j] 
 +=  coord[j];  //  得到每個縱向列的和; 
 
            } 

             
 for  ( int  k  =   0 ; k  <  Mean.Length; k ++ )
             
 {
                 Mean[k] 
 /=  coord.Length;  //  對每個縱向列取平均值 
 
            } 

         }
 

     }
 

 }
 

 


計算TF/IDF和利用余弦定理計算相似度的代碼見完整版的代碼下載,那兩部分都是外國人寫的,里面有它的聯系方式,不懂的可以問他,反正我差不多懂了。

下面看看咱們的測試結果:
Iteration 0...
Iteration 1...
Iteration 2...
-----------------
奧運 拳擊 入場券 基本 分罄 鄒市明 奪冠 對手 浮出 水面
杭州 股民 放 鞭炮 慶祝 印花稅 下調
殘疾 女 青年 入圍 奧運 游泳 比賽 創 奧運 歷史 兩 項 第一
運動員 行李 將 “后 上 先 下” 奧運 相關 人員 行李 實名制
奧運 票務 網上 成功 訂票 后 應 及時 到 銀行 代售 網點 付款
-----------------
股民 要 清楚 自己 的 目的
印花稅 之 股民 四季
輸 大錢 的 股民 給 我們 啟迪
某 心理 健康 站 開張 后 首 個 咨詢 者 是 位 新 股民
-----------------
介紹 一 個 ASP.net MVC 系列 教程
在 asp.net 中 實現 觀察者 模式 ,或 有 更 好 的 方法 (續)
Asp.Net 頁面 執行 流程 分析
asp.net 控件 開發 顯示 控件 內容
ASP.NET 自定義 控件 復雜 屬性 聲明 持久性 淺析 
聚 類聚的非常準確,而且只迭代了3次,模型就收斂了,當然了這是最理想的效果,其實聚類的結果受好多種因素制約,提取特征的算法,隨機初始化函 數,kmeans算法的實現等,都有優化的地方,不信你把輸入的數據的順序改改,聚類結果就不一樣了,或者把隨機數的種子變一下,結果也不一樣,k- means算法加入一些變異系數的調整,結果也不一樣,提取特征的地方不用TF/IDF權重算法用別的,結果肯定也不一樣。
完整代碼里還有另一組測試數據,結果也很不錯,我的意思是我的算法不是針對一組測試數據,而是針對好多數據都有不錯的結果。

總結:數學和英語真是寫程序之根本呀,弄這個東西遇到了好多英語單詞不會,查還查不出來,也理解不了,最后google一看,是個數學專用詞,再搜索這個數學專用詞的中文解釋,發現還是理解不了那數學原理。所以還是得多學習數學和英語。

參考鏈接:
K-MEANS算法
http://beauty9235.javaeye.com/blog/161675
什么是變異系數
http://zhidao.baidu.com/question/15013015.html
TF/IDF實現
http://www.codeproject.com/KB/cs/tfidf.aspx

 

源碼下載:WawaTextCluster.zip


http://www.cnblogs.com/onlytiancai/archive/2008/05/10/1191557.html 《來源》

posted on 2012-04-01 07:57 Snape 閱讀(581) 評論(0)  編輯 收藏 引用 所屬分類: C++ 轉載

導航

<2025年9月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

統計

常用鏈接

留言簿

隨筆分類

隨筆檔案

文章分類

文章檔案

my

搜索

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            久久综合色播五月| 国内精品久久久久影院 日本资源| 久久精品国产欧美激情| 久久精品一区二区| 欧美.日韩.国产.一区.二区| 欧美成在线观看| 国产精品人人爽人人做我的可爱| 国产午夜精品一区二区三区欧美| 亚洲国产精品日韩| 亚洲欧美日韩在线高清直播| 久久精品午夜| 99国产精品99久久久久久| 午夜精品福利视频| 欧美人牲a欧美精品| 韩国v欧美v日本v亚洲v| 亚洲一区自拍| 亚洲国产日韩在线| 一区二区三区精品在线| 久久精品视频va| 久久久爽爽爽美女图片| 国产精品一级久久久| 日韩一区二区久久| 久久综合久久久| 99国产精品久久久久老师| 国产伦理一区| 91久久精品网| 久久综合色综合88| 亚洲一区亚洲| 美玉足脚交一区二区三区图片| 国产一区二区av| 欧美在线亚洲在线| 亚洲综合欧美| 国产精品视频免费| 亚洲电影第三页| 久久久精彩视频| 亚洲欧美日韩国产另类专区| 老色批av在线精品| 久久精品99国产精品| 欧美日韩国产小视频| 一区二区av| 亚洲免费av观看| 国产精品ⅴa在线观看h| 一区二区日韩欧美| 欧美岛国激情| 欧美电影免费| 美女视频黄a大片欧美| 欧美一区二区三区成人 | 一区在线观看| 久久久久久久波多野高潮日日| 欧美专区18| 激情综合色综合久久| 亚洲视屏一区| 国产精品有限公司| 一区二区欧美日韩视频| 国产精品一区二区欧美| 日韩视频在线免费观看| 亚洲美女在线观看| 99国产精品私拍| 亚洲作爱视频| 欧美日韩免费看| 性一交一乱一区二区洋洋av| 久久国产精品久久久| 久久精品99| 精品不卡在线| 老司机凹凸av亚洲导航| 欧美成人一品| 最新国产の精品合集bt伙计| 亚洲免费观看| 亚洲一区二区三| 久久精品日产第一区二区| 久久狠狠一本精品综合网| 国产日韩欧美另类| 欧美在线观看视频在线| 久久综合九色欧美综合狠狠| 91久久精品日日躁夜夜躁国产| 欧美成人免费小视频| 亚洲日本免费| 国产欧美日韩精品丝袜高跟鞋| 欧美激情国产精品| 国产精品女主播| 欧美国产先锋| 在线亚洲一区二区| 国产美女精品| 另类国产ts人妖高潮视频| 亚洲国产高清视频| 亚洲综合大片69999| 国产日韩精品一区| 麻豆精品在线观看| 夜夜嗨av色综合久久久综合网| 久久成人精品一区二区三区| 亚洲第一精品福利| 久久影音先锋| av不卡在线观看| 久久久久91| 一区二区三区四区五区视频| 国产乱人伦精品一区二区 | 久久色在线观看| 欧美影视一区| 亚洲黄网站在线观看| 久久久久免费| 亚洲精品欧美专区| 亚洲日本成人女熟在线观看| 亚洲视频欧美视频| 在线视频一区观看| 娇妻被交换粗又大又硬视频欧美| 欧美精品 国产精品| 欧美激情一区二区三区在线视频观看| 日韩亚洲精品电影| 国产主播一区| 国产精品高潮呻吟| 亚洲午夜国产成人av电影男同| 久久久久99| 午夜老司机精品| 国产欧美一区二区精品性色| 欧美高清视频一二三区| 亚洲国产99| 久久综合伊人77777蜜臀| 国产一区二区毛片| 国产精品视频男人的天堂| 欧美刺激性大交免费视频| 久久动漫亚洲| 性色av一区二区怡红| 玖玖精品视频| 欧美一区二区三区精品电影| 日韩视频中文| 亚洲欧洲精品一区二区三区不卡| 国产欧美日韩另类视频免费观看| 欧美日韩一区二区欧美激情| 女女同性精品视频| 久久综合激情| 久久久精品国产99久久精品芒果| 午夜精品一区二区三区四区| 在线视频你懂得一区| 夜夜躁日日躁狠狠久久88av| 日韩视频专区| 99热这里只有成人精品国产| 91久久精品一区二区别| 亚洲国产精品www| 亚洲第一页自拍| 亚洲狠狠丁香婷婷综合久久久| 欧美国产免费| 欧美高清视频免费观看| 欧美成在线观看| 欧美顶级少妇做爰| 亚洲国产裸拍裸体视频在线观看乱了| 欧美激情亚洲激情| 亚洲精品美女久久7777777| 亚洲人久久久| 一本色道久久综合| 亚洲天堂男人| 午夜精品影院| 久久视频一区二区| 欧美激情视频在线免费观看 欧美视频免费一 | 久久免费视频网站| 一区二区三区高清视频在线观看| 99国产精品私拍| 亚洲色无码播放| 在线成人www免费观看视频| 欧美日韩精品欧美日韩精品一| 久久精品一区中文字幕| 欧美大片一区二区| 久久一区视频| 欧美成人综合在线| 欧美无乱码久久久免费午夜一区| 国产精品激情| 国产一区免费视频| 亚洲精品女人| 亚洲愉拍自拍另类高清精品| 久久精品女人的天堂av| 欧美韩日一区二区三区| 亚洲精品一区二区三区福利| 亚洲免费中文| 欧美国产成人精品| 国产精品日产欧美久久久久| 国产主播喷水一区二区| 99视频一区| 久久精品国产99| 亚洲美女精品久久| 欧美一区亚洲| 欧美日韩你懂的| 国精品一区二区| 亚洲视频每日更新| 米奇777在线欧美播放| 一区二区av在线| 久久久久这里只有精品| 亚洲另类在线一区| 久久综合网络一区二区| 国产精品www| 亚洲精品视频免费| 老司机一区二区三区| 亚洲天堂av高清| 欧美第一黄色网| 一区二区三区自拍| 性欧美大战久久久久久久免费观看 | 快播亚洲色图| 国产女同一区二区| 亚洲一级在线观看| 亚洲日本免费电影| 麻豆成人在线观看| 狠狠色狠狠色综合日日五|