文本相似度结合PageRank算法

目标

尝试了一下把PageRank算法结合了文本相似度计算。直觉上是想把一个list里,和大家都比较靠拢的文本可能最后的PageRank值会比较大。因为如果最后计算的PageRank值大,说明有比较多的文本和他的相似度值比较高,或者有更多的文本向他靠拢。这样是不是就可以得到一些相对核心的文本,或者相对代表性的文本?如果是要在整堆文本里切分一些关键的词做token,那么每个token在每份文本里的权重就可以不一样,那么是否就可以得到比较核心的token,来给这些文本打标签?当然,分词切词的时候都是要用工具过滤掉stopword的。

我也只是想尝试一下这个想法,就简单实现了整个过程。可能实现上还有问题。我的结果是最后大家的PageRank值都非常接近。如:

5.626742067958352, 5.626742066427658, 5.626742070495978, 5.626742056768215, 5.626742079766638

选5,10,20,50都差不多。都非常接近。主要在设置PageRank定制迭代的那个DISTANCE值,值越接近0,迭代次数越多,经过很多次游走之后,文本之间的关系都很相近,各自的pagerank值相差不大。如果调成0.5这样的级别,可能迭代了4次左右就停下来了,互相之间差距会大一些。具体看自己的需求来控制这个距离参数了。

代码实现

文本之间的相似度计算用的是余弦距离,先哈希过。下面是计算两个List<String>的余弦距离代码:

package dcd.academic.recommend;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

import dcd.academic.util.StdOutUtil;

public class CosineDis {

	public static double getSimilarity(ArrayList<String> doc1, ArrayList<String> doc2) {
		if (doc1 != null && doc1.size() > 0 && doc2 != null && doc2.size() > 0) {

			Map<Long, int[]> AlgorithmMap = new HashMap<Long, int[]>();

			for (int i = 0; i < doc1.size(); i++) {
				String d1 = doc1.get(i);
				long sIndex = hashId(d1);
				int[] fq = AlgorithmMap.get(sIndex);
				if (fq != null) {
					fq[0]++;
				} else {
					fq = new int[2];
					fq[0] = 1;
					fq[1] = 0;
					AlgorithmMap.put(sIndex, fq);
				}
			}

			for (int i = 0; i < doc2.size(); i++) {
				String d2 = doc2.get(i);
				long sIndex = hashId(d2);
				int[] fq = AlgorithmMap.get(sIndex);
				if (fq != null) {
					fq[1]++;
				} else {
					fq = new int[2];
					fq[0] = 0;
					fq[1] = 1;
					AlgorithmMap.put(sIndex, fq);
				}

			}

			Iterator<Long> iterator = AlgorithmMap.keySet().iterator();
			double sqdoc1 = 0;
			double sqdoc2 = 0;
			double denominator = 0;
			while (iterator.hasNext()) {
				int[] c = AlgorithmMap.get(iterator.next());
				denominator += c[0] * c[1];
				sqdoc1 += c[0] * c[0];
				sqdoc2 += c[1] * c[1];
			}

			return denominator / Math.sqrt(sqdoc1 * sqdoc2);
		} else {
			return 0;
		}
	}

	public static long hashId(String s) {
		long seed = 131; // 31 131 1313 13131 131313 etc.. BKDRHash
		long hash = 0;
		for (int i = 0; i < s.length(); i++) {
			hash = (hash * seed) + s.charAt(i);
		}
		return hash;
	}

	public static void main(String[] args) {
		ArrayList<String> t1 = new ArrayList<String>();
		ArrayList<String> t2 = new ArrayList<String>();
		t1.add("sa");
		t1.add("dfg");
		t1.add("df");

		t2.add("gfd");
		t2.add("sa");

		StdOutUtil.out(getSimilarity(t1, t2));
	}
}

利用上面这个类,根据文本之间的相似度,为每份文本计算得到一个向量(最后要归一一下),用来初始化PageRank的起始矩阵。我用的数据是我solr里的论文标题+摘要的文本,我是通过SolrjHelper这个类去取得了一个List<String>。你想替换的话把这部分换成自己想测试的String列就可以了。下面是读取数据,生成向量给PageRank类的代码:

package dcd.academic.recommend;

