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

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>
            99v久久综合狠狠综合久久| 亚洲成色精品| 亚洲性图久久| 99精品视频免费全部在线| 欧美日韩精品欧美日韩精品 | 亚洲欧美日韩一区二区三区在线观看| 欧美日韩另类视频| 午夜在线精品偷拍| 久久国产精品第一页| 黄色成人av| 亚洲精品美女在线观看| 欧美性一区二区| 久久精视频免费在线久久完整在线看| 欧美亚洲在线视频| 亚洲欧洲日产国产网站| 中国成人黄色视屏| 一区精品久久| 亚洲美女精品久久| 国产一区二区三区四区老人| 欧美成人亚洲成人| 国产精品国产三级国产普通话三级 | 欧美 日韩 国产 一区| 亚洲一区二区高清| 欧美中文字幕精品| 一本久久综合亚洲鲁鲁| 亚洲综合日韩在线| 亚洲乱码视频| 欧美一区二区三区免费看| 亚洲精品在线观| 欧美一区二区网站| 在线综合+亚洲+欧美中文字幕| 欧美一二三区在线观看| 中日韩高清电影网| 老鸭窝毛片一区二区三区| 香港久久久电影| 欧美精品一区二区三区蜜臀| 久久成人在线| 欧美体内she精视频在线观看| 老司机免费视频久久| 国产精品久久久久久久浪潮网站| 男女精品网站| 国产日韩欧美成人| 亚洲一区二区三区精品动漫| 亚洲免费电影在线| 你懂的国产精品| 久久久久国色av免费观看性色| 欧美三区美女| 亚洲国产一区二区a毛片| 在线看视频不卡| 欧美一区二区日韩一区二区| 亚洲天堂av综合网| 欧美精品www在线观看| 欧美va亚洲va香蕉在线| 国产亚洲激情| 欧美在线综合| 久久久久久久综合日本| 国产欧美日本一区二区三区| 亚洲图片在区色| 亚洲尤物在线视频观看| 欧美午夜激情在线| 一本色道精品久久一区二区三区| 一区二区激情小说| 欧美日韩一区二区在线| 99国内精品久久| 在线亚洲国产精品网站| 欧美日韩人人澡狠狠躁视频| 亚洲精品久久久久中文字幕欢迎你 | 亚洲人体偷拍| 欧美 日韩 国产一区二区在线视频| 暖暖成人免费视频| 亚洲欧洲一区二区三区久久| 免播放器亚洲| 最新亚洲电影| 亚洲网址在线| 国产一区二区高清不卡| 久久久噜久噜久久综合| 欧美a级在线| 亚洲美女视频在线免费观看| 欧美日韩ab片| 亚洲尤物精选| 狂野欧美激情性xxxx| 亚洲高清不卡av| 欧美激情久久久| 亚洲一区二区三区乱码aⅴ蜜桃女| 篠田优中文在线播放第一区| 狠狠色丁香久久综合频道| 卡一卡二国产精品| a91a精品视频在线观看| 久久九九有精品国产23| 最新日韩精品| 国产精品尤物福利片在线观看| 久久精品国产免费| 亚洲精品一区二区三区四区高清 | 一区二区激情| 国产亚洲精品bt天堂精选| 蜜臀av在线播放一区二区三区| 日韩视频三区| 久久亚洲国产成人| 一本色道久久加勒比精品| 国产欧美在线| 欧美国产精品劲爆| 欧美一区在线视频| 亚洲美女黄色片| 久久久五月天| 亚洲视频免费| 亚洲国产精品va在线看黑人| 国产精品国产三级国产a| 久久久久久婷| 亚洲综合欧美| 亚洲伦理中文字幕| 免费一级欧美片在线播放| 亚洲欧美国产毛片在线| 亚洲国产你懂的| 国产综合在线看| 国产精品mm| 欧美精品日韩综合在线| 久久综合色影院| 午夜在线精品偷拍| 日韩视频免费观看| 亚洲第一在线| 男男成人高潮片免费网站| 欧美一区二区三区在线观看视频| 亚洲精品男同| 亚洲国产精品电影| 激情综合色丁香一区二区| 国产精品久久久久一区二区三区| 欧美韩日亚洲| 免费观看30秒视频久久| 久久国产精品网站| 久久国产福利| 欧美一区二区三区免费视频| 午夜精品福利视频| 亚洲欧美韩国| 亚洲免费网站| 亚洲一区二区免费视频| 一区二区三区www| 99香蕉国产精品偷在线观看| 亚洲精品国产精品乱码不99按摩| 欧美激情一区二区三区不卡| 欧美大片一区二区| 欧美成人免费在线| 欧美国产日韩精品| 亚洲国产第一| 亚洲精品免费在线播放| 亚洲精品影视| 一区二区三区黄色| 亚洲少妇中出一区| 午夜激情综合网| 久久激情五月丁香伊人| 久久久欧美精品sm网站| 另类酷文…触手系列精品集v1小说| 久久婷婷国产综合国色天香| 女生裸体视频一区二区三区| 欧美国产丝袜视频| 欧美午夜精彩| 国产一区免费视频| 亚洲丶国产丶欧美一区二区三区| 91久久国产精品91久久性色| 日韩视频在线一区二区| 亚洲欧美另类在线观看| 欧美一区2区三区4区公司二百| 久久久久九九视频| 亚洲福利视频三区| 夜夜嗨av一区二区三区四区 | 亚洲日本欧美日韩高观看| 99精品视频一区| 欧美一级久久久| 免费影视亚洲| 国产精品美女久久久久av超清 | 国产亚洲精品高潮| 亚洲理伦在线| 欧美一区在线看| 欧美黄色免费| 亚洲一级黄色| 麻豆精品91| 国产欧美在线视频| 亚洲精品美女在线| 久久xxxx| 亚洲另类自拍| 久久久噜噜噜久久| 国产精品久久久久99| 永久免费精品影视网站| 中文欧美字幕免费| 蜜桃视频一区| 亚洲欧美在线视频观看| 欧美韩日一区二区| 激情婷婷欧美| 亚洲欧美精品suv| 亚洲国产欧美日韩| 欧美一区二区成人6969| 欧美日韩亚洲系列| 亚洲电影免费观看高清完整版在线 | 欧美有码视频| 亚洲美女区一区| 久久综合福利| 国产综合视频| 久久成年人视频| 在线亚洲激情| 欧美激情亚洲国产| 亚洲国产第一页|