毕业设计5－－－web网页自动分类(carrot2初步研究)

最好的搜索引擎开发交流社区 http://www.zhuayu.net      

也可以加入qq群：  38707929

找不到数据挖掘的版块, 而这个课题的建立是基于STUCTS的,所以发在这里也未尝不可^_^.

        好久没写blog了,由于之前对毕业设计的要求理解错误,导致研究方向发生了偏移. 在3月7号的时候导师开了一个会才知道要做的系统是一个聚类系统, 之前研究的使用训练集产生分类器的方法是针对"自动归类"的.

       香港回来后(3月9~3月16), 开始了这个课题的研究, 这个过程中碰到种种困难. 比如vsm(向量空间模型), STC(后缀树表示法)等等要涉及一些矩阵分解(对web网页表示的降维), 基向量,特征值... 以前一直觉得学数学对软件开发毫无用处, 现在得洗洗脑子了,因为以前接触的多是web应用型项目,框架建好了,填填代码而已.

       很感谢陈黎飞博士, soulmachine, 在我学习的过程中,给予的指导.

       过几天就要交开题报告了, 所以我就先在这里总结一下我这几天的学习心得. 一开始我看了几篇陈博士给我的几篇论文, 大概对web网页聚类过程有了大概的了解.后来研究Carrot2(一个开源的聚类程序,读者可以上网查询相关信息,网址是project.carrot2.org),看的全是英文资料,比较的累,呵呵, 不够Carrot2设计的真的很好,很容易看懂, 不过对几个聚类算法(lingo, Fuzzyant...)还是要花一些功夫的

        下面我分要点进行总结.

一.  web网页聚类基本流程和框架

   这里引用的是Carrot2的一个框架, 这跟我研究的web网页自动分类是一致的.

   通过各种大型搜索引擎API获得源数据(一般至少包括一个唯一的URL地址,网页标题), 通过网页清洗,分词,提取特征项(降维作用),建立VSM, 构造STC进行聚类(如果你采用STC作为聚类算法), 聚类后就到了怎样把聚类结果展现给用户了, 这里有个很关键的问题是,如果让用户一看分类目录的标题,就知道这个类里包含那方面的内容.

    这里要补充说一下的是, Carrot2并没有中文分词功能,其默认的分词功能往往不能尽如人意.本人打算以后用中科院的ICTCLAS分词组件进行分词.

二.  基本概念解释

1.      TF：（term frequency）用关键词的次数除以网页的总字数（在一篇特定网页中）-------词权值, 用于建立VSM

2.  IDF（Inverse document frequency）：它的公式为ｌｏｇ（Ｄ／Ｄｗ）其中Ｄ是全部网页数（假定一个关键词 ｗ 在 Ｄｗ 个网页中出现过）

-------词权值, 用于建立VSM

3. TF/IDF(可以有改进,见论文TFRDF---词频相对文本频率):  在 VSM中文档被映射成由一组规范化特征项权值矢量 ,其中特征项权值常见的量化加权模型有:布尔模型、词频模型、TF IDF模型 ,我们使用效果较好的 TF  IDF 模型。这种模型认为特征词条在某文档中的重要性与其在该文档中出现的频率成正比 ,与其在其他文档中出现的频率成反比。因此它主

要考虑两个因素: ①词语频率 TF TermFrequency ,即词语在(文档中出现次数; ②词语倒排文档频率 IDF InverseDocumentFrequency ,即词语在文档集合中分布的一种量化。.

4. 频度：指一个词（或其它语义单位）在文本中出现的次数越多，则所带 的 信息量越大。

集中度：指在多类别的大量文本中，一个词只在一类或少数几类文本里出现，而在其它文本里不出现，则它所带的信息量就大，对所在文本的类别的表示能力就强。

分散度：指在某一类文本中，一个词在越多的文本中出现，即越分散，说明它信息量越大，对类别表示能力越强。

5.. 文档频率 DF、互信息 MI、信息增益 IG、期望交叉熵 CE、CHI 统计、文本证据权和优势率、特征强度------一系列特征提取的方法(目的:降维)

 

6.归一化(实际应用中各类别文本的长度很难一致，各类文本包含的字数、词数可能差别会很大，这对词频会造成直接影响，因此通常对词频作归一化处理。)   你在所有的数据中找出最大的那个数max 可以用matlab的max函数 在所有的数据中找出最小的那个数min 可以用matlab的min函数 然后把所有的数据这样计算 (x-min)/(max-min) 这样所有的数据都归一化为0到1之间的数了
这对于模式识别是很重要的一环 无论你是用BP网、多层感知器、SVM

 

7 .Stopwords：词“的”站了总词频的 80% 以上，而它对确定网页的主题几乎没有用。我们称这种词叫“应删除词”（Stopwords)，也就是说在度量相关性是不应考虑它们的频率。

