数据挖掘之分类

/**

*作者：张荣华

*日期：2008-2-19

**/
随着当代计算机硬件的发展，硬件功能越来越强大，价格越来越低，企业可以记录的数据也越来越多，这些因素就为数据挖掘的普及做了比较好的前提准备，树挖掘是未来信息处理的重要技术，而且就目前而言已经取得了决定性成功而且得到了比较广泛的应用。

数据挖掘中有很多领域，分类就是其中之一，什么是分类，
分类就是把一些新得数据项映射到给定类别的中的某一个类别，比如说当我们发表一篇文章的时候，就可以自动的把这篇文章划分到某一个文章类别，一般的过程是根据样本数据利用一定的分类算法得到分类规则，新的数据过来就依据该规则进行类别的划分。

分类在数据挖掘中是一项非常重要的任务，有很多用途，比如说预测，即从历史的样本数据推算出未来数据的趋向，有一个比较著名的预测的例子就是大豆学习。再比如说分析用户行为，我们常称之为受众分析，通过这种分类，我们可以得知某一商品的用户群，对销售来说有很大的帮助。

分类器的构造方法有统计方法，机器学习方法，神经网络方法等等。常见的统计方法有knn算法，基于事例的学习方法。机器学习方法包括决策树法和归纳法，上面讲到的受众分析可以使用决策树方法来实现。神经网络方法主要是bp算法，这个俺也不太了解。


文本分类， 所谓的文本分类就是把文本进行归类，不同的文章根据文章的内容应该属于不同的类别，文本分类离不开分词，要将一个文本进行分类，首先需要对该文本进行分词，利用分词之后的的项向量作为计算因子，再使用一定的算法和样本中的词汇进行计算，从而可以得出正确的分类结果。在这个例子中，我将使用庖丁分词器对文本进行分词。

下面这个例子将使用反余弦进行词汇单元进行匹配，
第一步，训练样本：

protected Map<String, Map<String, Integer>> getClassVector(List<Category> categoryList) throws Exception {
		
		if (categoryList == null || categoryList.size() == 0) {
			if (logger.isDebugEnabled()) {
				logger.debug("The list of new categoryList which should be classified is null or size = 0");
			}
			return Collections.emptyMap();
		}
		
		Map<String, Map<String, Integer>> categoryMap = new HashMap<String, Map<String, Integer>>();
		
		Directory ramDir = new RAMDirectory();
		IndexWriter writer = new IndexWriter(ramDir, new PaodingAnalyzer(), true);
		
		for (Category cRc : categoryList) {
			for (Article item : cRc.getArticleList()) {
				
				Document doc = new Document();
				doc.add(new Field("description", item.getContent(), Field.Store.NO,
						Field.Index.TOKENIZED, TermVector.YES));
				doc.add(new Field("category", cRc.getId().toString(), Field.Store.YES, Field.Index.NO));
				writer.addDocument(doc);
			}
		}
		
		if (logger.isDebugEnabled()) {
			logger.debug("Generate the index in the memory, the size of categoryList list is " + categoryList.size());
		}
		
		writer.close();
		
		buildContentVectors(ramDir, categoryMap, "category", "description");
		return categoryMap;
		
	}

第二步：对待分类的文章进行分词（原理和样本训练类似）：

protected Map<String, Map<String, Integer>> getArticleVector(List<Article> articleList) throws Exception {
		if (articleList == null || articleList.size() == 0) {
			if (logger.isDebugEnabled()) {
				logger.debug("The list of articles which should be classified is null or size = 0");
			}
		}
		
		Map<String, Map<String, Integer>> articleMap = new HashMap<String, Map<String, Integer>>();
		
		Directory articleRamDir = new RAMDirectory();
//		IndexWriter writer = new IndexWriter(articleRamDir, new ChineseAnalyzer(), true);
		IndexWriter writer = new IndexWriter(articleRamDir, new PaodingAnalyzer(), true);
		
		for (Article article : articleList) {
			Document doc = new Document();
			doc.add(new Field("articleId", article.getId(),
					Field.Store.YES, Field.Index.NO));
			doc.add(new Field("description", article.getContent(), Field.Store.NO, Field.Index.TOKENIZED, TermVector.YES));
			writer.addDocument(doc);
		}
		
		writer.flush();
		writer.close();
		
		buildContentVectors(articleRamDir, articleMap, "articleId", "description");
		return articleMap;
	}

