（计算机软件与理论专业论文）机器学习算法在文本分析中的研究.pdf

摘要 随着互联网信息资源的指数增长，如何实现海量文本数据的自动分析已成为 日益紧迫的研究课题。近年来，作为文本自动分析的重要手段，文本聚类及热点 信息发现逐渐受到研究者的重视。对互联网信息的聚类处理使人们可以从总体上 了解信息主题的分布，并根据特定兴趣选择不同主题的文本进行浏览；对互联网 热点信息的自动发现使用户更容易了解不同类别中最受关注的焦点。 本文关注于文本聚类算法和热点信息发现算法的改进和高效实现，以期在 海量数据和工程化环境中有效推动文本自动分析技术的实用化。首先，针对 k m e a n s 算法的聚类结果严重依赖于初始中心点的特性，本文在k m e a n s 算法 中引入了具有优化近似因子的d e l t a 近似k c e n t e r 算法，构造了改进的聚类算法 k w o c ( k m e a n sw i t ho p t i m i z e dc e n t e r s ) ，用以实现更有效的初始中心点选择。 实验表明k w o c 可显著提高最终聚类结果的鲁棒性。在k w o c 的具体实现中， 本文创新性地设计了针对性较强的事务性文件系统，实现了k c e n t e r 中间计算 结果的高效缓存，在文件层面实现k c e n t e r 与k m e a n s 的计算结果共享。该方 案显著降低k w o c 算法的时间开销。 其次，为了有效挖掘海量w e b 数据中的热点信息，设计了一种新颖的w e b 热点信息发现算法。该算法以分阶段的串频变化量统计矩阵为基础，结合串频变 化的历史波动，得出有效的热点信息串的评价指标，并根据由该指标选中的热点 信息串最终完成热点文章的甄选工作。该算法的具体实现同样利用了有针对性的 事务性文件系统，因而具有较高的时间效率。 最后，论文给出了针对上述聚类及热点信息发现算法的事务性文件系统的设 计方案及实现方法，该事务性文件系统基于一致性哈希理论，以高速的散列文件 为基础高效地实现了算法运行中计算结果共享，有效地把计算依赖转化为事务依 赖，在事务重建理论框架下为算法的可靠性提供了有力保障。 实验表明，本文提出聚类算法、热点算法及其系统方案实现具有良好的性能 和效率，可以适应于实际工程环境下的海量数据应用。 关键词：文本聚类热点信息发现事务型文件系统机器学习算法 a bs t r a c t a st h ee x p o n e n t i a lg r o w i n go fi n t e r a c t si n f o r m a t i o n ，h o wt or e a l i z et h ea u t o m a t i c a n a l y s i so fh u g et e x td a t ab e c o m e s a ni n c r e a s i n g l yu r g e n tr e s e a r c hs u b j e c t i nt h e s e y e a r s ，a sa ni m p o r t a n tm e a s u r eo f t e x ta u t oa n a l y s i s ，t e x tc l u s t e r i n ga n dh o t s p o t i n f o r m a t i o nd e t e c t i n ga r eg a i n i n gm o r ea n dm o r er e s e a r c h e r s a t t e n t i o n t h ec l u s t e r i n g o fi n t e r n e t si n f o r m a t i o nm a k e sp e o p l ek n o wa b o u tt h ed i s t r i b u t i o no ft h et h e m e so f t h ei n f o r m a t i o nf r o mah i g hl e v e l ，a n dc h o o s et e x to fd i f f e r e n tt h e m e sb a s e do nt h e i r o w ni n t e r e s t i n gt ob r o w s e a u t o m a t i c a l l yd e t e c t i n gt h eh o t s p o ti n f o r m a t i o no fi n t e r n e t m a k e su s e r sk n o wa b o u td i f f e r e n th o t s p o t so fd i f f e r e n tc l a s s i ce a s i l y t h i sd i s s e r t a t i o nc o n c e n t r a t e so nt h ei m p r o v e m e n ta n de f f e c t i v er e a l i z i n go f t e x t c l u s t e r i n ga n dh o t s p o ti n f o r m a t i o nd e t e c t i n ga l g o r i t h m ，t op u s ht h et e x ta u t o m a t i c a n a l y s i st e c h n i q u e sp r a c t i c a lu s ei nh u g ed a t aa n de n g i n e e r e de n v i r o n m e n te f f e c t i v e l y f i r s t l y , o na c c o u n to f t h ef e a t u r et h a tk m e a n sa l g o r i t h m sc l u s t e r i n gr e s u l ts e r i o u s l y d e p e n do nt h ef i r s tp o i n t ，t h i sd i s s e r t a t i o ni m p o r t sa d e l t aa p p r o x i m a t ek c e n t e r a l g o r i t h mw i t ho p t i m i z e dc e n t e r st ot h ek - m e a n sa l g o r i t h m ，a n dc o n s t r u c t st h e i m p r o v e dc l u s t e r i n ga l g o r i t h mk w o c ( k m e a n s w i t ho p t i m i z e dc e n t e r s ) t or e a l i z e t h em o r ee f f e c t i v ec e n t e r sc h o s e n e x p e r i m e n tp r o v e dt h a tk w o c c a ni m p r o v ef i n a l c l u s t e r i n gr e s u l t sr o b u s t n e s sd i s t i n c t l y i nt h ec o n c r e t er e a l i z i n go fk w o c ，t h i s d i s s e r t a t i o nd e s i g nac r e a t i v et r a n s a c t e df i l es y s t e m , w h i c hr e a l i z e se f f e c tc a c h i n go f t h em i d d l er e s u l t so f t h ek c e n t e ra l g o r i t h m ，a n dr e a l i z e st h er e s u l ts h a r i n go nt h ef i l e l e v e l t h i ss c h e m ec a nr e d u c et h et i m es p e n di n go ft h ek w o ca l g o r i t h m s e c o n d l gt om i n et h eh o t s p o ti n f o r m a t i o ni nh u g ew e b d a t ae f f e c t i v e l y , w ed e s i g n an e ww e bh o t s p o ti n f o r m a t i o nd e t e c t i n ga l g o r i t h m t h i sa l g o r i t h mb a s e do ns t a g e d s t r e a m i n g f r e q u e n c yc h a n g i n gd a t am a t r i x ，c o m b i n i n gt h eh i s t o r yw a v eo f t h e s t r e a m i n g f r e q u e n c yc h a n g i n g ，f i g u r e so u tt h ee f f e c th o t s p o ti n f o r m a t i o nc l u s t e r s e v a l u a t i n gi n d i c a t o r , a n df i n a l l yf i n i s h e st h ew o r ko fc h o o s i n gh o t s p o td o c u m e n t b a s e do nt h ec h o s e ni n f o r m a t i o nb yt h ei n d i c a t o r t h i sa l g o r i t h m sc o n c r e t er e a l i z i n g a sw e l lu s e st h et a r g e t e dt r a n s a c t e df i l es y s t e m , s oi th a sh i g ht i m ee f f i c i e n c y a tl a s t ，t h i sd i s s e r t a t i o ng i v e st h ed e s i g ns c h e m ea n di m p l e m e n t a t i o nm e t h o d so f a b o v ec l u s t e r i n ga n dh o t s p o ti n f o r m a t i o nd e t e c t i n gt a r g e t e dt r a n s a c t e df i l es y s t e m ， w h i c hi sb a s e do nt h ec o n s i s t e n c yh a s h st h e o r y ，e f f e c t i v e l yi m p l e m e n t sr e s u l t s h a r i n gd u r i n gc o m p u t i n gb a s e do nf a s th a s hf i l e ，e f f e c t i v e l yt r a n s p o r t sc o m p u t i n g d e p e n d i n gt ot r a n s a c t i o nd e p e n d i n g ，a n dp r o v i d e st h es t r o n gi n s u r a n c eo f t h e r e l i a b i l i t yo ft h ea l g o r i t h mi nt h ef i a m eo f t r a n s a c t e dr e b u i l d i n gt h e o r y 匕x p e r i m e n tp r o v e dt h eg o o dp e r f o r m a n c ee f f i c i e n c yo ft h e c l u s t e r i n ga l g o r i t h m h o t s p o ta l g o r i t h ma n dt h e i ri m p l e m e n t a t i o no ft h es y s t e m sd e s i g ns c h e m e ，a n dt h e v c a nb eu s e di nh u g ed a t ao f t h er e a le n g i n e e r e de n v i r o n m e n t 1 ( e yw o r d s ：t e x t c l u s t e r i n g ，h o t s p o td e t e c t i n g ，t r a n s a c t i o np r o c e s s i n gf i l e s y s t e m , m a c h i n el e a r n i n ga l g o r i t h m s 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨鲞盘鲎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：炻头乏签字日期：2 p 。年。 t 1w r i t e t 1w r i t e ， g o 2 夕 图2 4 丢失修改 事务1 的写操作被事务2 所忽略，图2 4 中显示的是i 汪a d w 对t e w r t e 顺序，但w r i t e w 刚t e w r j t e 顺序会造成同样的结果。 2 w r i t e r e a d 依赖( 导致读脏数据) t 2w r i t e t 1r e a d t 2w r l t e t 2w r i t e t 1w r i t e 如图2 - 6 所示，事务l 读了两次对象，一次是在事务2 对对象修改之前，一 次是事务2 对对象修改之后，显然这两次对对象的读取是不一致的，这种情况导 致了不可重复读情况的出现。 以上所出现的在并发控制中的三种异常情况应用“锁”处理，“锁”可以由 具有排它性的信号量实现，“锁”管理系统用来管理对共享数据的并行操作问题。 在实际的运用中共享的数据结构往往是由指针连结在一起的一个节点集，遍历这 样的结构的作法：读入一个或者一批锚点记录( a n c h o rp o i n t ) ，找到某些锚点的当 前值，然后以这些入口值得到其它的记录，当遍历这样一个共享指针结构的时侯， 必须保持指针稳定直到它被用来查找下一个对象为止，目标对象的稳定靠在释放 源指针上的信号量之前成功获得其目标信号量，该操作称为“蟹行 ( c r a b b i n g ) 操作：蟹往往在迈向下一个点时，总是攀住前一个点。 2 3 6 系统可靠性及其相关 一个由多个模块构成的系统仍可以看作是由一个单一的模块构成的，每个模 块都理想的特定行为( s p e c i f i e db e h a v i o r ) 和与之对应的观察行为( o b s e r v e d b e h a v i o r ) ，当观察行为违背理想的特定行为而发生不致时称为失败( f a i l u r e ) 。 失败往往是由存在于模块中的错误( e r r o r ) 或缺陷( d e f e c t ) 导致的，导致的原因称之 为故障( f a u l t ) ，发生错误和导致失败之间的时间称之为错误延迟【j 引。 文件系统是有一些固定的参数与指标来衡量的：m t t f ( m e a nt i m et o f a i l u r e ，平均失效时间) ，被定义为随机变量、出错时间等的期望值；m t t r ( m e a n t i m e t or e s t o r a t i o n ，平均恢复时间) ，被定义为随机变量恢复时间的期望值； m t b f ( m e a nt i m eb e t w e e nf a i l u r e ，平均故障时间间隔) 定义为失效或维护中所需 要的时间。 第二章算法及相关概念综述 2 3 7 一致性哈希( c o n s i s t e n th a s h ) 一致性哈希( c o n s i s t e n th a s h ) 在1 9 9 7 年由麻省理工学院( m i t ) 提出，设计的目 标就是为了解决因特网的热点( h o t s p o t ) i 洒- j 题，初衷和c a r p 十分类似。它满足4 个适应性条件： 1 平衡性( b a l a n c e ) 平衡性是指哈希结果能分散到所有的缓冲中去，使所有的缓冲区都得到 利用。 2 单调性( m o n o t o n i c i t y ) 单调性是指如果旧内容己经分派到了相应缓冲，此时又有新的缓冲加系 统，哈希的结果能够保证原有的己分配内容可以被映射到新的缓冲中去。 3 分散性( s p r e a d ) 分散性指面对多终端时，相同的内容应被不同的终端映射到相同的缓冲 区，本系统中的终端可被认为是请求线程。 4 负载( l o a d ) 负载是与分散性类似的问题，它是指：同一个缓冲区不应被不同的终端 映射成不同的内容。 一致性哈希的特性被深入研究并扩展应用于不同的领域中1 9 】，本系统中的 h a s h 文件系统为线性h a s h 算法，基本满足一致性哈希的适应性条件。 2 4 本章小结 本章介绍了在文本分析研究中所采用的相关算法知识及相关概念：( 1 ) 聚类部 分：首先对聚类的算法做了综述，然后简单介绍了聚类的基本过程，最后指出了 聚类结果的评估标准。( 2 ) 热点信息发现部分：对热点信息发现的概念及特征做 了描述并指出热点信息发现的研究意义及科研难点。( 3 ) 对于算法运行过程依赖 的事务性文件系统结构设计概念及设计原则进行讨论并对其具体特性及相关知 识作了介绍，最后重点对计算依赖、事务依赖及一致性哈希等做了阐述。 1 6 第三章优化初始化中心选取的聚类算法 第三章优化初始化中，d 选取的聚类算法 本章介绍了一种基于k m e a n s 改进的聚类算法k w o c ( k m e a n sw i t h o p t i m i z e dc e n t e r s ) ，本章的组织如下：首先介绍了k c e n t e r 的工作原理，指出利 用k c e n t e r 算法的聚类中心发现结果作为k m e a n s 的初始化中心输入的方法， 其次分析k c e n t e r 及k - m e a n s 之间的共享数据，给出文件系统中存储向量的内 积高效计算算法，最后在应用层面上逐步介绍了该算法的详细实现。特别地，本 章提出了一种使用并查集进行停用词过滤及词典空间构建的算法。 3 1 聚类算法选取及改进 3 1 1 适用环境及聚类目标 本章介绍的聚类算法原始数据输入是由天津海量科技公司提供的网络新闻 信息语料( 文本集合) 。本章讨论的聚类算法及其实现用于第一级新闻分栏目归 类，这些栏目是：( 1 ) 财经；( 2 ) 互联网；( 3 ) 房产；( 4 ) 汽车；( 5 ) 体育；( 6 ) 娱乐；( 7 ) 教育；( 8 ) 科技；( 9 ) 社会；( 1 0 ) 个性化新闻。 本章讨论的聚类算法的最终目标是：根据实际的运行环境选取并改进合适的 算法及设计高效的处理系统实现对大批量语料进行聚类加工处理，使有高度相似 描述的网页聚合成簇以便做进一步的二级分类处理。在系统试运行过程中，本系 统先后成功处理近2 0 0 g 的语料做聚类实验并在实验中取得了令人满意的效果。 3 1 2 算法选取 根椐系统实际运行环境，其处理的原始语料数据具有以下特点： 1 无严格时间顺序 所给定的语料是由在多台服务器并发运行的多个网络爬行器所抓取的语料 简单汇总而成。虽然具体到每个爬行器所抓取语料都有明确的起止时间，但在合 并后的语料记录时间戳并不能保证严格有序的递增或递减，结果输出要求按发布 时间顺序递增，相关时间戳的解析及标准化成为必要且关键的工作。 2 数据量大 一般语料的大小为以g b 为单位，从数g 到数百g 不等。聚类是新闻分类别 第三章优化初始化中心选取的聚类算法 显示的第一步，其基本目的是做初始化分簇。由于其后续工作仍然十份繁重，聚 类应争取尽可能多的时间给后续精细化的分类处理，这就要求：系统尽可能的优 化以使得在占用最少空间的前提下，使用最少的时间得出最中肯的归类效果。 3 格式不固定 根据实际语料情况，由不同的网络爬行器抓取的数据格式并非完全一致从而 导致处理格式标准化问题不得不占用大量处理时间，这就对系统的核心运行时间 提出了更高的要求。 4 可分类别数量明确 根据以上的特点，( 1 ) 、( 2 ) 、( 3 ) 要求核心算法尽可能高效，( 4 ) 决定了可以使 用无监督的算法。综合高效、无监督这两大特点本系统采用了基于k m e a n s 算 法的改进算法。 3 1 3 算法优化 k m e a n s 算法接受输入参数k ，然后将n 个文本样本( 在本系统中，为文章 的分词向量) 划分到k 个簇并最终使得：同一簇中的对象相似度较高而不同簇中 的对象相似度较小。聚类过程中单个文本的归类操作是参考各聚类中对象的均值 所获得的“聚类中心”来进行计算的，也就是说，对于每个文本样本分别计算其 与所有聚类中心的相似度并把该文本样本归类到与其相似度最近聚类中，设d 为语料文本集合，n = ldf 为语料的总篇数，语料中每篇文章假定成空间一个点， k 为最终的聚类个数，k m e a n s 算法的过程可描述为： 算法击3 1 ：k m e a n s 原始算法： 输入：d ，k ，m 输出：k 个中心 c ，i2 i k ) 及以k 为中心的分割d 各类的结果描述。 参数说明： d ：文本集合，其格式为预处理格式之一( 见3 3 1 节) k ：最终的聚类数目 m ：最大迭代次数，若超过m 算法未收敛，则算法中止并输出结果 ( 1 ) 从d 中随机选取k 个点做为聚类中心c 。其中，1 i k ； 。 ( 2 ) 以c ，的变化幅度为测度，当所计算的值较上次计算的结果有明显变动 时( 衡量标准为设定的阈值) ，不断的重复该过程：重新计算d 中每点 与聚类中心的距离并把该点分配到最近的聚类中心中。分配完毕后计 算新的聚类中心。 第三章优化初始化中心选取的聚类算法 ( 3 ) 输出最终k 划分的结果。 k 个聚类具有以下特点：各聚类内部尽可能的紧凑，而各聚类之间尽可能的 分开。 1 对中心选取策略做改进 以上版本的k m e a n s 算法有明显的不足，在( 1 ) 随机选取的k 个聚类中心中 有可能是杂质元素，这些具有杂质的中心会导致迭代时间过长或聚类效果不佳， 甚至会使最终的聚类中心振荡从而超过实用时间的时限。解决方案是使用 k c e n t e r 的近似算法获取聚类中心，k - c e n t e r 聚类算法的目标是：使得所有子集 的最大半径最小。因此，k c e n t e r 可取得较中肯的聚类中心，把获取的中心结果 做为k - m e a n s 的初始中心输入。由于k c e n t e r 所解决的问题为n p 完全问题， 只能获得与理论最优解较接近的近似算法，该近似算法的描述如下： 算法3 2 舟：k c e n t e r 近似算法： a k c e n t e r ( p ，k ) p = p l ，仍，见) s = p 1 ) ，u o 卜p l ，i 卜1 f o r ( j = 1 ；j = n ；j + + ) 嘭卜d ( p ，u o ) w h i l e ( s _ k ) f o r ( j = 1 ；j 4 g b 时 语料所在的文件系统需是n t f s 格式 j z l t f d词l dt f - i d f 但 图3 1 三元组格式 由公式( 3 - 2 ) ，在两篇文章样本的相似度计算过程中，优化矩阵行向量内积计 算是的优化系统整体性能的关键。从逻辑层面来讲，行向量的维度与词典空间的 维度相同，但向量的有效大小为行向量所代表的样本中己选取的切分词数量。如 第三章优化初始化中心选取的聚类算法 图3 3 所示： 图3 - 2 向量运算有效元素示意图 向逻辑维度= 词典空阃的维度 向有效大小= 样本申已选取切 分词的数 词典空间的维度规模一般为数十万计或更多而某篇文本样本的分词数量一 般只是以百为单位的级别，可见参与运算的行向量为稀疏向量。稀疏向量的内积 计算过程如图3 2 所示：判定两向理的有效长度，遍历具有较长有效长度的向量， 对该向量中的每一有效元素( i e ，矿一彬值不为0 的元素) 的矿一f 够值k ，在 另一较短向量中进行索引查找其所对应的矿一矽值做乘法运算： 砭= 悟0 蒜茹鬈磊慧葛? 。 p 3 ， 2 i ，对应文章不存在相同的词i d 、7 可以从直观看出，此算法的时间主要消耗在对向量。的相同元素查找操作( 即巧 值的确定) 中。根据上述内积的计算方法，如图3 2 所示只有在两个向量稀疏表 示中有效的公共元素对内积结果才有贡献，因此该优化问题转化为：优化查找两 向量稀疏表示序列有效公共元素的方法。为解决该问题提出以下解决方案： 解决方案一：使用双路跳转的二分查找算法( 时间复杂度 o ( n l o g ( n ) ) ) 使用双路跳转的算法求公共子序列问题的理论复杂度为o ( n l o g ( n ) ) ，。其算法 描述如下： 首先稳定排序这两个稀疏向量表示序列，然后以互跳的方式双向交错二分查 找。计算过程如图3 3 所示： 第三章优化初始化中心选取的聚类算法 图3 3 双路跳转二分查找 在该过程中，双路跳转二分查找求内积算法设计如下： 算法3 3 ：双路跳转二分查找求内积算法 输入：只，b 输出：只、最所代表向量内积 参数：只、咒为两个向量的稀疏化表示，q 为公共素队列，r ，为结果值。 ( 1 ) 建公共元素队列q ，初始化为空，设定结果值b 。 ( 2 ) 当只与b 都不为空时，反复做 a ) 把a 序列指针只下移，直至只所指向的元素己大于等于b 序列 指针只或所指向的元素值或到了序尾。 b ) 在b 中二分查找只所指向的元素，若找到，当两个指针指向的值 相等时，反复做 i 。把其加入q ，同时计算巴与忍所指向元素的内积，更新r ，。同 时把两个指针加l 。 否则若未找到 把指针移向第一个大于被索引元素的内存位置。 c ) 在a 中二分查找b 所指向元素的的值，若找到，当两个指针指 向的值相等时，反复做与步骤b ) 中描述的对应处理。 i 把其加入q ，同时计算只与b 所指向元素的内积，更新r 。同 时把两个指针加l 。 否则若未找到 把指针移向第一个大于被索引元素的内存位置。 返回。 第三章优化初始化中心选取的聚类算法 从理论层面分析，该方法中的二分查找使内积运算由o ( 即2 ) 复杂度降到了 o ( n l o g ( n ) ) 复杂度，此外由于向量表示特别稀疏，算法互跳的索引方式使得大批 单侧元素序列被略过并不参与计算，因而该算法有比理论值更高的实践性能。在 上图所示的例子中，a l 、a 7 块只有做复杂度为o ( 1 ) 的块指针比较就被舍弃，同时 口2 、口6 之间的元素块由二分查找被整块跳过，口6 、口8 块以o ( 1 ) 复杂度的指针比 较被成块的选取。 解决方案二：使用h a s h 高速索7 1 ( 时间复杂度d ( 玎) ) 算法解决方案二中的复杂度为o ( n l o g ( n ) ) ，但假定两个序列中存取元素可以 在0 ( 1 ) 的时间复杂度内完成，则可以按照以下算法存得时间复杂度为o ( n ) 的算 法： 算法3 4 卉：h a s h 高速索引求内积法 设定结果值b 。 ( 1 ) 当巴与尼均不为尾端元素时，反复做 a ) h a s h 取1e ， l a s h 取b 。 ( 2 ) 更新b 。 复杂度为o ( 1 ) 的h a s h 取值方法在由基于线性一致性哈希的存取结构决定 并实现。在本项目的实践过程中，用于计算内积方案二较方案一有稳定高效性能 表现，经过优化过的k m e a n s 算法在系统运行期间中取得了令人满意的效果。 3 2 聚类算法运行环境 3 2 1 系统开发及运行环境 本系统前期在w i n d o w sx p z h c n + v s 2 0 0 5 【e n s p l 下开发，后期为了软 件的兼容性转入w i n d o w sv i s t a e n 】+ v s 2 0 0 8e n 下开发，该系统开发过程中采用 m f c 用户交互，同时采用s t l 作为重点算法实现以保证高效率。 开发完成后，经过实际软件运行测试己知的兼容系统如下所示： 1 h a s h 取：从实际的h a s h 存储序列中取相应忭i d f 值。即若该x 存在于相应的h a s h 序列中，则取出的t f - i d f 值，否则为0 ；该操作的性能依赖于h a s h 存储的设计。 2 3 第三章优化初始化中心选取的聚类算法 w i n d o w s2 0 0 0p r o f e s s i o n a l + s p 4 w i n d o w sx pp r o f e s s i o n a l + s p 2 w i n d o w s2 0 0 3s e r v e r w i n d o w sv i s t au l t i m a t e