import java.io.IOException;
import java.net.UnknownHostException;
import java.util.ArrayList;
import java.util.List;

import dcd.academic.mongodb.MyMongoClient;
import dcd.academic.solrj.SolrjHelper;
import dcd.academic.util.StdOutUtil;
import dcd.academic.util.StringUtil;

import com.mongodb.BasicDBList;
import com.mongodb.BasicDBObject;
import com.mongodb.DBCollection;
import com.mongodb.DBCursor;
import com.mongodb.DBObject;

public class BtwPublication {

	public static final int NUM = 20;

	public static void main(String[] args) throws IOException{
		BtwPublication bp = new BtwPublication();
		//bp.updatePublicationForComma();
		PageRank pageRank = new PageRank(bp.getPagerankS("random"));
		pageRank.doPagerank();
	}

	public double getDist(String pub1, String pub2) throws IOException {
		if (pub1 != null && pub2 != null) {
			ArrayList<String> doc1 = StringUtil.getTokens(pub1);
			ArrayList<String> doc2 = StringUtil.getTokens(pub2);
			return CosineDis.getSimilarity(doc1, doc2);
		} else {
			return 0;
		}
	}

//	public List<Map<String, String>> getPubs(String name) {
//
//	}

	public List<List<Double>> getPagerankS(String text) throws IOException {
		SolrjHelper helper = new SolrjHelper(1);
		List<String> pubs = helper.getPubsByTitle(text, 0, NUM);
		List<List<Double>> s = new ArrayList<List<Double>>();
		for (String pub : pubs) {
			List<Double> tmp_row = new ArrayList<Double>();
			double total = 0.0;
			for (String other : pubs) {
				if (!pub.equals(other)) {
					double tmp = getDist(pub, other);
					tmp_row.add(tmp);
					total += tmp;
				} else {
					tmp_row.add(0.0);
				}
			}
			s.add(getNormalizedRow(tmp_row, total));
		}
		return s;
	}

	public List<Double> getNormalizedRow(List<Double> row, double d) {
		List<Double> res = new ArrayList<Double>();
		for (int i = 0; i < row.size(); i ++) {
			res.add(row.get(i) / d);
		}
		StdOutUtil.out(res.toString());
		return res;
	}
}

最后这个是PageRank类,部分参数可以自己再设置:

package dcd.academic.recommend;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import dcd.academic.util.StdOutUtil;

public class PageRank {
	private static final double ALPHA = 0.85;
	private static final double DISTANCE = 0.0000001;
	private static final double MUL = 10;

	public static int SIZE;
	public static List<List<Double>> s;

	PageRank(List<List<Double>> s) {
		this.SIZE = s.get(0).size();
		this.s = s;
	}

	public static void doPagerank() {
		List<Double> q = new ArrayList<Double>();
		for (int i = 0; i < SIZE; i ++) {
			q.add(new Random().nextDouble()*MUL);
		}
		System.out.println("初始的向量q为:");
		printVec(q);
		System.out.println("初始的矩阵G为:");
		printMatrix(getG(ALPHA));
		List<Double> pageRank = calPageRank(q, ALPHA);
		System.out.println("PageRank为:");
		printVec(pageRank);
		System.out.println();
	}

	/**
	 * 打印输出一个矩阵
	 *
	 * @param m
	 */
	public static void printMatrix(List<List<Double>> m) {
		for (int i = 0; i < m.size(); i++) {
			for (int j = 0; j < m.get(i).size(); j++) {
				System.out.print(m.get(i).get(j) + ", ");
			}
			System.out.println();
		}
	}

	/**
	 * 打印输出一个向量
	 *
	 * @param v
	 */
	public static void printVec(List<Double> v) {
		for (int i = 0; i < v.size(); i++) {
			System.out.print(v.get(i) + ", ");
		}
		System.out.println();
	}

	/**
	 * 获得一个初始的随机向量q
	 *
	 * @param n
	 *            向量q的维数
	 * @return 一个随机的向量q,每一维是0-5之间的随机数
	 */
	public static List<Double> getInitQ(int n) {
		Random random = new Random();
		List<Double> q = new ArrayList<Double>();
		for (int i = 0; i < n; i++) {
			q.add(new Double(5 * random.nextDouble()));
		}
		return q;
	}