分类的核心算法(下面这段代码的原理来自于lucene in action)：

public double caculateVectorSpace(Map<String, Integer> articleVectorMap, Map<String, Integer> classVectorMap) {
		if (articleVectorMap == null || classVectorMap == null) {
			if (logger.isDebugEnabled()) {
				logger.debug("itemVectorMap or classVectorMap is null");
			}
			
			return 20;
		}
		
		int dotItem = 0;
		double denominatorOne = 0;
		double denominatorTwo = 0;
		
		
		for (Entry<String, Integer> entry : articleVectorMap.entrySet()) {
			String word = entry.getKey();
			double categoryWordFreq = 0;
			double articleWordFreq = 0;
			
			if (classVectorMap.containsKey(word)) {
				categoryWordFreq = classVectorMap.get(word).intValue() / classVectorMap.size();
				articleWordFreq = entry.getValue().intValue() / articleVectorMap.size();
			}
			
			dotItem += categoryWordFreq * articleWordFreq;
			denominatorOne += categoryWordFreq * categoryWordFreq;
			denominatorTwo += articleWordFreq * articleWordFreq;
		}
		
		double denominator = Math.sqrt(denominatorOne) * Math.sqrt(denominatorTwo);
		
		double ratio =  dotItem / denominator;
		
		return Math.acos(ratio);
	}

效果：
测试数据：

public static List<Category> prepareCategoryList() {
		List<Category> categoryList = new ArrayList<Category>();
		List<Article> articleList = new ArrayList<Article>();
		
		Category c = new Category();
		c.setArticleList(articleList);
		c.setId("1");
		categoryList.add(c);
		
		Article a1 = new Article();
		a1.setId("1");
		a1.setTitle("Hibernate初探");
		a1.setContent("开始看Hibernate reference,运行hibernate的test中的代码。 Environment是一个非常重要的类。它定义了很多常量，最重要的是hibernate的入口在这里。");
		
		Article a2 = new Article();
		a2.setId("2");
		a2.setTitle("Hibernate SQL方言");
		a2.setContent("PO的数据类型设置 int 还是Integer Integer 允许为 null Hibernate 既可以访问Field也可以访问Property");
		
		Article a3 = new Article();
		a3.setId("3");
		a3.setTitle("Hibernate 杂烩");
		a3.setContent("Hibernate 中聚合函数的使用 Criteria接口的Projections类主要用于帮助Criteria接口完成数据的分组查询和统计功能:");
		
		Article a4 = new Article();
		a4.setId("4");
		a4.setTitle("Hibernate映射类型");
		a4.setContent("Hibernate映射类型Hibernate映射类型,对应的基本类型及对应的标准SQL类型");
		
		
		articleList.add(a1);
		articleList.add(a2);
		articleList.add(a3);
		articleList.add(a4);
		
		return categoryList;
	}
	
	public static List<Article> prepareArticleList() {
		List<Article> articleList = new ArrayList<Article>();
		Article a1 = new Article();
		a1.setId("1");
		a1.setTitle("Hibernate学习笔记(一)");
		a1.setContent("本笔记的内容: 分层体系结构 ORM介绍 Hibernate简介 Hibernate开发步骤 Hibernate核心API ");
		
		Article a2 = new Article();
		a2.setId("2");
		a2.setTitle("Hibernate的性能问题");
		a2.setContent("各位老大，使用hibernate做企业级别的应用，会不会有性能问题啊？比如大数据量的搜索或者客户端同时大量的请求，会不会严重影响性能啊？有没有什么好的解决办法? 谢了先!");
		
		Article a3 = new Article();
		a3.setId("3");
		a3.setTitle("Spring2.5全面支持JEE5的实现");
		a3.setContent("Spring 2.5 发布已经有一段时间了，一直没有时间研究一下，只是听说有很多方面的提升。有一点十分重要的就是全面支持JEE5风格的annotation。");
		
		Article a4 = new Article();
		a4.setId("4");
		a4.setTitle("谈谈Spring的SqlMapClientTemplate对SqlMapClientCallback");
		a4.setContent("谈谈Spring的SqlMapClientTemplate对SqlMapClientCallback的使用 ■记得以前在看SqlMapClientTemplate的源代码的时候，下面的这两段代码硬是没看懂当时我很疑惑：真的有必要用到内部匿名类这样诡异的手法么？");
		
		Article a5 = new Article();
		a5.setId("5");
		a5.setTitle("spring 2.0 学习笔记");
		a5.setContent("前几天学习hibernate!在mysql下都能正常跑出来.! 但是我一换成oracle就出现下面这种情况: 小弟不解呀..google了很多次也解决不了此问题::.希望老大门帮忙看一下哈.!!! 环境:MyEclipse5.5,hibernate2.0,spring2.0");
		
		articleList.add(a1);
		articleList.add(a2);
		articleList.add(a3);
		articleList.add(a4);
		articleList.add(a5);
		
		return articleList;
	}

