从网页相关性TF-IDF到余弦定理的新闻分类的程序实现

前提：TF-IDF 模型是搜索引擎等实际应用中被广泛使用的信息检索模型，但对于 TF-IDF 模型一直存在各种疑问。本文为信息检索问题一种基于条件概率的盒子小球模型，其核心思想是把“查询串q和文档d的匹配度问题”转化为“查询串q来自于文档d的条件概率问题”。它从概率的视角为信息检索问题定义了比 TF-IDF 模型所表达的匹配度更为清晰的目标。此模型可将 TF-IDF 模型纳入其中，一方面解释其合理性，另一方面也发现了其不完善之处。另外，此模型还可以解释 PageRank 的意义，以及 PageRank 权重和 TF-IDF 权重之间为什么是乘积关系.--->引用(http://baike.baidu.com/view/1228847.htm?fr=aladdin)。

2014年9月19日23:49:07 实现IF-IDF。才30%。坑啊，后期的阈值怎么设置还是需要研究的~

package com.lean;

import java.util.ArrayList;
import java.util.Arrays;

/*
 * 1.如何度量网页和查询的相关性---信息检索领域
 * TF-IDF(词频-逆文本频率指数)算法: 
 * TF词频=(词出现的次数/文本中中单词的总数)
 * IDF=log(D/DW)=log(网页总数/包含特定单词的网页)---->为什么是log()，数学之美给出的解释是“一个特定条件下关键词的概率分布的交叉熵”
 * 相关性=TF1*IDF1+TF2*IDF2+TF3*IDF3+...
 * 
 * 2.如何利用余弦定理到新闻的自动分类算法
 * 计算每个新闻词汇表的IDF。
 * 将每个新闻词汇表IDF当做特征向量-->数组实现，每个下标对应特定的单词
 * 利用余弦公式计算新闻两两之间的夹角A,(A角度越大，相关性就越小，平行时相关性最大)
 * 不断合并A<T(T代表阈值，根据经验划分)产生的小类
 * 继续计算各个小类的特征向量，继续合并，直到合并为1个大类。
 * 根据合并的层次大小，决定新闻分类的规模，ok
 * 
 * 
 * 3.优化算法复杂度：
 * 余弦定理的分子分母优化，做记忆化存储。
 * 删除虚词(的，是，和，一些连词，副词，介词，只定位实词"aXb"模式)
 * 位置的加权（主题的关键词权重>正文，正文首尾关键词权重>中间）
 * 
 * 模拟算法开始啦~~~
 */
public class newCate {
	int A[]={};
	static int news1[]={0,1,2,3,4,5,6,7,8,9,1,2,3,4,5,1,2,3,3,3};//代表一条新闻。文字用数字代替~~~
	static int news2[]={12,13,19,11,12,13,14,15,11,12,13,13,3};
	static int news3[]={10,11,12,13,24,24,25,21,22,23,23,13};
	
	static int Keys[]={3,2,8};//3个关键词，当然假设已经经过分词处理过的结果
    
	/*
	 * 计算词频
	 */
	private double[] getTF(ArrayList<int[]> newsList ,int keys[]) {
		int n=newsList.size(),m=Keys.length;
		double TF[]=new double[m];//词频
		
		for (int i = 0; i < TF.length; i++) {
			TF[i]=0;
		}
		/*
		 * 可以优化到nlogn~~~懒的写了~~
		 */
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				int news[]=newsList.get(j);
				int K=news.length;
				for (int k = 0; k <K ; k++) {
					if(keys[i]==news[k]) TF[i]+=(1.0/K);
				}		
			}
		}			
		return TF;
	}	
	/*
	 * 计算各个关键词的权重
	 * IDF=log(D/DW)=log(网页总数/包含特定单词的网页)
	 */
	private double[] getIDF(ArrayList<int[]> al,int keys[]) {	
		int D=al.size(),DW=0;
		double IDF[]=new double[keys.length];
		
		for (int i = 0; i < IDF.length; i++) {
			DW= getDw(al,keys[i]);
			IDF[i]+=Math.log(D/DW);
		}
		return IDF;
	}
	
	/*
	 * 计算出现关键词的新闻数
	 */
	private int getDw(ArrayList<int[]> newsList, int i) {
		int cnt=0;
		for (int j = 0; j < newsList.size(); j++) {
			int news[]=newsList.get(j);
			for (int k = 0; k < news.length; k++) {
				if(news[k]==i){
					 cnt++;
					 break;
				}
			}
		}
		return cnt;
	}


	/*
	 * 词频*权重的集合
	 * 相关性=TF1*IDF1+TF2*IDF2+TF3*IDF3+...
	 */
	private double getRelate(double TF[],double IDF[]) {
		int n=TF.length;
		double ans=0.0;
		for (int i = 0; i <n; i++) {
			ans+=TF[i]*IDF[i];
		}
		return ans;
	}
	
	public static void main(String[] args) {
		newCate nc=new newCate();
		
//---------------IF-IDF------------		
		//新闻网页集合
		ArrayList<int[]> newsList=new ArrayList<int[]>();
		newsList.add(news1);
		newsList.add(news2);
		newsList.add(news3);
		newsList.add(news3);
		newsList.add(news3);
		newsList.add(news3);
		double tf[]=nc.getTF(newsList, Keys);
		double idf[]=nc.getIDF(newsList, Keys);
		System.out.println("关键词词频集合="+Arrays.toString(tf));
		System.out.println("关键词贡献集合="+Arrays.toString(idf));
		
		double relate=nc.getRelate(tf, idf);
		System.out.println("关键词的相关性="+relate);
		
//-----------news_cate-----------------------
		
		
		
	}
	
	
}