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. 应删除词的权重应该是零。

我们很容易发现，如果一个关键词只在很少的网页中出现，我们通过它就容易锁定搜索目标，它的权重也就应该大。反之如果一个词在大量网页中出现，我们看到它仍然不很清楚要找什么内容，因此它应该小。概括地讲，假定一个关键词 ｗ 在 Ｄｗ 个网页中出现过，那么 Ｄｗ 越大，ｗ的权重越小，反之亦然。在信息检索中，使用最多的权重是“逆文本频率指数” （Inverse document frequency 缩写为ＩＤＦ），它的公式为ｌｏｇ（Ｄ／Ｄｗ）其中Ｄ是全部网页数。比如，我们假定中文网页数是Ｄ＝１０亿，应删除词“的”在所有的网页中都出现，即Ｄｗ＝１０亿，那么它的ＩＤＦ＝log(10亿/10亿）= log (1) = ０。假如专用词“原子能”在两百万个网页中出现，即Ｄｗ＝２００万，则它的权重ＩＤＦ＝log(500) =6.2。又假定通用词“应用”，出现在五亿个网页中，它的权重ＩＤＦ = 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. #We further use k words  corresponding to the k bigges weights as the features set for each big class.  
3.   
4. import IndexOfClass  #import the IndexOfClass.py, to obtain the row index of each big class in the original Rujia data  
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. //---------------------TF Features-------------------------//                 
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. //                                      System.out.println("Find "+key);  //输出找到  
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. //                  System.out.println(key+"appears "+otherClassNum+" times");  //输出当前word在其他类当中出现的次数  
126.                     idfMap.put(key, Math.log10(1.0*(totalClassNum-1)/otherClassNum));  
127. //                  System.out.println(Math.log10(1.0*(totalClassNum-1)/otherClassNum));   
128.                 }  
129.                   
130. //-----------TF和IDF特征的融合，并排序，取每个小类的前五名-----------------//  
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. //                      return (o1.getKey()).toString().compareTo(o2.getKey());  
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. }