以上测试代码中的数据来源于javaeye的文章。
输出：
2008-02-19 11:05:42,031 DEBUG ArticleClassifierImpl:74 - articleId=2---------acos value=1.412016112149136
2008-02-19 11:05:42,031 DEBUG ArticleClassifierImpl:74 - articleId=1---------acos value=1.3258176636680326
2008-02-19 11:05:42,031 DEBUG ArticleClassifierImpl:74 - articleId=5---------acos value=1.4244090675006476

有此可见文章id号为1,2,5的文章符合hibernate分类，事实上我们还要更进一步，假设我们有两个分类，hibernate，spring，各有5各样本，那么最后的结果应该再次作最小符合判断，acos值最小的则认为该article属于该分类，同学们可以自己做一下实验。

文本分类中有很多注意点，比如说噪音词去除（上面的代码中并包括最简单的噪音词去除功能）等，接下来我会使用knn算法改造以上代码，并使用相同的测试数据并比对测试结果。

评论

33 楼 longrm 2008-12-25  

看来我得先看看lucene

32 楼 sdh5724 2008-12-25  

楼主不错， 这样的东西就是要共享出来。有的人觉得自己明白几次名词就大吵大闹没有什么意思。我在研究HMM，bayers分类等等。 我准备自己实现。文档聚合， 分类是个很复杂的课题 这些算法都对数学功力要求很高。实际上， 这些东西， 不知道数学原理就是给代码也很难明白的。 关键是需要理解原理， 代码实现就是降低了很多难度。 知道算法了， 管他这些应用会用在什么地方， 算法是很奇妙的东西， 有时候到处都能用， 有时候一无是处。  看看我的BLOG， 有谁能想到，我用分词算法来解决违禁词汇过滤呢。

31 楼 mice123 2008-03-07  

讲SVM吧，与时俱进

30 楼 mba9001 2008-03-06  