8负熵:sdg (在google的数学之美系列里能找到)

 

熵：是表征热力学系统的混乱度或者是无序度大小的物理量，主要描述的是

系统的稳定状态的一个表征值。

  熵包括高熵和低熵，其中“高熵”对系统是高混乱的或者是无序的状态，“低熵”对系统是低混乱的或者是有序的状态。
 其中大多数书中主要讲到的是“负熵流”，关于负熵流的概念我的理解是：外界向系统输入能量，使系统降低的熵值超过系统内部产生的熵值的那部分熵值就是负熵流。负熵值使系统趋于平衡，稳定。

9.n元语法短语

一般來說，N-Gram模型就是假設當前詞的出現概率只同它前面的N-1個詞有關，或者說它是用前N-1個詞的出現概率去預測當前詞的出現概率(Markov Chain)。常用的N-Gram模型有uni-Gram (N=1、一元組)、bi-Gram(N=2、二元組)和tri-Gram (N=3、三元組)。

  1. 傳統檢索系統以詞庫比對法斷出索引詞，則可稱為「以詞彙為主」

(word-based)的索引詞模式。

    2. 中文系統中亦有「以字元為主」(character-based)的索引詞模式。

3. 「N-gram索引法」，N-gram為文件中任意N個連續字元，

如「中國社會」此一字串，

當N為２時將可產生

    「中國」、「國社」、「社會」三個索引詞。如此可排除或降低

「字元法」中類似

「中國」與「國中」的字串順序問題，也可省去「詞彙法」中維護詞庫的煩惱。

10.一个矩阵被因式分解成两个矩阵, 左矩阵U中所有列向量(称为基向量).

   一直没搞懂基向量(那个红坐标是怎么弄出来的)----该图的背景可以看附件Clustering SearchResults with Carrot2 的第47页

11.      KNN(K-Nearest Neighbor)

KNN法即K最近邻法，最初由Cover和Hart于1968年提出的，是一个理论上比较成熟的方法。该方法的思路非常简单直观：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。因此，采用这种方法可以较好地避免样本的不平衡问题。另外，由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。

该方法的不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。另外还有一种Reverse KNN法，能降低KNN算法的计算复杂度，提高分类的效率。

该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。

 

12. SVM法

SVM法即支持向量机(Support Vector Machine)法，由Vapnik等人于1995年提出，具有相对优良的性能指标。该方法是建立在统计学习理论基础上的机器学习方法。通过学习算法，SVM可以自动寻找出那些对分类有较好区分能力的支持向量，由此构造出的分类器可以最大化类与类的间隔，因而有较好的适应能力和较高的分准率。该方法只需要由各类域的边界样本的类别来决定最后的分类结果。

支持向量机算法的目的在于寻找一个超平面H(d),该超平面可以将训练集中的数据分开，且与类域边界的沿垂直于该超平面方向的距离最大，故SVM法亦被称为最大边缘(maximum margin)算法。待分样本集中的大部分样本不是支持向量，移去或者减少这些样本对分类结果没有影响，SVM法对小样本情况下的自动分类有着较好的分类结果。

12.      K-NN和SVM是基于向量空间模型(VSM)的最好的分类器,
14. 聚类的方法:  1. 基于图论的方法,形成一个样本间相似性矩阵, 根据阀值类确定类别; 二是基于种子的方法,先指定一个初识的类中心,其他的样本的类别与最近的类中心相同; 3.聚类分裂法,将新的信息样本作为一个查询,与已经存在的类进行比较,寻求最佳匹配类作为其所属的类别. 当然,还可以将聚类方法分为平面方法和层次方法,只是考虑的角度不同而已.

(以上12点,是我学习过程中摘记下来的,虽然已经过整理,但还是有些乱^_!!)

三.      毕业设计的目标

1.        一个可以运行的基于WEB的网页自动分类系统(无监督):  其可以根据用户输入的查询, 直接从goolge搜索引擎中查询并获得查询结果,对查询结果清洗后, 进行分词,特征提取后,建立VSM模型,并用STC聚类算法进行聚类,并通过分类目录的形式显示给用户.

2.        数据来源只针对搜索引擎返回的snippet, 并不获取整个网页

