文档章节

利用pfgrowth算法查找相关词

Harry_sir
 Harry_sir
发布于 2017/06/29 16:36
字数 1971
阅读 6
收藏 0

相关词查找: 例如在一批关于“一带一路”关键词的语料中,找出“一带一路”的相关词(如丝绸之路 习近平 等)。

【方案一】 利用关联规则中pfgrowth算法,输出与“一带一路”相关的规则。由于输出规则的一种意义是: 在Number(Number>minsupport)篇文章中,与 “一带一路”同时出现的词汇。若输出规则中词汇有意义,则Number越大,同规则中的词与“一带一路”越具有相关性。 在测试中,我们大概为1500篇语料,并约定最小支持度数(minsupport)为100。

部分结果如下:如,共156篇文章中同时出现了“一带一路,习近平,高峰论坛,国家主席”。 一带一路,人文交流:106 一带一路,丝绸之路:159 一带一路,习近平,高峰论坛,国家主席:156 一带一路,习近平,国家主席:182 一带一路,高峰论坛,习近平:224 一带一路,高峰论坛,国际合作:545 一带一路,高峰论坛:609

【方案二】 在1500篇与“一带一路”相关的文章中,利用LDA主题抽取方法,输出多个主题。认为所得主题的Top词汇,作为“一带一路”的相关词。 这里是列表文本 这里是列表文本 结果如下:

国际合作 银行业 丝绸之路 投资者 人文交流 高峰论坛 国家主席 大盘 个股 韩国 沿线国家 习近平 资本 班列 人民币 一带一路 美国 基金 板块 信息 香港 产能合作 指数 新股 部长

在以上两个策略中,个人认为方案一更加准确,但是在这过程中关键在于分词的准去率和支持度数的设置。当然在该过程中,为了提高通用性,可将支持度数改为支持度,这样就不需要获得语料数量。

附pfgrowth算法代码:

public LinkedList<LinkedList<String>> readF1(String OriginalPath) throws IOException {
	LinkedList<LinkedList<String>> records = new LinkedList<LinkedList<String>>();
	// String filePath="scripts/clustering/canopy/canopy.dat";
	String filePath = PathConfig.SegDocsPath + "hebing.txt";
	BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(filePath)));
	for (String line = br.readLine(); line != null; line = br.readLine()) {
		if (line.length() == 0 || "".equals(line))
			continue;
		lineNum++;
		String[] str = line.split(",");
		LinkedList<String> litm = new LinkedList<String>();

		for (int i = 0; i < str.length; i++) {
				litm.add(str[i].trim());
		}
		litm = removeDuplicatedElements(litm);
		records.add(litm);

	}
	br.close();
	return records;
}

// linklist去重
public static LinkedList<String> removeDuplicatedElements(LinkedList<String> list) {
	HashSet<String> set = new HashSet<String>();
	Iterator<String> iter = list.listIterator();
	while (iter.hasNext() && !(iter.equals(","))) {
		String str = (String) iter.next();
		if (!set.contains(str))
			set.add(str);
		else
			iter.remove();
	}
	return list;
}

// 创建表头链
public LinkedList<TreeNode2> buildHeaderLink(LinkedList<LinkedList<String>> records, double support) {
	LinkedList<TreeNode2> header = null;
	if (records.size() > 0) {
		header = new LinkedList<TreeNode2>();
	} else {
		return null;
	}
	Map<String, TreeNode2> map = new HashMap<String, TreeNode2>();
	for (LinkedList<String> items : records) {

		for (String item : items) {
			// 如果存在数量增1,不存在则新增
			if (map.containsKey(item)) {
				map.get(item).Sum(1);
			} else {
				TreeNode2 node = new TreeNode2();
				node.setName(item);
				node.setCount(1);
				map.put(item, node);
			}
		}
	}
	// 把支持度大于(或等于)minSup的项加入到F1中
	Set<String> names = map.keySet();
	for (String name : names) {
		TreeNode2 tnode = map.get(name);
		if (tnode.getCount() > support*lineNum) {
			header.add(tnode);
		}
	}
	sort(header);

	String test = "ddd";
	return header;
}