<div class='quote_title'>hyf 写道</div><div class='quote_div'><div class='quote_title'>mba9001 写道</div><div class='quote_div'><div class='quote_title'>mochow 写道</div><div class='quote_div'><img src='../../../../../../images/smiles/icon_biggrin.gif' alt=''/>按照你的逻辑，你应该先检查你自己是否看明白我的意思没有。<br/><br/>我的意思很简单：<br/><br/>首先，分类是一类算法的集合，它包含很多种不同的算法，光统计方法的算法常见的除了knn之外，还有贝叶斯，分类是数据挖掘一个很重要的算法，并不意味着它仅仅属于数据挖掘这一个学科，还在其他很多学科有应用，其中很多领域是数据挖掘涉及不到的地方，很简单的例子，医院的医学图象处理，交通部门的各种图象处理，很多工业上的应用以及航空航天和国防上的应用等等。你是否看懂我的这个意思了呢？至于你说分类用的多不多，你认为在这个研究分类算法的文章里讨论这个有意义么？<br/><br/>其次，分类的学习，我的看法就是掌握分类的基本算法原理比去琢磨或者死记一段代码要重要的多，这样不管你换成什么语言，都可以写出代码来，而且，一旦以后需要用到这个算法的时候，根本无须拘泥于是否是数据挖掘这个领域之内，只要能解决问题就ok。就这个观点来看这篇文章，价值很低。<br/><br/>我的话完了。</div><br/><br/>看你举的几个例子,如 医院的医学图象处理，交通部门的各种图象处理<br/><span style='color: #ff0000;'><span style='color: #ff0000;'>大概可以猜出你应该是眼高手低的,顶多你是最多看了看weka的源代码而已</span>.</span><br/><br/>我也不懂多少.但我不会自认为自己就比别人高明多少.</div><p> </p><p> </p><p>老兄你是怎么猜出来的？</p><p> </p></div><p>首先向mochow道歉.语气太重．</p><p>其次,我解释一下我这样回复的原因，和回复一下其它前辈的提问，</p><p>1.三人行,必有我师.不可以随意否定别人的努力.</p><p>2.每个帖子都会找到适应的读者，君可见各书店的各类入门书非常畅销．</p><p>3.学过或看过DM相关的，都会看看weka.</p><p>4.对于视音的管理，mochow前辈应该知道，现在已出来和将会出来更多的优秀的＂媒资管理系统＂</p>

29 楼 lonlyleo 2008-03-05  

看了这些,我只觉得自己还很需要努力学习,呵呵.我还是个算法盲

28 楼 Jinfonet_DEE 2008-03-01  

期待 楼主的第三篇 利用朴素bayes定理进行分类
另外 我同意楼上的意见
谢谢楼主提供的相关知识

27 楼 bluemeteor 2008-02-25  

我不认为楼主做错或者说错了什么，这篇文章值得精华……

26 楼 ahuaxuan 2008-02-24  

谢谢mba9001，downpour，h819，corvallis的中肯的意见及建议，我也希望大家能够把注意力集中在技术方面，毕竟每个人讨论技术的方式是不一样的，我们的目的是在讨论中得到进步，希望大家看了我的文章之后能够学习到点什么，我也希望能从大家的回复中学习到什么，我们应该相互学习，而不要相互贬低。

关于第二篇文章我已经写好了，就是本文提到的使用knn算法来进行分类 http://www.iteye.com/topic/164435
第三篇文章：“利用朴素bayes定理进行分类”也正在编辑之中，谢谢大家对我的帮助

25 楼 hyf 2008-02-24  

<div class='quote_title'>mba9001 写道</div><div class='quote_div'><div class='quote_title'>mochow 写道</div><div class='quote_div'><img src='../../../../../../images/smiles/icon_biggrin.gif' alt=''/>按照你的逻辑，你应该先检查你自己是否看明白我的意思没有。<br/><br/>我的意思很简单：<br/><br/>首先，分类是一类算法的集合，它包含很多种不同的算法，光统计方法的算法常见的除了knn之外，还有贝叶斯，分类是数据挖掘一个很重要的算法，并不意味着它仅仅属于数据挖掘这一个学科，还在其他很多学科有应用，其中很多领域是数据挖掘涉及不到的地方，很简单的例子，医院的医学图象处理，交通部门的各种图象处理，很多工业上的应用以及航空航天和国防上的应用等等。你是否看懂我的这个意思了呢？至于你说分类用的多不多，你认为在这个研究分类算法的文章里讨论这个有意义么？<br/><br/>其次，分类的学习，我的看法就是掌握分类的基本算法原理比去琢磨或者死记一段代码要重要的多，这样不管你换成什么语言，都可以写出代码来，而且，一旦以后需要用到这个算法的时候，根本无须拘泥于是否是数据挖掘这个领域之内，只要能解决问题就ok。就这个观点来看这篇文章，价值很低。<br/><br/>我的话完了。</div><br/><br/>看你举的几个例子,如 医院的医学图象处理，交通部门的各种图象处理<br/><span style='color: #ff0000;'>大概可以猜出你应该是眼高手低的,顶多你是最多看了看weka的源代码而已</span>.<br/><br/>我也不懂多少.但我不会自认为自己就比别人高明多少.</div><p> </p><p> </p><p>老兄你是怎么猜出来的？</p><p> </p>