	/**
	 * 计算两个向量的距离
	 *
	 * @param q1
	 *            第一个向量
	 * @param q2
	 *            第二个向量
	 * @return 它们的距离
	 */
	public static double calDistance(List<Double> q1, List<Double> q2) {
		double sum = 0;

		if (q1.size() != q2.size()) {
			return -1;
		}

		for (int i = 0; i < q1.size(); i++) {
			sum += Math.pow(q1.get(i).doubleValue() - q2.get(i).doubleValue(),
					2);
		}
		return Math.sqrt(sum);
	}

	/**
	 * 计算pagerank
	 *
	 * @param q1
	 *            初始向量
	 * @param a
	 *            alpha的值
	 * @return pagerank的结果
	 */
	public static List<Double> calPageRank(List<Double> q1, double a) {

		List<List<Double>> g = getG(a);
		List<Double> q = null;
		while (true) {
			q = vectorMulMatrix(g, q1);
			double dis = calDistance(q, q1);
			System.out.println(dis);
			if (dis <= DISTANCE) {
				System.out.println("q1:");
				printVec(q1);
				System.out.println("q:");
				printVec(q);
				break;
			}
			q1 = q;
		}
		return q;
	}

	/**
	 * 计算获得初始的G矩阵
	 *
	 * @param a
	 *            为alpha的值,0.85
	 * @return 初始矩阵G
	 */
	public static List<List<Double>> getG(double a) {
		List<List<Double>> aS = numberMulMatrix(s, a);
		List<List<Double>> nU = numberMulMatrix(getU(), (1 - a) / SIZE);
		List<List<Double>> g = addMatrix(aS, nU);
		return g;
	}

	/**
	 * 计算一个矩阵乘以一个向量
	 *
	 * @param m
	 *            一个矩阵
	 * @param v
	 *            一个向量
	 * @return 返回一个新的向量
	 */
	public static List<Double> vectorMulMatrix(List<List<Double>> m,
			List<Double> v) {
		if (m == null || v == null || m.size() <= 0
				|| m.get(0).size() != v.size()) {
			return null;
		}

		List<Double> list = new ArrayList<Double>();
		for (int i = 0; i < m.size(); i++) {
			double sum = 0;
			for (int j = 0; j < m.get(i).size(); j++) {
				double temp = m.get(i).get(j).doubleValue()
						* v.get(j).doubleValue();
				sum += temp;
			}
			list.add(sum);
		}

		return list;
	}

	/**
	 * 计算两个矩阵的和
	 *
	 * @param list1
	 *            第一个矩阵
	 * @param list2
	 *            第二个矩阵
	 * @return 两个矩阵的和
	 */
	public static List<List<Double>> addMatrix(List<List<Double>> list1,
			List<List<Double>> list2) {
		List<List<Double>> list = new ArrayList<List<Double>>();
		if (list1.size() != list2.size() || list1.size() <= 0
				|| list2.size() <= 0) {
			return null;
		}
		for (int i = 0; i < list1.size(); i++) {
			list.add(new ArrayList<Double>());
			for (int j = 0; j < list1.get(i).size(); j++) {
				double temp = list1.get(i).get(j).doubleValue()
						+ list2.get(i).get(j).doubleValue();
				list.get(i).add(new Double(temp));
			}
		}
		return list;
	}

	/**
	 * 计算一个数乘以矩阵
	 *
	 * @param s
	 *            矩阵s
	 * @param a
	 *            double类型的数
	 * @return 一个新的矩阵
	 */
	public static List<List<Double>> numberMulMatrix(List<List<Double>> s,
			double a) {
		List<List<Double>> list = new ArrayList<List<Double>>();

		for (int i = 0; i < s.size(); i++) {
			list.add(new ArrayList<Double>());
			for (int j = 0; j < s.get(i).size(); j++) {
				double temp = a * s.get(i).get(j).doubleValue();
				list.get(i).add(new Double(temp));
			}
		}
		return list;
	}

