TF-IDF算法及其编程实现

概念

TF-IDF(term frequency–inverse document frequency)是一种用于资讯检索与资讯探勘的 常用加权技术 。TF-IDF是一种统计方法,用以评估一字词对于一个文件集或一个语料库中的其中一份文件的重要程度。 字词的重要性随着它在文件中出现的次数成正比增加 ,但同时会 随着它在语料库中出现的频率成反比下降 。TF-IDF加权的各种形式常被搜寻引擎应用,作为文件与用户查询之间相关程度的度量或评级。除了TF-IDF以外,因特网上的搜寻引擎还会使用基于连结分析的评级方法,以确定文件在搜寻结果中出现的顺序。

原理

在一份给定的文件里, 词频 (term frequency, TF) 指的是某一个给定的词语在该文件中出现的次数。这个数字通常会被 归一化(分子一般小于分母 区别于IDF) ,以防止它偏向长的文件。(同一个词语在长文件里可能会比短文件有更高的词频,而不管该词语重要与否。)

逆向文件频率 (inverse document frequency, IDF) 是一个词语普遍重要性的度量。某一特定词语的IDF,可以由总文件数目除以包含该词语之文件的数目,再将得到的商取对数得到。

某一特定文件内的高词语频率,以及该词语在整个文件集合中的低文件频率,可以产生出高权重的TF-IDF。因此,TF-IDF倾向于过滤掉常见的词语,保留重要的词语。

TFIDF的主要思想是 :如果某个词或短语在一篇文章中出现的频率TF高,并且在其他文章中很少出现,则认为此词或者短语具有很好的类别区分能力,适合用来分类。 TFIDF实际上是:TF * IDF,TF词频(Term Frequency),IDF反文档频率(Inverse Document Frequency)。 TF 表示词条在文档d中出现的频率(另一说: TF词频(Term Frequency)指 的是 某一个给定的词语在该文件中出现的次数 )。IDF的主要思想是:如果 包含词条t的文档越少 ,也 就是n越小,IDF越大 ,则说明词条t具有很好的类别区分能力。如果某一类文档C中 包含词条t的文档数为m ,而 其它类包含t的文档总数为k ,显然所有包含t的文档数n=m+k,当 m大 的时候, n也大 ,按照IDF公式得到的 IDF的值会 小,就说明该词条t类别区分能力不强。(另一说: IDF反文档频率(Inverse Document Frequency) 是指果包含词条的文档越少,IDF越大,则说明词条具有很好的类别区分能力。 )但是实际上,如果一个词条在一个类的文档中频繁出现,则说明该词条能够很好代表这个类的文本的特征,这样的词条应该给它们赋予较高的权重,并选来作为该类文本的特征词以区别与其它类文档。这就是IDF的不足之处.

在一份给定的文件里, 词频 (term frequency,TF)指的是某一个给定的词语在该文件中出现的频率。这个数字是对 词数 (term count)的归一化,以防止它偏向长的文件。(同一个词语在长文件里可能会比短文件有更高的词数,而不管该词语重要与否。)对于在某一特定文件里的词语 ti 来说,它的重要性可表示为:

以上式子中 nij是 该词在文件dj中的出现次数 ,而分母则是在 文件dj中所有字词的出现次数之和

      逆向文件频率 (inverse document frequency,IDF)是一个词语普遍重要性的度量。某一特定词语的IDF,可以由总文件数目除以包含该词语之文件的数目,再将得到的商取对数得到:

其中

  • |D|:语料库中的 文件总数
  • 包含词语的文件数目 (即nij!=0的文件数目) 如果该词语不在语料库中,就会导致被除数为零, 因此一般情况下使用

然后

某一特定文件内的高词语频率,以及该词语在整个文件集合中的低文件频率,可以产生出高权重的TF-IDF。因此, TF-IDF倾向于过滤掉常见的词语,保留重要的词语

示例