// 选择法排序,如果次数相等,则按名字排序,字典顺序,先小写后大写
public List<TreeNode2> sort(List<TreeNode2> list) {
	int len = list.size();
	for (int i = 0; i < len; i++) {

		for (int j = i + 1; j < len; j++) {
			TreeNode2 node1 = list.get(i);
			TreeNode2 node2 = list.get(j);
			if (node1.getCount() < node2.getCount()) {
				TreeNode2 tmp = new TreeNode2();
				tmp = node2;
				list.remove(j);
				// list指定位置插入,原来的>=j元素都会往下移,不会删除,所以插入前要删除掉原来的元素
				list.add(j, node1);
				list.remove(i);
				list.add(i, tmp);
			}
			// 如果次数相等,则按名字排序,字典顺序,先小写后大写
			if (node1.getCount() == node2.getCount()) {
				String name1 = node1.getName();
				String name2 = node2.getName();
				int flag = name1.compareTo(name2);
				if (flag > 0) {
					TreeNode2 tmp = new TreeNode2();
					tmp = node2;
					list.remove(j);
					// list指定位置插入,原来的>=j元素都会往下移,不会删除,所以插入前要删除掉原来的元素
					list.add(j, node1);
					list.remove(i);
					list.add(i, tmp);
				}

			}
		}
	}

	return list;
}

// 选择法排序,降序,如果同名按L 中的次序排序
public List<String> itemsort(LinkedList<String> lis, List<TreeNode2> header) {
	// List<String> list=new ArrayList<String>();
	// 选择法排序
	int len = lis.size();
	for (int i = 0; i < len; i++) {
		for (int j = i + 1; j < len; j++) {
			String key1 = lis.get(i);
			String key2 = lis.get(j);
			Integer value1 = findcountByname(key1, header);
			if (value1 == -1)
				continue;
			Integer value2 = findcountByname(key2, header);
			if (value2 == -1)
				continue;
			if (value1 < value2) {
				String tmp = key2;
				lis.remove(j);
				lis.add(j, key1);
				lis.remove(i);
				lis.add(i, tmp);
			}
			if ((value1 == value2) && (ordermap.get(key2) != null) && (ordermap.get(key1) != null)) {
				// System.err.println("****"+key2+"****"+ordermap.get(key2));
				int v1 = ordermap.get(key1);
				int v2 = ordermap.get(key2);
				// System.err.println("****"+key2+"****"+v2);
				if (v1 > v2) {
					String tmp = key2;
					lis.remove(j);
					lis.add(j, key1);
					lis.remove(i);
					lis.add(i, tmp);
				}
			}
		}
	}
	return lis;
}

public Integer findcountByname(String itemname, List<TreeNode2> header) {
	Integer count = -1;
	for (TreeNode2 node : header) {
		if (node.getName().equals(itemname)) {
			count = node.getCount();
		}
	}
	return count;
}

/**
 * 
 * [@param](https://my.oschina.net/u/2303379) records
 *            构建树的记录,如I1,I2,I3
 * [@param](https://my.oschina.net/u/2303379) header
 *            韩书中介绍的表头
 * [@return](https://my.oschina.net/u/556800) 返回构建好的树
 */
public TreeNode2 builderFpTree(LinkedList<LinkedList<String>> records, List<TreeNode2> header) {

	TreeNode2 root;
	if (records.size() <= 0) {
		return null;
	}
	root = new TreeNode2();
	for (LinkedList<String> items : records) {
		itemsort(items, header);
		addNode(root, items, header);
	}
	String dd = "dd";
	String test = dd;
	return root;
}

// 当已经有分枝存在的时候,判断新来的节点是否属于该分枝的某个节点,或全部重合,递归
public TreeNode2 addNode(TreeNode2 root, LinkedList<String> items, List<TreeNode2> header) {
	if (items.size() <= 0)
		return null;
	String item = items.poll();
	// 当前节点的孩子节点不包含该节点,那么另外创建一支分支。
	TreeNode2 node = root.findChild(item);
	if (node == null) {
		node = new TreeNode2();
		node.setName(item);
		node.setCount(1);
		node.setParent(root);
		root.addChild(node);

		// 加将各个节点加到链头中
		for (TreeNode2 head : header) {
			if (head.getName().equals(item)) {
				while (head.getNextHomonym() != null) {
					head = head.getNextHomonym();
				}
				head.setNextHomonym(node);
				break;
			}
		}
		// 加将各个节点加到链头中
	} else {
		node.setCount(node.getCount() + 1);
	}

	addNode(node, items, header);
	return root;
}

// 从叶子找到根节点,递归之
public void toroot(TreeNode2 node, LinkedList<String> newrecord) {
	if (node.getParent() == null)
		return;
	String name = node.getName();
	newrecord.add(name);
	toroot(node.getParent(), newrecord);
}

