文本相似度的设计与实现

向量空间模型的基本思想：

给定一篇文档D=D(T1,T2,…Ti,…,Tn)，若Ti在文档中既可以重复出现又存在先后次序，因此分析起来会较为困难。针对上述情况，暂不考虑Ti的顺序，并要求Ti互异，此时可将T1,T2,…Ti,…,Tn看作n维坐标，每一维对应相应值Wi，因此D(W1,W2,…,Wi,…,Wn)便可以看作一个n维向量。

例如：有一篇文档D={大家好，才是真的好}，首先进行分词后转换为D={大家/好/才是/真的/好}，之后提取出公因词D={大家，好，才是，真的}，最后通过向量空间模型将文档转换为对应的向量D={1，2，1，1}。

向量空间模型只是将文档转换为方便计算的格式，若进行相似度计算，还需使用相似度计算公式进行计算。本文使用余弦相似度计算公式。

2. 余弦相似度

余弦相似度计算公式广泛应用于文本数据之间的相似度计算过程中。其数学表达如下：

计算过程如下：

例如，有2个文档D1={大家好}，D2={才是真的好}，首先将D1、D2分词后，D1={大家/好}，D2={才是/真的/好}，其次提取出公因词D={大家，好，才是，真的}，然后通过向量空间模型转换成向量表达，D1={1，1，0，0}，D2={0，1，1，1}，最后进行相似度计算

3. 文本相似度系统

本文主要使用向量空间模型及余弦相似度距离公式进行文本相似度计算任务，系统的基本架构如下图1所示：

其基本思想为：将文档输入系统，对文档进行数据预处理操作，数据预处理完成后使用向量空间模型将词组转化为向量，之后使用余弦相似度计算公式求解文档之间的相似度，最终将计算后的结果展示出来。

数据预处理阶段，包括分词、取停用词、word2vec语义扩展，其流程如下图2所示：

在word2vec语义扩展阶段，Word2vec是Google于2013年发布的一款基于深度学习的开源工具包，主要用于将单词以向量形式表示[3]。Word2vec首先使用语料训练模型，待模型训练结束后，将新的单词输入模型进行预测，模型可按相关度排序将最相近的预测单词展现给用户，通常而言，会将top30展示给用户。

针对文档语义扩充，系统会先使用搜狗新闻语料训练CBOW模型，待模型训练结束后，将本档中的单词输入CBOW模型进行预测，最终将预测结果扩充回文档中，用于向量空间模型。

同样以之前的2篇文档为例，D1={大家/好}，D2={才是/真的/好}，通过word2vec模型后，D1={大家/好/很好/不错}，D2={才是/真的/好/很好/不错}，提取出公因词D={大家，好，很好，不错，才是，真的}，然后通过向量空间模型转换成向量表达，D1={1，1，1，1，0，0}，D2={0，1，1，1，1，1}，最后进行相似度计算

通过比较两次的Score值可得出，通过word2vec能够提高文本相似度的计算分值。

另外系统会计算文档中每一句话所对应的最大匹配及其相似度值，针对文档与文档的相似度计算，本文提出一种平均相似度计算公式，即：

其中n(dicList1)是所求文档中包含的句子个数，公式的主要思路即将每句话的最大匹配相似度叠加后求取平均值。

4. 系统设计