一:有很多不同的数学公式可以用来计算TF-IDF。这边的例子以上述的数学公式来计算。词频 (TF) 是一词语出现的次数除以该文件的总词语数。假如一篇文件的总词语数是100个,而词语“母牛”出现了3次,那么“母牛”一词在该文件中的词频就是3/100=0.03。一个计算文件频率 (DF) 的方法是测定有多少份文件出现过“母牛”一词,然后除以文件集里包含的文件总数。所以,如果“母牛”一词在1,000份文件出现过,而文件总数是10,000,000份的话,其逆向文件频率就是 log(10,000,000 / 1,000)=4。最后的TF-IDF的分数为0.03 * 4=0.12。

二: 根据关键字k1,k2,k3进行搜索结果的相关性就变成TF1*IDF1 + TF2*IDF2 + TF3*IDF3 。比如document1的term总量为1000,k1,k2,k3在document1出现的次数是100,200,50。包含了 k1, k2, k3的docuement总量分别是 1000, 10000,5000。document set的总量为10000。 TF1 = 100/1000 = 0.1 TF2 = 200/1000 = 0.2 TF3 = 50/1000 = 0.05 IDF1 = log(10000/1000) = log(10) = 2.3 IDF2 = log(10000/100000) = log(1) = 0; IDF3 = log(10000/5000) = log(2) = 0.69 这样 关键字k1,k2,k3与docuement1的相关性 = 0.1*2.3 + 0.2*0 + 0.05*0.69 = 0.2645 其中k1比k3的比重在document1要大,k2的比重是0.

三:在某个一共有一千词的网页中“原子能”、“的”和“应用”分别出现了 2 次、35 次 和 5 次,那么它们的词频就分别是 0.002、0.035 和 0.005。 我们将这三个数相加,其和 0.042 就是相应网页和查询“原子能的应用”  相关性的一个简单的度量概括地讲,如果一个查询包含关键词 w1,w2,...,wN, 它们在一篇特定网页中的词频分别是: TF1, TF2, ..., TFN。 (TF: term frequency)。 那么,这个查询和该网页的相关性就是:TF1 + TF2 + ... + TFN

读者可能已经发现了又一个漏洞。在上面的例子中,词“的”站了总词频的 80% 以上,而它对确定网页的主题几乎没有用。我们称这种词叫“应删除词”(Stopwords),也就是说在度量相关性是不应考虑它们的频率。在汉语中,应删除词还有“是”、“和”、“中”、“地”、“得”等等几十个。忽略这些应删除词后,上述网页的相似度就变成了0.007,其中“原子能”贡献了 0.002,“应用”贡献了 0.005。细心的读者可能还会发现另一个小的漏洞。在汉语中,“应用”是个很通用的词,而“原子能”是个很专业的词,后者在相关性排名中比前者重要。因此我们需要给汉语中的每一个词给一个权重,这个权重的设定必须满足下面两个条件:

1. 一个词预测主题能力越强,权重就越大,反之,权重就越小。我们在网页中看到“原子能”这个词,或多或少地能了解网页的主题。我们看到“应用”一次,对主题基本上还是一无所知。因此,“原子能“的权重就应该比应用大。

2. 应删除词的权重应该是零。

我们很容易发现,如果一个 关键词只在很少的网页中出现,我们通过它就容易锁定搜索目标,它的权重也就应该大 。反之 如果一个词在大量网页中出现 ,我们看到它仍然不很清楚要找什么内容,因此它应该小。概括地讲, 假定一个关键词 w 在 Dw 个网页中出现过,那么 Dw 越大,w的权重越小,反之亦然 。在信息检索中,使用最多的权重是“逆文本频率指数” (Inverse document frequency 缩写为IDF),它的公式为log(D/Dw)其中D是全部网页数。比如,我们假定中文网页数是D=10亿,应删除词“的”在所有的网页中都出现,即Dw=10亿,那么它的IDF=log(10亿/10亿)= log (1) = 0。 假如专用词“原子能”在两百万个网页中出现,即Dw=200万,则它的权重IDF=log(500) =6.2。又假定通用词“应用”,出现在五亿个网页中,它的权重IDF = log(2)则只有 0.7。也就只说,在网页中找到一个“原子能”的比配相当于找到九个“应用”的匹配 。利用 IDF, 上述相关性计算个公式就由词频的简单求和变成了加权求和,即 TF1*IDF1 + TF2*IDF2 +... + TFN*IDFN 。在上面的例子中,该网页和“原子能的应用”的相关性为 0.0161,其中“原子能”贡献了 0.0126,而“应用”只贡献了0.0035。这个比例和我们的直觉比较一致了。