	/**
	 * 初始化U矩阵,全1
	 *
	 * @return U
	 */
	public static List<List<Double>> getU() {
		List<Double> row = new ArrayList<Double>();
		for (int i = 0; i < SIZE; i ++) {
			row.add(new Double(1));
		}

		List<List<Double>> s = new ArrayList<List<Double>>();
		for (int j = 0; j < SIZE; j ++) {
			s.add(row);
		}
		return s;
	}
}

下面是我一次实验结果的数据,我设置了五分文本,这样看起来比较短:

[0.0, 0.09968643574761415, 0.2601130421632277, 0.31094706119099713, 0.32925346089816093]
[0.1315115598803241, 0.0, 0.23650307622882252, 0.2827229880685279, 0.34926237582232544]
[0.13521235055030142, 0.09318868159350341, 0.0, 0.3996835314966943, 0.3719154363595009]
[0.1389453620825689, 0.0957614822411479, 0.34357346750710194, 0.0, 0.4217196881691813]
[0.14612484353723476, 0.11749453142051332, 0.31752920814285096, 0.4188514168994011, 0.0]
初始的向量q为:
8.007763265073303, 3.1232982446687387, 1.1722525763669134, 5.906625842576609, 9.019220483814852,
初始的矩阵G为:
0.030000000000000006, 0.11473347038547205, 0.2510960858387436, 0.2943050020123476, 0.30986544176343683,
0.14178482589827548, 0.030000000000000006, 0.23102761479449913, 0.2703145398582487, 0.3268730194489766,
0.1449304979677562, 0.10921037935447789, 0.030000000000000006, 0.36973100177219015, 0.3461281209055758,
0.14810355777018358, 0.11139725990497573, 0.3220374473810367, 0.030000000000000006, 0.38846173494380415,
0.15420611700664955, 0.12987035170743633, 0.29989982692142336, 0.38602370436449096, 0.030000000000000006,
8.215210604296416
2.1786836521210637
0.6343362349619535
0.19024536572818584
0.05836227176176904
0.018354791916908083
0.0059297512567364945
0.0019669982458251243
6.679891158687752E-4
2.312017647733628E-4
8.117199104238135E-5
2.8787511843006215E-5
1.0279598478348542E-5
3.6872987746593366E-6
1.3264993458811192E-6
4.780938295685138E-7
1.7251588746973008E-7
6.229666266632005E-8
q1:
5.62674207030434, 5.626742074589739, 5.626742063777632, 5.626742101012727, 5.626742037269133,
q:
5.626742067958352, 5.626742066427658, 5.626742070495978, 5.626742056768215, 5.626742079766638,
PageRank为:
5.626742067958352, 5.626742066427658, 5.626742070495978, 5.626742056768215, 5.626742079766638, 
时间: 2024-11-15 15:06:43

文本相似度结合PageRank算法的相关文章

从赌钱游戏看PageRank算法

谈到并行计算应用,会有人想到PageRank算法,我们有成千上万的网页分析链接关系确定排名先后,借助并行计算完成 是一个很好的场景.长期以来,Google的创始发明PageRank算法吸引了很多人学习研究,据说当年Google创始者兴奋的找到 Yahoo!公司,说他们找到一种更好的搜索引擎算法,但是被Yahoo!公司技术人员泼了冷水,说他们关心的不是更好的技术, 而是搜索的盈利.后来Google包装成了"更先进技术的新一代搜索引擎"的身份,逐渐取代了市场,并实现了盈利. 由于PageR

文本相似度的最后的精准率和召回率怎么实现啊?

问题描述 文本相似度的最后的精准率和召回率怎么实现啊? 利用tf-idf算法和余弦相似度算法计算了文本之间的余弦相似系数,可是结果出来了,不知道结果的好坏啊,请问大神们有没有知道怎么评测结果的好坏啊?上网查到可以计算精准率与召回率,这个用Python怎么实现啊? 解决方案 Python没有相应的例子,建议你根据以下内容自己写吧 http://blog.sina.com.cn/s/blog_4b59de070100ehl7.html

性能测试-文本相似度分析的性能检测?