相应代码如下：

	/**
	 * 程序运行入口
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException {
		String dir,inputPath1,inputPath2,outputPath,word2vecModel,str1,str2;
		long start,end,dur;
		start = System.currentTimeMillis();
		dir = "data/test/";
		inputPath1 = dir + "doc3.txt";
		inputPath2 = dir + "doc3.txt";
		dir = "data/result/";
		outputPath = dir + "out3_3.txt";
		word2vecModel = "model/vectors-sougou.bin";
		
		FileHandler fh = new FileHandler();
		List<String> docList1 = fh.putFileToList(inputPath1);
		List<String> docList2 = fh.putFileToList(inputPath2);
		Tool.initWriter1(outputPath);
		
		Word2VEC w = new Word2VEC() ;
        	w.loadGoogleModel(word2vecModel) ;
        
        	Model model = new Model();
        	model.run(docList1, docList2 ,w);
        
        	end = System.currentTimeMillis();
        	dur = end - start;
        	System.out.println("dur time = " + (1.0 * dur / 1000) + " s");
        	System.out.println("dur time = " + (1.0 * dur / (1000 * 60)) + " min");
        
	}/**
	 * 程序运行入口
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException {
		String dir,inputPath1,inputPath2,outputPath,word2vecModel,str1,str2;
		long start,end,dur;
		start = System.currentTimeMillis();
		dir = "data/test/";
		inputPath1 = dir + "doc3.txt";
		inputPath2 = dir + "doc3.txt";
		dir = "data/result/";
		outputPath = dir + "out3_3.txt";
		word2vecModel = "model/vectors-sougou.bin";
		
		FileHandler fh = new FileHandler();
		List<String> docList1 = fh.putFileToList(inputPath1);
		List<String> docList2 = fh.putFileToList(inputPath2);
		Tool.initWriter1(outputPath);
		
		Word2VEC w = new Word2VEC() ;
        	w.loadGoogleModel(word2vecModel) ;
        
        	Model model = new Model();
        	model.run(docList1, docList2 ,w);
        
        	end = System.currentTimeMillis();
        	dur = end - start;
        	System.out.println("dur time = " + (1.0 * dur / 1000) + " s");
        	System.out.println("dur time = " + (1.0 * dur / (1000 * 60)) + " min");
        
	}

数据预处理阶段如下：

public class FileHandler {
	
	public static FileReader fr=null;
	public static BufferedReader br=null;
	public static String line=null;
	
	/**
	 * input:path
	 * 将文件内容添加入list中，一句一条
	 */
	public List<String> putFileToList(String path) {
		
		List<String> docList = new ArrayList<String>();
		try {
			fr = new FileReader(path);
			br = new BufferedReader(fr);
			while ((line = br.readLine()) != null) {
				String[] strArr;
				if(line.contains(".")){
					strArr = line.split(".");
					System.out.println(strArr.length);
				}else if (line.contains("。")) {
					strArr = line.split("。");
				}else if (line.contains("．")) {
					strArr = line.split("．");
				}else if (line.contains(";")) {
					strArr = line.split(";");
				}else {
					strArr = new String[1];
					strArr[0] = line;
				}
				int i,n;
				n = strArr.length;
				for(i = 0;i < n;i++){
					docList.add(strArr[i]);
				}
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
		return docList;
	}
	
	/**
	 * input:path
	 * output:List<String>
	 * 读取词典信息，以list返回词典
	 */
	public List<String> readDic(String path) {
		List<String> list = new ArrayList<String>();
		try {  
            fr=new FileReader(path);
			br=new BufferedReader(fr);
            while ((line=br.readLine()) != null ) {  
                StringTokenizer st = new StringTokenizer(line);
                while(st.hasMoreElements()){
                	list.add(st.nextToken());
                }
			}
            br.close();
            br.close();
		} catch (Exception e) {
			e.printStackTrace();
		}
		
		return list;
	}
	
}

public class StringHandler {
	
	public static byte[] bt;
	public static InputStream is;
	public static Reader read;
	public static Lexeme t;
	public static IKSegmenter iks;
	
	/**
	 * input:str
	 * 将字符串分词转换成数组
	 */
	public List<String> stringToArray(String str) {
		
		List<String> list = new ArrayList<String>();
		bt = str.getBytes();
		is = new ByteArrayInputStream(bt);
		read = new InputStreamReader(is);
		iks = new IKSegmenter(read, true);
		try {
			while ((t = iks.next()) != null) {
				list.add(t.getLexemeText());
			}
		} catch (IOException e) {
			e.printStackTrace();
		}
		return list;
		
	}
	
	/**
	 * input:arr
	 * 使用word2vec将字符数组内容扩充
	 */
	public List<String> extendWord(Word2VEC w, List<String> list) {
	
		List<String> tempList = new ArrayList<String>();
		Set<WordEntry> temp;
		Iterator iter;
		WordEntry entry;
		int i,n;
		n = list.size();
		for(i = 0;i < n;i++){
			temp = w.distance(list.get(i));
			iter = temp.iterator();
			if(!tempList.contains(list.get(i))){
				tempList.add(list.get(i));
			}
			while(iter.hasNext()){
				entry = (WordEntry) iter.next();
				if(!tempList.contains(entry.name)){
					tempList.add(entry.name);
				}
			}
		}
		return tempList;
		
	}
	
	/**
	 * input:list,stopWordsPath
	 * 删除停用词，通过读取stopWordsPath中的停用词表，将list中的停用词删除,并返回去除停用词后的list
	 */
	public List<String> deleteStopWords(List<String> list, String path2) {
		
		FileHandler fh = new FileHandler();
		List<String> stopDic = fh.readDic(path2);
		List<String> temp = new ArrayList<String>();
		int i,n;
		n = list.size();
		try {  
			for(i = 0;i < n;i++){
				if(!stopDic.contains(list.get(i))){
					temp.add(list.get(i));
				}
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
		return temp;
		
	}
}

模型计算阶段如下：

public class Model {

	/**
	 * input:docList1,docList2 主方法入口及控制器
	 */
	public void run(List<String> docList1, List<String> docList2, Word2VEC w) {
		int i, j, n1, n2;
		double[] similarArr;
		int[] locArr;
		double max, temp;
		int loc;
		n1 = docList1.size();
		n2 = docList2.size();
		similarArr = new double[n1];
		locArr = new int[n1];
		for (i = 0; i < n1; i++) {
			max = 0.0;
			temp = 0.0;
			loc = 0;
			for (j = 0; j < n2; j++) {
				try {
					temp = getSimilar(docList1.get(i), docList2.get(j), w);
				} catch (IOException e) {
					temp = 0.0;
					e.printStackTrace();
				}
				if (temp > max) {
					max = temp;
					loc = j;
				}
			}
			similarArr[i] = max;
			locArr[i] = loc;
		}
		Tool.output(docList1, docList2, locArr, similarArr);
	}

	/**
	 * input:str1,str2 计算2个字符串之间的相似度
	 */
	public double getSimilar(String str1, String str2, Word2VEC w) throws IOException {

		double ret = 0.0;
		// 创建向量空间模型，使用map实现，主键为词项，值为长度为2的数组，存放着对应词项在字符串中的出现次数
		Map<String, int[]> vectorSpace = new HashMap<String, int[]>();
		int[] itemCountArray = null;// 为了避免频繁产生局部变量，所以将itemCountArray声明在此
		Iterator iter;
		double vector1Modulo = 0.00;// 向量1的模
		double vector2Modulo = 0.00;// 向量2的模
		double vectorProduct = 0.00; // 向量积
		List<String> list1,list1_temp,list2,list2_temp,temp1,temp2;
		
		StringHandler sh = new StringHandler();
		
		list1_temp = sh.stringToArray(str1);
		list2_temp = sh.stringToArray(str2);
		
		/*
		//使用word2vec扩充语义
		temp1 = sh.stringToArray(str1);
		temp2 = sh.stringToArray(str2);
		list1 = sh.extendWord(w, temp1);
		list2 = sh.extendWord(w, temp2);
		*/
		list1 = sh.deleteStopWords(list1_temp, Conf.stopWordsPath);
		list2 = sh.deleteStopWords(list2_temp, Conf.stopWordsPath);
		
		int i,n;
		n = list1.size();
		for (i = 0; i < n; ++i) {
			if (vectorSpace.containsKey(list1.get(i)))
				++(vectorSpace.get(list1.get(i))[0]);
			else {
				itemCountArray = new int[2];
				itemCountArray[0] = 1;
				itemCountArray[1] = 0;
				vectorSpace.put(list1.get(i), itemCountArray);
			}
		}
		
		// 对str2处理

		n = list2.size();
		for (i = 0; i < n; ++i) {
			if (vectorSpace.containsKey(list2.get(i)))
				++(vectorSpace.get(list2.get(i))[1]);
			else {
				itemCountArray = new int[2];
				itemCountArray[0] = 0;
				itemCountArray[1] = 1;
				vectorSpace.put(list2.get(i), itemCountArray);
			}
		}

		// 计算相似度
		iter = vectorSpace.entrySet().iterator();
		while (iter.hasNext()) {
			Map.Entry entry = (Map.Entry) iter.next();
			itemCountArray = (int[]) entry.getValue();
			vector1Modulo += itemCountArray[0] * itemCountArray[0];
			vector2Modulo += itemCountArray[1] * itemCountArray[1];
			vectorProduct += itemCountArray[0] * itemCountArray[1];
		}
		vector1Modulo = Math.sqrt(vector1Modulo);
		vector2Modulo = Math.sqrt(vector2Modulo);
		// 返回相似度
		ret  = (vectorProduct / (vector1Modulo * vector2Modulo));
		return ret;

	}

}

参考文献：

[1]Salton G, Lesk M E. Computer Evaluation of Indexing and Text Processing[J].Journal of the Acm, 1968, 15(1):8-36.

[2]Salton. The SMART Retrieval System—Experiments in Automatic DocumentProcessing[C]// Prentice-hall, Inc Upper Saddle River. Prentice-Hall, Inc.1971.

[3]苏增才.基于word2vec和SVMperf的网络中文文本评论信息情感分类研究［D］.河北科技大学,2015.

本文代码下载地址：

http://download.csdn.net/detail/u013473512/9742055

https://github.com/Emmitte/DocDistance

欢迎关注“程序杂货铺”公众号，里面有精彩内容，欢迎大家收看^_^