我使用python编写程序,提取了**问答系统中数据的TF-IDF特征。(其中的文本文件大家可以随意替换为其余文件)

[python] view plaincopy

  1. # This demo can extract the TF-IDF features of each big class data.   
  2.   
  3.   
  4. import  IndexOfClass     
  5. import  math   # the math.log10 is in this module   
  6.   
  7. fileTF=open( 'TF features.txt' 'w' )  
  8.   
  9. numBigClass=len(IndexOfClass.dictClassR_C)- 1   
  10.   
  11.   
  12. for  index  in  range( 1 , numBigClass+ 1 ):   # 1, numBigClass+1   
  13.      print   'the ' +str(index)+ ' class is processing...'   
  14.     fileRujia=open( 'Data_After_Split.txt' 'r' )   #open the original Rujia data file   
  15.     dictTF_IDF={}  
  16.     wordSum= 0    #mark the sum of frequency of words, i.e. the denumerator of TF   
  17.      
  18.     rowHead=IndexOfClass.dictClassR_C[index]   # head row of the index class   
  19.     rowTail=IndexOfClass.dictClassR_C[index+ 1 # tail row   
  20.      for  line  in  fileRujia.readlines()[rowHead- 1 :rowTail- 1 ]:   # within the index class   
  21.          #print rowHead, rowTail   
  22.          #print line   
  23.          for  word  in  line.split():   # this FOR loop counts the term times   
  24.             wordSum+= 1   
  25.              if  dictTF_IDF.has_key(word):  
  26.                 dictTF_IDF[word]+= 1   
  27.              else :  
  28.                 dictTF_IDF[word]= 1   
  29.      
  30.      
  31.      for  word  in  dictTF_IDF:  
  32.         dictTF_IDF[word]= 1.0 *dictTF_IDF[word]/wordSum   # to obtain the TF   
  33.          
  34.         numDocument= 1   
  35.          for  k  in  range( 1 , numBigClass+ 1 ):   # search for the number of big class containing the current word   
  36.             r1=IndexOfClass.dictClassR_C[k]  
  37.             r2=IndexOfClass.dictClassR_C[k+ 1 ]  
  38.              #print r1, r2   
  39.             fileRujia=open( 'Data_After_Split.txt' 'r' )  
  40.              for  line  in  fileRujia.readlines()[r1- 1 :r2- 1 ]:  
  41.                  #print line   
  42.                  if  word  in  line.split():  
  43.                     numDocument+= 1   
  44.                      #print 'abc'   
  45.                      break   
  46.          #print numDocument          
  47.         dictTF_IDF[word]*=math.log10( 1.0 *numBigClass/numDocument)  # IDF   
  48.                 
  49.   
  50.     L=sorted(dictTF_IDF.iteritems(), key= lambda  asd: asd[ 1 ], reverse= True )  
  51.      for  k  in  L[ 0 : 5 ]:  
  52.         fileTF.write(k[ 0 ]+ ' ' +str(k[ 1 ])+ ' ' )  
  53.     fileTF.write( '\n' )    
  54.      

JAVA版本的程序我也实现了,其中有许多注释和不必要的调试语句。

[java] view plaincopy

  1. import  java.io.BufferedReader;  
  2. import  java.io.File;  
  3. import  java.io.FileInputStream;  
  4. import  java.io.FileOutputStream;  
  5. import  java.io.InputStreamReader;  
  6. import  java.io.PrintWriter;  
  7.   
  8. import  java.util.ArrayList;  
  9. import  java.util.Collections;  
  10. import  java.util.Comparator;  
  11. import  java.util.Iterator;  
  12. import  java.util.Map.Entry;  
  13. import  java.util.Scanner;  
  14. import  java.util.HashMap;   
  15. import  java.util.List;   
  16. import  java.util.Arrays;   
  17.   
  18.   
  19. public   class  demo {  
  20.   
  21.      /**  
  22.      * @param args  
  23.      */   
  24.      public   static   void  main(String[] args)  throws  Exception{  
  25.          // TODO Auto-generated method stub   
  26.              // TODO Auto-generated method stub   
  27.   
  28.             java.io.File oriDataFile= new  java.io.File( "originalData.txt" );  //读取文件   
  29.             java.io.File classIndexFile= new  java.io.File( "smallClassIndex.txt" );   
  30.              if (!oriDataFile.exists() && !classIndexFile.exists()){  
  31.                 System.out.println( " inputFile does not exist..." );   
  32.                 System.exit( 0 );   
  33.             }             
  34.               
  35.             Scanner inputData= new  Scanner(oriDataFile);   
  36.             Scanner inputIndex= new  Scanner(classIndexFile);   
  37.              int  totalClassNum= 0 ;    //小类的类别数   
  38.              int  a[]= new   int [ 1000 ];   
  39.              while  (inputIndex.hasNext()){  
  40.                 a[totalClassNum++]=inputIndex.nextInt();     //存储每个小类的行号,最后一个无用             
  41.             }  
  42. //          System.out.println(totalClassNum);   
  43.               
  44.             java.io.File featureFile= new  java.io.File( "TFIDFFeatures.txt" );   
  45.             java.io.PrintWriter output =  new  java.io.PrintWriter(featureFile);  
  46.              for ( int  k= 0 ; k<totalClassNum- 1 ; k++){   //循环遍历每个小类   totalClassNum-1   
  47. //              System.out.println(totalClassNum);    
  48.                 System.out.println( "The " +(k+ 1 )+ " class is processing ..." );   
  49.                  int  headLine=a[k];   //当前小类起始行   
  50.                  int  tailLine=a[k+ 1 ]; //终止行   
  51.                  int  numLine=tailLine-headLine;    
  52. //              System.out.println(numLine);   
  53.                   
  54.   
  55. //              可以统计当前类中每个word出现的次数,TF   
  56.                 System.out.println( "The TF features are extracting ..." );   
  57.                 HashMap<String, Integer> wordMap= new  HashMap<String, Integer>();   
  58.                  int  totalCount= 0 ;   
  59.                  for ( int  i= 0 ; i<numLine; i++){  
  60.                     String str=inputData.nextLine();   //提取每一行   
  61. //                  System.out.println(str);   
  62.                       
  63.                     String[] strArray=str.split( " " );   //按空格切割   
  64.                     totalCount+=strArray.length;   
  65.                      for ( int  j= 0 ; j<strArray.length; j++){  
  66. //                      System.out.println(strArray[j]);    
  67.                          if (!wordMap.containsKey(strArray[j])){   //如果不存在,添加   
  68.                             wordMap.put(strArray[j],  1 );   
  69.                         }  
  70.                          else {   //如果已存在,count+1   
  71.                              int  v=wordMap.get(strArray[j]);   
  72.                             wordMap.put(strArray[j], v+ 1 );   
  73.                         }                         
  74.                     }  
  75.                 }  
  76. //              System.out.println(totalCount);                
  77.                 HashMap<String, Double> tfMap= new  HashMap<String, Double>();   
  78.                 Iterator it=wordMap.keySet().iterator();  
  79.                  while  (it.hasNext()){  
  80.                     String key=(String) it.next();   
  81.                      int  v=wordMap.get(key);   
  82.                     tfMap.put(key,  1.0 *v/totalCount);   //TF Map   
  83. //                  System.out.println(key+1.0*v/totalCount);    
  84.                 }  
  85.                   
  86. //---------------------IDF Features----------------------//   
  87.                 System.out.println( "The IDF features are extracting ..." );   
  88.                   
  89.                 HashMap<String, Double> idfMap= new  HashMap<String, Double>();   
  90.                 Iterator it1=wordMap.keySet().iterator();  
  91.                  while  (it1.hasNext()){  
  92.                     String key=(String) it1.next();   //取当前word   
  93. //                  System.out.println("Searching for "+key);   
  94.                      //在其余小类中查找是否出现过key   
  95.                      int  otherClassNum= 1 ;   //记录每个word在其他类出现的次数   
  96.                      for  ( int  m= 0 ; m<totalClassNum- 1 ; m++){   //遍历所有的类 totalClassNum-1   
  97.                          int  beginning=a[m];    //当前其他类的起始行   
  98.                          int  ending=a[m+ 1 ];    //终止行   
  99. //                      System.out.println(beginning);    
  100. //                      System.out.println(ending);    
  101.                           
  102.                         InputStreamReader I= new  InputStreamReader( new  FileInputStream( "originalData.txt" ),  "gbk" );   //编码是gbk,不过最好统一为utf-8   
  103.                         BufferedReader sr =  new  BufferedReader(I);  
  104.                         String txt=sr.readLine();    //readLine读取一行,字符串   
  105.                          int  next= 1 //记录读取的行数   
  106.                          while (txt!= null ){                              
  107.                              if (next>=beginning- 1  && next<ending){   //一定要在当前其他类才好判断   
  108. //                              System.out.println(txt);    
  109.                                 String []str2Array=txt.split( " " );   
  110.                                  int  l;   
  111.                                  for  (l= 0 ; l<str2Array.length; l++){  
  112.                                      if (str2Array[l].equals(key)){  
  113.   
  114.                                         otherClassNum++;   
  115.                                          break ;   //跳出while该类的判断,期待   
  116.                                     }  
  117.                                 }  
  118.                                  if (l<str2Array.length)   //说明已经找到   
  119.                                      break //break出while循环   
  120.                             }  
  121.                             txt=sr.readLine();  //继续读取下一个问题   
  122.                             next++;   
  123.                         }  
  124.                     }  
  125.   
  126.                     idfMap.put(key, Math.log10( 1.0 *(totalClassNum- 1 )/otherClassNum));  
  127.   
  128.                 }  
  129.                   
  130.   
  131.                 HashMap<String, Double> tfIdfMap= new  HashMap<String, Double>();   
  132. //              Iterator it1=tfIdfMap.keySet().iterator();   
  133.                 Iterator it2=tfMap.keySet().iterator();  
  134.                 Iterator it3=idfMap.keySet().iterator();   
  135.                  while (it2.hasNext() && it3.hasNext()){  
  136.                     String key1=(String) it2.next();   
  137.                     String key2=(String) it3.next();   
  138.                     Double v=tfMap.get(key1)*idfMap.get(key2);   //tf*idf   
  139.                     tfIdfMap.put(key1, v);   //idfTfMap   
  140.                 }  
  141.                  //排序   
  142.                 List<Entry<String, Double>> infoIds =  
  143.                          new  ArrayList<Entry<String, Double>>(tfIdfMap.entrySet());  
  144.                 Collections.sort(infoIds,  new  Comparator<Entry<String, Double>>() {     
  145.                      public   int  compare(Entry<String, Double> o1, Entry<String, Double> o2) {   
  146.                          if (o2.getValue() - o1.getValue()> 0 ){  
  147.                              return   1 ;  
  148.                         }  
  149.                          return  - 1 ;  
  150.                          //return (int)(o2.getValue() - o1.getValue());    
  151.   
  152.                     }  
  153.                 });   
  154.                   
  155.                  int  selectNum;   
  156.                  if (infoIds.size()< 5 ){   //防止有些小类问题数量少   
  157.                     selectNum=infoIds.size();   
  158.                 }  
  159.                  else   
  160.                     selectNum= 5 ;   
  161.                   
  162.                  for  ( int  q= 0 ; q<selectNum; q++){   //只取前五名   
  163.                     String id = infoIds.get(q).toString();  
  164. //                  System.out.println(id);    
  165.                      int  equalIndex=id.indexOf( '=' );   
  166.                      char  []strChar=id.toCharArray();   
  167.                     String fea= new  String();   
  168.                      for  ( int  d= 0 ; d<equalIndex; d++){  
  169.                         fea=fea+strChar[d];   
  170.                     }  
  171.                     System.out.println(fea);  
  172.                     output.print(fea);   
  173.                     output.print( ' ' );  
  174.                 }  
  175.                 output.print( '\n' );  
  176.                 System.out.println( "The " +(k+ 1 )+ " class ends..." );   
  177.             }  
  178.               
  179.             output.close();   //close 输出的文件   
  180.               
  181.               
  182.               
  183.     }  
  184.   
  185. }  
我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章