问题描述 文本相似度分析的性能检测? 利用tf-idf算法和余弦相似度算法计算了文本之间的相似度,可是结果出来了,不知道结果的好坏啊,请问大神们有没有知道怎么评测结果的好坏啊? 解决方案 分析算法复杂度.如果算法太复杂,分析起来有困难,评价算法的好坏就是给数据量大小不等的测试样本,运行得到耗费的时间. 对数据量和运行时间的曲线拟合. 糟糕的算法就是随着数据量的增加,时间或者存储的开销呈现几何级数地发散出去. 好的算法是,时间随着数据的增加,呈现常数.收敛在某个值或者是线性增加的. 解决方案二:

【BABY夜谈大数据】计算文本相似度

简单讲解 上一章有提到过[基于关键词的空间向量模型]的算法,将用户的喜好以文档描述并转换成向量模型,对商品也是这么处理,然后再通过计算商品文档和用户偏好文档的余弦相似度. 文本相似度计算在信息检索.数据挖掘.机器翻译.文档复制检测等领域有着广泛的应用. 比如舆论控制,我们假设你开发了一个微博网站,并且已经把世界上骂人的句子都已经收录进了数据库,那么当一个用户发微博时会先跟骂人句子的数据库进行比较,如果符合里面的句子就不让用户发出. 通常情况下,很多工程师就会想到用like或者where的sql语

《R的极客理想——高级开发篇 A》一一2.2 PageRank算法R语言实现

2.2 PageRank算法R语言实现 问题 如何用R语言实现PageRank算法? 引言 Google搜索,早已成为我每天必用的工具,我无数次惊叹它搜索结果的准确性.同时,我也在做Google的SEO,推广自己的博客.经过几个月尝试,我的博客PR到2了,外链也有几万个.总结下来,还是感叹PageRank的神奇.笔者认为PageRank是改变互联网的算法!2.2.1 PageRank算法介绍 PageRank是Google专有的算法,用于衡量特定网页相对于搜索引擎索引中的其他网页而言的重要程度.

PageRank 算法解析

PageRank 算法解析    Jun 26, 2005 来源:未详         什么是PageRank? PageRank是Google衡量网页重要性的工具,测量值范围为从1至10分别表示某网页的重要性.在Google工具栏可以随时获得某网页的PageRank值.在这里我们将PageRank的一些特殊之处,从而对其能够获得较为深入的了解,使广大用户能够更好的使用和了解Googel. 网站 排名的历史渊源 上世纪90年代早期网络刚刚兴起之时,每天都有大量的含有特别行业内容的站点发布于网上.

文本相似度判定

简介 针对文本相似判定,本文提供余弦相似度和SimHash两种算法,并根据实际项目遇到的一些问题,给出相应的解决方法.经过实际测试表明:余弦相似度算法适合于短文本,而SimHash算法适合于长文本,并且能应用于大数据环境中. 余弦相似度 原理 余弦定理:                    图-1 余弦定理图示 性质: 余弦值的范围在[-1,1]之间,值越趋近于1,代表两个向量的方向越趋近于0°,他们的方向更加一致,相应的相似度也越高.需要指出的是,在文本相似度判定中,因为文本特征向量定义的特

【原创】机器学习之PageRank算法应用与C#实现(1)算法介绍

考虑到知识的复杂性,连续性,将本算法及应用分为3篇文章,请关注,将在本月逐步发表. 1.机器学习之PageRank算法应用与C#实现(1)算法介绍 2.机器学习之PageRank算法应用与C#实现(2)球队排名应用与C#代码 3.机器学习之PageRank算法应用与C#实现(3)球队实力排名应用与C#代码  Pagerank是Google排名运算法则(排名公式)的一部分,是Google用于用来标识网页的等级/重要性的一种方法,是Google用来衡量一个网站的好坏的唯一标准.在揉合了诸如Title

跪求:算法复杂度最低的算法

问题描述 算法题:两个数组,M和N,分别存了任意个整数,从M中取一个数,从N中取一个数,如果相加等于1000,则计数为1,以此类推,求M和N中和为1000的数的个数.(M×N的复杂度的就算了,大家都知道),求算法复杂度最低的算法 解决方案 解决方案二:我对算法的复杂度不太了解,不知道怎么算的.如果先对某个数组排序,算法复杂度是O(N·logN)的话然后再遍历另一个数组,那复杂度是O(N),再用1000减去遍历出来的那个数得到差,再到排序数组中使用二分法找这个数,复杂度为O(logN)我不知道这样