3.        处理文件格式为: a.纯文本(无超链接,无格式)---plain text

b. 网页(html, xml): 暂不考虑各种颜色信息,各种格式等的影响

                           暂不考虑DOC. PDF的文件格式

4.        拟适用中英文网页

四.      设计难点

1.        中文分词

2.        高维度的降维

3.        适用中英文查询

4.        结果显示的标签提取问题

5.        分布式查询的性能问题

 

五.      实现方法

1.        软件平台:  myeclipse + tomcat + stucts + cvs

2.        测试工具:   junit + jmeter

 

Ps:

1. 学习Carrot2可以到project.carrot2.org,有丰富的例子和介绍

2. 如果有些文件格式发不上来,我会发在我的论坛里 www.zhuayu.net

3. 本人也初次接触这种带些研究性质的项目,还望各位多多指教!

 

使用训练集产生分类器的方法是针对"自动归类"的.
自动归类，你有没有好的想法，介绍下？

不好意思，现在我主要集中于学习自动聚类，呵呵，为了完成毕业设计嘛
不过我寒假的时候看过一本书《搜索引擎--技术,原理,系统》--北大天网创世人写的，里面专门有一章专门讲自动归类，建议你去看一下

我们曾经做过一个类似的产品（一个IE plugin,有兴趣的得话，可以从这里download http://www.bluesofts.com/download/598/1295/p-ZOOM_v1.0.177.html），不过似乎市场反应不佳，公司也面临倒闭的边缘。原因很简单，理论上的东西（自动分类）总是不能满足用户的需求，连google都不怎么感兴趣。

所以我的建议，如果这个是一个本科毕业设计，it is fine。 算是练练手。如果是研究生的论文. 就有点差强人意了，太缺乏创新性。除非你可以在分类算法上有所建树 （我不是说速度上，而是你的算法能够通过图灵测试，达到AI的水准，即单从分类结果上看，我们分不出来这是人类分类的还是计算机分类的 ）。

非常复杂的毕业设计，做得完吗？你是厦大软院的哪位，呵呵……
“这个课题的建立是基于STUCTS的,”这句话有点问题吧，STURTS顶多算是实现你这个课题的辅助而已吧。

要提供一个可用的分类系统绝非易事，根据我以前的经验产品的prototype大概需要3个月 3 个developer （算法已有）

老兄也是软院的说？呵呵

恩，你说的没错，STRUTS只是一个辅助而已， 项目就我一个人做，不知道要做多久

这么恐怖哇。。。要这么长时间？@！！！

我才一个人做，现在都快四月份了，而6月份之前要把这个毕设搞定，当然还有毕业论文。

今早去指导我的陈博士那里，之前我只是对真个框架有个大概的了解，在陈博士给我十分耐心的讲解了差不多一个小时后（在此，特别感谢陈博士，一个认真，和蔼的前辈），我相信自己对做这个系统有了更深一层的了解，而且把我之前零零碎碎看的东西都串了起来。最后，陈博士说，代码量不是很大，不过担心我如果用java做，机子能不能承受的了。他说，由于java没有指针，如果要传递一个500M的东西，java给你再copy一份，那1G的内存就没了。。。

听emarket前辈的评论，相信您对这方面颇有研究也有一些经历，希望不吝赐教！

ps: 今天我会把修改好的开题报告贴出来，希望大家多提些建议，不胜感激！

我觉得没有必要用J2EE来做，你要实现的是一个WEB网页的分类功能，写一个界面来演示一下就可以了，为什么非要做成一个J2EE的系统呢？这不是增加复杂性吗？
你做的自动分类不是针对网页吗？为什么要存到本地来？这我就不明白了。JAVA应该可以解决大文件的读取问题，应该有很多算法。不过也是增加了复杂性。可能课题以外的工作要做很多了。课题本身应该是属于研究性的，而不是做一个应用系统。

  真的很感谢这位兄弟的建议，以前j2ee的项目做熟了，觉得现在也非得把它做成这个模样的，否则心里不爽似的，呵呵，其实我当然了。幸亏开题报告还没有提交上去^_！！用一个界面演示一下就足够。

  这个分类是针对网页的，从搜索引擎那里获得的结果要存到本地，以便后面的处理。如果搜索引擎返回大批结果的话，可能存于本地会有些性能问题。我不知道陈博士讲的是不是这个意思。

  本来这是一个2~3个人的项目，由于报的人手不够，现在就剩我一人在做，而我对这方面以前没接触过多少，入门阶段很艰难。大家的建议给了我莫大的鼓励^_^