24 楼 corvallis 2008-02-24  

另外也可以看一下 Andrew Moore 的tutorial：

http://www.autonlab.org/tutorials/

如果你同时对快速实现的算法感兴趣比如如何有效的实现knn。 Andrew Moore 的Group应该是世界上最好的之一了。

23 楼 corvallis 2008-02-24  

如果对这一方面 有兴趣。
算法可以看一下 Duda 的 "pattern classification"
对于统计的方法"The element of statical learning“ 也算很经典的书。
其实我觉得在实际应用中， 更重要的是如何构建feature。 如何评估系统。 最最重要的是哪里找来"Training data". 如果想看一下现。 可以看weka的源代码， 比较基本， 虽然很慢， 每一个算法的注释都会给出基本的参考文献。

22 楼 h819 2008-02-23  

嗯，不要举着棍子打杀，即是说的不对或者不完美，也要给人说话的机会
关键是大家能学习到机会，而不是逞口舌之快，大师都是很谦虚地...

21 楼 downpour 2008-02-23  

mochow说的和ahuaxuan说的都各自在理，不要为这种文字上的歧义而争论不休了，火气都小一些嘛。

对于分类算法丝毫不了结的人，或许看啦ahuaxuan的代码会更形象得了结这是怎么回事。当然，mochow前辈可能对分类算法有深入的研究，不妨也和大家交流一下心得。大家和和气气讨论讨论岂不是更好？

20 楼 mochow 2008-02-23  

mba9001同学不要太自以为是。 还真不好意思，关于分类各种算法的代码，我还真是在若干年前自己编过，也还真没有参照过其他人的代码。

另外，你哪只眼睛看到我说自己是高手来着？

19 楼 mba9001 2008-02-22  

mochow 写道

按照你的逻辑，你应该先检查你自己是否看明白我的意思没有。

我的意思很简单：

首先，分类是一类算法的集合，它包含很多种不同的算法，光统计方法的算法常见的除了knn之外，还有贝叶斯，分类是数据挖掘一个很重要的算法，并不意味着它仅仅属于数据挖掘这一个学科，还在其他很多学科有应用，其中很多领域是数据挖掘涉及不到的地方，很简单的例子，医院的医学图象处理，交通部门的各种图象处理，很多工业上的应用以及航空航天和国防上的应用等等。你是否看懂我的这个意思了呢？至于你说分类用的多不多，你认为在这个研究分类算法的文章里讨论这个有意义么？

其次，分类的学习，我的看法就是掌握分类的基本算法原理比去琢磨或者死记一段代码要重要的多，这样不管你换成什么语言，都可以写出代码来，而且，一旦以后需要用到这个算法的时候，根本无须拘泥于是否是数据挖掘这个领域之内，只要能解决问题就ok。就这个观点来看这篇文章，价值很低。

我的话完了。

看你举的几个例子,如 医院的医学图象处理，交通部门的各种图象处理
大概可以猜出你应该是眼高手低的,顶多你是最多看了看weka的源代码而已.

我也不懂多少.但我不会自认为自己就比别人高明多少.

18 楼 ccnujzw 2008-02-20  

    有点收获。
     如果能用更少的话讲清更多的道理会更好。

     mochow 是个粗鲁的人，跟这样的人讨论，是不会有收获的。

17 楼 ahuaxuan 2008-02-20  

imjl 写道

仔细看了lz的文字，当然我不会看code的。

没看清lz要表达的意思，同意mochow的观点。

不好意思了，我比较喜欢看代码，如果您不看code的话，我想确实可能不能知道我的意思