// 对条件FP-tree树进行组合,以求出频繁项集
public void combineItem(TreeNode2 node, LinkedList<String> newrecord, String Item) {
	if (node.getParent() == null)
		return;
	String name = node.getName();
	newrecord.add(name);
	toroot(node.getParent(), newrecord);
}

// fp-growth
public void fpgrowth(LinkedList<LinkedList<String>> records, String item, double support, String inputkeyword) {
	// 保存新的条件模式基的各个记录,以重新构造FP-tree
	LinkedList<LinkedList<String>> newrecords = new LinkedList<LinkedList<String>>();
	// 构建链头
	LinkedList<TreeNode2> header = buildHeaderLink(records, support);
	// 创建FP-Tree
	TreeNode2 fptree = builderFpTree(records, header);
	// 结束递归的条件
	if (header.size() <= 0 || fptree == null) {
		// System.out.println("-----------------");
		return;
	}
	// 打印结果,输出频繁项集
	if (item != null) {
		// 寻找条件模式基,从链尾开始
		for (int i = header.size() - 1; i >= 0; i--) {
			TreeNode2 head = header.get(i);
			String itemname = head.getName();
			Integer count = 0;
			while (head.getNextHomonym() != null) {
				head = head.getNextHomonym();
				// 叶子count等于多少,就算多少条记录
				count = count + head.getCount();

			}
			// 打印频繁项集
			if (head.getName().contains(inputkeyword) || item.contains(inputkeyword)  && (double)count/lineNum >= support) {
				System.out.println(head.getName() + "," + item + ":" + (double)count/lineNum+":"+count);
			}

		}
	}
	// 寻找条件模式基,从链尾开始
	for (int i = header.size() - 1; i >= 0; i--) {
		TreeNode2 head = header.get(i);
		String itemname;
		// 再组合
		if (item == null) {
			itemname = head.getName();
		} else {
			itemname = head.getName() + "," + item;
		}

		while (head.getNextHomonym() != null) {
			head = head.getNextHomonym();
			// 叶子count等于多少,就算多少条记录
			Integer count = head.getCount();
			for (int n = 0; n < count; n++) {
				LinkedList<String> record = new LinkedList<String>();
				toroot(head.getParent(), record);
				newrecords.add(record);
			}
		}
		fpgrowth(newrecords, itemname, support, inputkeyword);
	}
}

// 保存次序
public void orderF1(LinkedList<TreeNode2> orderheader) {
	for (int i = 0; i < orderheader.size(); i++) {
		TreeNode2 node = orderheader.get(i);
		ordermap.put(node.getName(), i);
	}
}

public void pfGrowthMain(double support, String OriginalPath, String inputkeyword) throws Exception {
	// 关联规则
	Myfptree2 fpg = new Myfptree2();
	LinkedList<LinkedList<String>> records = fpg.readF1(OriginalPath);
	LinkedList<TreeNode2> orderheader = fpg.buildHeaderLink(records, support);
	fpg.orderF1(orderheader);
	fpg.fpgrowth(records, null, support, inputkeyword);
}

public class TreeNode2 implements Comparable<TreeNode2>{
private String name; // 节点名称
private Integer count; // 计数
private TreeNode2 parent; // 父节点
private List<TreeNode2> children; // 子节点
private TreeNode2 nextHomonym; // 下一个同名节点
public TreeNode2() {
}

public String getName() {  
    return name;  
}  

public void setName(String name) {  
    this.name = name;  
}  

public Integer getCount() {  
    return count;  
}  

public void setCount(Integer count) {  
    this.count = count;  
}  
public void Sum(Integer count) {  
    this.count =this.count+count;  
}  
public TreeNode2 getParent() {  
    return parent;  
}  

public void setParent(TreeNode2 parent) {  
    this.parent = parent;  
}  

public List<TreeNode2> getChildren() {  
    return children;  
}  

public void setChildren(List<TreeNode2> children) {  
    this.children = children;  
}  

public TreeNode2 getNextHomonym() {  
    return nextHomonym;  
}  

public void setNextHomonym(TreeNode2 nextHomonym) {  
    this.nextHomonym = nextHomonym;  
}  
/** 
 * 添加一个节点 
 * [@param](https://my.oschina.net/u/2303379) child 
 */  
public void addChild(TreeNode2 child) {  
    if (this.getChildren() == null) {  
        List<TreeNode2> list = new ArrayList<TreeNode2>();  
        list.add(child);  
        this.setChildren(list);  
    } else {  
        this.getChildren().add(child);  
    }  
}  
/** 
*  是否存在着该节点,存在返回该节点,不存在返回空 
* [@param](https://my.oschina.net/u/2303379) name 
* @return 
*/  
public TreeNode2 findChild(String name) {  
    List<TreeNode2> children = this.getChildren();  
    if (children != null) {  
        for (TreeNode2 child : children) {  
            if (child.getName().equals(name)) {  
                return child;  
            }  
        }  
    }  
    return null;  
}  


public int compareTo(TreeNode2 arg0) {  
    // TODO Auto-generated method stub  
    int count0 = arg0.getCount();  
    // 跟默认的比较大小相反,导致调用Arrays.sort()时是按降序排列  
    return count0 - this.count;  
}  

}