16 楼 ahuaxuan 2008-02-20  

确实，我对数据挖掘是很不了解，不过我身边有几位同事的研究方向是数据挖掘，我不是搞这方面的，只能算是道听途说一些，实际上，我连Lucene也一窍不通。
不过我的帖子是针对您的那段代码的。你的代码里，最核心的根据TF/IDF求余弦的部分并没有给出。而且这段代码，我个人感觉没有Google黑板报的那篇文章深入本质且简洁易懂(讲算法还要了解Lucene的API，这不是干扰么)，所以补充了出来，你后来也贴出了那篇文章的截图。LuceneInAction确实不是描述数据挖掘的书，但这个例子，却和LuceneInAction里很相似，而且关键部分的代码有缺失，所以我也补充了说建议看看LuceneInAction。
嗯，也谢谢您推荐的书，呵呵。

public double caculateVector(Map<String, Integer> articleVectorMap, Map<String, Integer> classVectorMap) {
		if (articleVectorMap == null || classVectorMap == null) {
			if (logger.isDebugEnabled()) {
				logger.debug("itemVectorMap or classVectorMap is null");
			}
			
			return 20;
		}
		
		int dotItem = 0;
		int sumOfSquares = 0;
		int matchSize = 0;
		
		for (Entry<String, Integer> entry : articleVectorMap.entrySet()) {
			String word = entry.getKey();
			double categoryWordFreq = 0;
			
			if (classVectorMap.containsKey(word)) {
				categoryWordFreq = classVectorMap.get(word).intValue();
				++matchSize;
			}
			
			dotItem += categoryWordFreq;
			sumOfSquares += categoryWordFreq * categoryWordFreq;
		}
		
		double denominator;
		if (sumOfSquares == articleVectorMap.size()) {
			denominator = sumOfSquares;
		} else {
			denominator = Math.sqrt(sumOfSquares) * Math.sqrt(articleVectorMap.size());
		}
		
		double ratio =  dotItem / denominator;
		
		return Math.acos(ratio);
	}

这段代码包含在我提供的代码下载里，如果想要用的人必然会看代码，不过我也发现我的代码贴错了，就是核心代码是这一块，我提供的代码是可以运行的

fyting 写道

mochow JJ后面说了很多，耐心真是好。。。

就这种态度吗，随便说别人无知，随便侮辱贬低别人，这叫有耐心

15 楼 imjl 2008-02-20  

仔细看了lz的文字，当然我不会看code的。

没看清lz要表达的意思，同意mochow的观点。

14 楼 fyting 2008-02-20  

ahuaxuan 写道

fyting 写道

建议看Lucene In Action,或者Google的数学之美系列-余弦定理和新闻的分类

你对数据挖掘可能还不是很了解，lucene in action我当然看过，看过多次，可是lucene in action并不是描述数据挖掘的书，里面只有几页纸的内容描写到分类，但是分类是一门很大的学问，涉及很多方法，很多算法，如果你对数据挖掘有兴趣建议你到圈子里看看我推荐的书

确实，我对数据挖掘是很不了解，不过我身边有几位同事的研究方向是数据挖掘，我不是搞这方面的，只能算是道听途说一些，实际上，我连Lucene也一窍不通。
不过我的帖子是针对您的那段代码的。你的代码里，最核心的根据TF/IDF求余弦的部分并没有给出。而且这段代码，我个人感觉没有Google黑板报的那篇文章深入本质且简洁易懂(讲算法还要了解Lucene的API，这不是干扰么)，所以补充了出来，你后来也贴出了那篇文章的截图。LuceneInAction确实不是描述数据挖掘的书，但这个例子，却和LuceneInAction里很相似，而且关键部分的代码有缺失，所以我也补充了说建议看看LuceneInAction。
嗯，也谢谢您推荐的书，呵呵。
mochow JJ后面说了很多，耐心真是好。。。

ahuaxuan 写道

呵，有意见可以说出来，不用这样，这样只不过能说明你真的是一个女人，而不是马甲。