参考:http://blog.csdn.net/javastart/article/details/50527592

© 著作权归作者所有

上一篇: 文本相似度计算
下一篇: 函数应用示例
Harry_sir
粉丝 16
博文 80
码字总数 48004
作品 0
朝阳
其他
私信 提问
【面试被虐】腾讯面试必备题解析:游戏中的敏感词过滤是如何实现的?

文末有面试资料免费领取 小秋今天去面试了,面试官问了一个与敏感词过滤算法相关的问题,然而小秋对敏感词过滤算法一点也没听说过。于是,有了以下事情的发生….. 面试官开怼 面试官:玩过王...

我最喜欢三大框架
05/09
22
0
中文分词常用方法简述

中文分词 就是将一句话分解成一个词一个词,英文中可以用空格来做,而中文需要用一些技术来处理。 三类分词算法: 1. 基于字符串匹配: 将汉字串与词典中的词进行匹配,如果在词典中找到某个...

不会停的蜗牛
2017/10/11
0
0
jcseg - 中文姓名识别算法

jcseg支持中文姓名的识别。 但是并不是什么很具有新意的算法,或者说需要经过一大版的数学公式计算才能实现的。 jcseg的姓名识别算法很简单,但是从实际效益来看,确实达到了我预期的效果。 ...

狮子的魂
2012/11/19
4.5K
0
基于腾讯AI Lab词向量进行未知词、短语向量补齐与域内相似词搜索

AI Lab开源大规模高质量中文词向量数据,800万中文词随你用,质量非常高,就是一个词向量.txt文件都有16G之多,太夸张了。。不过的确非常有特点: ⒈ 覆盖率(Coverage): 该词向量数据包含...

火力全開
2018/12/19
153
0
php使用前缀树实现关键词查找

之前旧的php系统有一个关键词查找和敏感词过滤的功能,直接使用了如下代码实现, 随着关键词增多,性能上有点拖后腿,一直想优化一下性能。 刚好从网上看到一个比较简单的java版本"利用利用字...

penngo
07/04
24
0

没有更多内容

加载失败,请刷新页面

加载更多

redis 内存信息解析

used_memory:由 Redis 分配器分配的内存总量,包含了redis进程内部的开销和数据占用的内存,以字节(byte)为单位 used_memory_rss:向操作系统申请的内存大小。与 top 、 ps等命令的输出一...

Canaan_
29分钟前
4
0
windows 下 python3 安装 pip setuptools

本文链接:https://blog.csdn.net/huzuxing/article/details/80807744 最近在家使用python的时候,总是报setuptools 模块未找到,于是在网上搜索了相关解决办法,但是都没有解决问题。 于是去...

开源中国首席CYO
36分钟前
4
0
数据库添加索引

mysql索引添加 navicat 步骤 - 选择表 -> 设计表 ->索引

以谁为师
46分钟前
6
0
java7与java9中的try-finally关闭资源

1.java7中的try 在java7之前,对于一些需要使用finally关闭资源的操作,会显得很臃肿. try{//}catch(Exception e){//}finally{if(xxxx != null){xxxx.close();}} 在jav...

Blueeeeeee
47分钟前
4
0
字节序转换详解

在跨平台和网络编程中我们经常会提到网络字节序和主机字节序,如果没有正确对两者进行转换,从而导致两方产生了不同的解释,就会出现意想不到的bug。 目录 0x01 概念 0x02 分类 0x03 两种字节...

无心的梦呓
57分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部