朴素贝叶斯方法-盘古文库

朴素贝叶斯方法（精选8篇）

朴素贝叶斯方法第1篇

关键词：查询推荐,用户日志,点击预测,朴素贝叶斯,二分图,Jaccard相似度

0 引言

在目前主要根据关键词进行检索的搜索引擎框架中,用户往往无法得到令其满意的返回结果。这一方面是由于网络数据呈海量增长态势,每条查询都可能会有上万到几十万条的相关反馈信息,在这庞杂的信息中要找到用户满意的结果,这就要求用户尽可能准确地描述查询请求,同时需要搜索引擎在一定程度上能够理解用户查询意图,这对用户和搜索引擎来说,都面临一定挑战。而另一方面,在用户获得了比较满意的结果后,如何帮助用户发掘潜在的相关信息来提升用户的搜索体验,这也是亟待解决的问题。

查询推荐作为搜索引擎改善用户查询体验的有效方式之一,其旨在接受用户输入某个查询后,尽可能理解用户的查询需求并向用户推荐与用户查询语义相关的其他查询[1]。

在搜索点击日志中,包含了大量用户真实的搜索行为[2],对这些数据进行分析与挖掘,可以更好地理解用户查询意图,发现与用户查询相关的其他查询。因此,本文在用户点击日志的基础上,对用户搜索行为进行建模,找出与用户查询意图相关的查询信息,并给出个性化推荐。

1 查询推荐相关研究

目前查询推荐已经作为国内外各大商业搜索引擎的标准配置功能之一,在学术界也得到了广泛关注和研究。然而现在的搜索引擎中大多针对用户输入的查询文本本身,进行改写和扩展,或是简单地提供与用户查询文本近似的热门搜索作为推荐,并没有考虑查询中潜在的用户搜索意图。如果搜索引擎能够根据查询词自动找出背后的用户搜索意图,然后根据不同的用户,提供不同的查询推荐,这无疑会增加搜索引擎用户的搜索体验。而查询日志中记录了用户大量的查询点击信息,这些信息体现了用户的查询习惯和点击意图,利用日志可以挖掘用户潜在的查询意图,目前针对日志进行分析的主流方法主要有两类[3]:基于查询会话(Session)的方法和基于点击图的方法。

1.1 基于查询会话方法

查询会话是某个用户在较短时间内连续发出的多个查询,一般而言,在同一查询会话内的查询之间往往存在一定的语义相关性[4]。比如某个用户想要购买手机,在某个集中的时间内连续向搜索引擎发出:“苹果手机”、“iphone 6图片”、“iphone 6价格”等一连串查询,这就形成一个查询会话。通过将用户搜索日志划分为大量不同的查询会话,然后利用各种数据挖掘算法对查询会话进行统计与分析,推荐的结果往往是一批查询对,这些查询在搜索过程中经常共同出现,反应了用户的搜索意图。李亚楠等人认为同一Session中的查询都具有语义相关性,而其中的前后查询具有一定的概率“跳转”,所以对Session进行划分,并据此建立查询关系图,使用加权的SimRank算法在图结构中进行相似计算,从而挖掘出查询间的间接关联和语义关系[4]。在文献[5]中,将查询推荐分为两阶段:第一阶段分析用户日志,从中抽取用户Session,第二阶段从用户Session中使用关联规则算法挖掘出查询间的关系,找出相关查询。Sadikov等人提出一种结合文档点击和用户查询Session的共现信息,利用近似用户搜索行为的马尔可夫多随机游走模型,根据用户的可能潜在意图进行查询修改聚类,用来改善搜索引擎中返回的查询建议[6]。

1.2 基于点击图方法

从用户查询日志记录中可以看到用户提出某个查询,搜索引擎返回相关结果后,用户会有选择地点击其中某些链接。之所以认为这种点击行为很有意义,是因为用户在看了返回的网页标题和摘要后,认为此链接和查询比较相关,所以才会点击。而将用户的查询和相对应点击的链接网址(URL)使用边连接起来,就构成了点击图,这是一种二分图[7],一端节点是用户发出的查询,另一端是对应点击的URL。在使用点击图作为查询推荐的一个简单的通用基本框架是:如果两个查询分别对应的点击URL中,有相当一部分比例是相同的,那么说明这两个查询有很大的语义相关性,可以作为相关查询进行推荐。不同的学者据此也提出了各种扩展和改进的方法。Hamada M.Zahera等人提出根据查询和URL点击二分图,对查询进行相似聚类,然后对用户提出的查询,找出与其最相似的一组进行排序推荐[8]。刘钰峰等人提出基于查询上下文训练词汇与查询间的语义关系,并结合查询和URL对应的点击图以及查询的序列行为构建Term-Query-URL异构信息网络,采用重启动随机游走算法进行查询推荐,该方法综合了语义和日志信息,提高了稀疏查询的推荐效果[9]。文献[10]中,提出一种新的基于上下文感知查询建议方法,该方法分为线下和线上两步。在线下,使用用户点击图进行聚类,把查询总结成不同概念,然后为Session数据序列构造概念后缀树作为查询建议模型。在线上,把用户提交的查询序列映射到概念中,获取用户搜索上下文,通过查询概念后缀树得到相关查询。

综上,除了日志分析方法中的两个主流方法外,还有基于相似度方法、基于时间分布法等[1]。虽然目前提出的很多方法对查询推荐有一定的效果,但由于大多具有高度复杂性并且用户意图不明确,所以很难得到广泛的实际应用。本文根据点击日志,对用户的查询进行意图点击预测,进而将预测值传播给其他查询,结合相似度和时间因子获得相关查询。最后在搜狗实验室提供的数据中进行实验,获得了较好的推荐效果。

2 基于用户日志挖掘的查询推荐

在对用户日志和搜索引擎进行深入分析后,提出基于图1的框架来研究查询推荐。从中可以看出用户在发出查询后,一部分经搜索引擎返回相关网页,而另一部分使用朴素贝叶斯针对用户查询,预测URL的点击率,将其值用在反向点击图中,从而找出相关查询,推荐给用户。

2.1 使用朴素贝叶斯进行URL点击率预测

朴素贝叶斯是一种基于贝叶斯理论的有监督的概率分类算法,尤其适用于样本特征维数很高的情形。有资料显示,就算样本属性相互独立的假设不成立,或者在完全相反的情况下(属性相互依赖),依然可以证明该算法是最优的[11]。在这里,将朴素贝叶斯算法作为一种预测模型,用它来预测URL对于用户及其所提交的查询的点击率,也就是说可以根据它计算出用户在提交某个查询时想要看到某个链接的概率。

首先,需要根据用户日志对朴素贝叶斯进行训练,将每个URL作为概念,每个与其对应的查询作为样本,根据所需计算出各个概念的先验概率及其对应的样本的条件概率,然后再依据用户当前输入的查询(实例)计算其与每个概念的点击值。具体过程如下:

输入:训练数据T={(q1,u1),(q2,u2),…,(qn,un)},其中qi=(qi1,qi2,…,qin),qij是第i个样本的第j个属性,ui∈{c1,c2,…,ck},ci为不同的URL;用户实例q。

输出:实例q对应URL的点击率。

a)URL的先验概率及样本属性的条件概率

式(1)代表每个URL的先验概率,分子为每个URL的频数,分母为样本个数;式(2)代表每个属性的条件概率,分子为属性和URL的联合概率。

b)经过训练后,就可以对用户当前提出的查询实例q=(q1,q2,…,qn),进行URL点击预测。公式如下:

这样每个相关URL都会有一个预测值,该预测值代表了用户输入的查询和URL的点击相关度,值越大,表示用户想要点击URL的意图性越强。

2.2 使用反向点击图进行查询推荐

2.2.1 反向点击图推荐模型

基于二分图结构,提出一种URL-Query的反向点击图推荐模型,如图2所示。

在该模型中,根据2.1节计算出用户当前查询对于历史点击中URL的预测点击值,作为URL的权重,并将其平均分配给与其对应的查询,这样每个查询经过整合后会有一个相关值,这个相关值也代表了用户的查询意图,如图3所示。

考虑一个由n个URL和m个查询(Query)构成的点击二分图,表示为G(U,Q,E),E表示URL和Query之间连接的边,URL节点表示为U={(u1,a1),(u2,a2),…,(un,an)},其中ai为计算用户当前查询的预测点击值,Query节点表示为Q={q1,q2,…,qm}。根据图3中的计算,每个qi的相关值经过传播求和,计算如下:

其中:k(uj)表示与uj连接的qi的个数;aj为URL的预测值。

然而由于对用户输入的查询进行朴素贝叶斯URL点击预测后的值会被均分到相对应的历史查询中,这会导致将每个查询均等化。鉴于此,对式(4)进行补充修正,加入了用户历史查询和对应URL的点击比率,公式如下:

其中:公式的后半部分表示qi的点击数占总点击数的比率,比率越大,表示在点击历史中,用户关注的越多,用户想要点击的意图性就越强。

2.2.2 融合文本相似度和时间因子

利用朴素贝叶斯预测用户查询行为,本质上是找到查询与链接(URL)的关系,但这忽略了用户查询与历史查询之间的文本相似性,很多时候我们想搜索的是和当前词相似的或是扩展的查询内容,比如在百度输入“江南大学”,在网页底部就会出现相关搜索,如表1所示。

在表中可以看到除了其他大学外(而这些大学我们假设经过用户点击过的并给予预测的推荐查询),与“江南大学”相似的或者说是扩展的推荐查询词占了较高比率,用户可能想查询与“江南大学”有直接关系的信息。而通过融合文本相似度可以增强这一相关性,在这里采用简单有效的Jaccard相关系数来计算当前用户提交的查询和用户历史查询的文本相似性,公式如下:

在点击日志中,时间因素是一个重要的上下文信息。一般来说,用户当前的查询和用户历史中最近的点击行为关系更大[12]。现在假设用户在时间t发出一个查询q,点击历史数据中的URL和其对应查询中的时间,记为:t0,t1,t2,t3,t4,t5,如图4所示,这样图中后面的四个查询的点击时间分别包括:q1(t0,t2),q2(t1),q3(t3,t4),q4(t5)。可以看到一个查询对应多个不同的URL,会有不同的点击时间,所以不能简单地采用最近时间作为标准衡量时间。对此,使用式(7)计算相关时间因子。该式综合了当前时间和所有历史时间差的和的均值作为衡量因素。

其中:α是时间衰减参数,可以根据不同的数据集选择合适的参数,如果用户查询意图变化快,就选择较大的值,相反需要取较小值。tq是用户当前查询时间,tqi是不同的查询点击时间,分母是点击次数。这样就可以根据时间的变化来优化预测推荐。

为了举例说明,现假设用户发出一个查询q时间为9:40,在用户历史点击数据中,查询q1的时间为8:40、10:40和q2的时间为7:40、11:40、13:40。按式(7)计算相关时间因子t(q,q1)和t(q,q2)(这里α取1,时间为小时)。所以不论从时间上的直观性来看,还是计算后的数值大小比较上,q和q1更具有明显的时间相关性。

在最终的推荐中,整合式(5)、式(6)和式(7),如式(8):

通过计算,对qi的相关值进行降值排序,按Top-N推荐给用户。

3 实验与结果分析

3.1 实验数据

本实验采用的数据来自搜狗实验室提供的2008年6月份查询日志中的一天数据,共1 724 264条查询。该日志中包括每条查询的时间、用户ID、查询串、URL返回的排名、点击顺序以及点击的URL。经过预处理,选择用户查询数在200条以上的点击数据,在这里选取了10名用户,共2803条查询。每名用户中点击数据的80%用作训练,另外一部分用来测试。实验平台使用IntelCoreTMDuo T2450@2.00 GHz双核处理器,2 GB内存,Windows XP 32位操作系统,算法使用Java语言编写,分词工具使用来自轻量级中文分词包IKAnalyzer2012_u6.jar[13]。

3.2 实验设计及结果分析

尽管在国内外关于查询推荐的相关研究已有不少成果,但总体上仍然缺乏统一和客观的评价方法,尤其是针对中文的查询推荐的研究,仍然比较欠缺。由于对于一个查询来说并不存在某种标准的推荐结果,在考虑基于用户意图的查询推荐时,更是无法把握用户的真实想法。因此,一般的查询推荐评价都采用信息检索里的评价指标[14]。本文采用Top-N的精度P@N(Precision at N)和平均精度均值MAP(Mean Average Precision)作为评价指标。由于在所有候选推荐中,很难得到所有相关查询数目,因而召回率(Recall)很少作为评价指标[15]。实验对于一个给定的查询qi,系统推荐出m个查询,这m个查询中的P@N精度为:

其中K是查询测试集,这里选取每个用户的20个查询作为测试集,N为5,然后由人工进行判断产生的查询推荐是否相关。对于单个查询qi的平均精度,定义为:

其中K为测试集,|Ri|为查询qi对应的相关查询集合,Ri[k]表示Ri中第k个查询。那么P(Ri[k])是在查询qi的排序队列中观察到查询Ri[k]的概率,如果查询相关,则为1,否则取0。

在实验中,选取文献[8]中基于查询日志的查询聚类方法和文献[16]的基于用户兴趣的Apriori方法进行对比实验(在实验中分别称为查询聚类法和Apriori法。)本文方法的时间参数α需要根据不同用户点击数据集的时间分布进行选择,这里α取1。在P@5和MAP上的对比结果如表2。

本文在P@3、P@5、P@7、P@9上进一步对这三种算法在不同P@N上的变化进行测试对比。从10名用户中选取用户1和用户2作参考,图5、图6为对比结果,从中可以看出本文方法在P@N上的精准度要优于前两种方法。

为了比较直观地观察推荐效果,现列出部分查询推荐示例如表3所示,从中可以看到,本文的算法在推荐的相关查询上取得了较好效果。由于本算法关注的是用户查询的相关性和意图性,忽略了查询间的冗余性,从而在一定程序上,推荐的查询有一定的重复率。另外,由于用户查询的稀疏问题,也造成了一定的推荐不明确性。

4 结语

朴素贝叶斯方法第2篇

基于贝叶斯网络的一种常规雷达目标识别方法

现役的常规雷达一般不具备径向上和横向上的.高分辨率,雷达所揭示的目标信息非常有限.贝叶斯网络基本原理基于概率论的统计知识,作为一种分类器,它使错误的分类概率最小.文中将它引入雷达目标识别,将这些有限的信息利用起来实现对雷达目标的粗分类,取得了不错的效果.

作者：简育华 JIAN Yu-hua 作者单位：西安电子工程研究所,西安,710100刊名：科学技术与工程 ISTIC英文刊名：SCIENCE TECHNOLOGY AND ENGINEERING年，卷(期)：20077(2)分类号：V249.32关键词：贝叶斯网络目标识别雷达

朴素贝叶斯方法第3篇

近10年来,在电子商务领域,个性化推荐技术应用最为广泛。通过使用个性化推荐技术,可以根据用户的特定需求从海量信息中过滤无关信息,挖掘有用信息,从而为用户提供个性化的推荐服务,以方便用户决策。

个性化推荐技术主要有以下4种推荐方法［１］:1基于内容的推荐,指根据用户选择的产品,向用户推荐与该产品属性相似的其它产品;2基于协同过滤的推荐,主要指根据用户对产品的偏好,将与该用户偏好相似的其他用户选择的产品推荐给该用户;3基于知识的推荐,该方法通过对特定领域的知识指定规则进行基于约束的推荐和基于实例的推荐;4基于社会媒体的推荐,主要是利用集体智慧,将社会媒体中用户间的社会关系或其它媒体数据运用于推荐中。例如:将与目标用户关系最密切、在社区中影响力大,或与目标用户在同一群组中的其他用户购买过且该用户未购买的产品推荐给该用户。

朴素贝叶斯方法是统计学分类方法,作为数据挖掘领域的经典算法,朴素贝叶斯方法在不同领域有着广阔的应用前景。在特征项独立的条件下,该方法预测的准确性超过了神经网络和基于向量机算法［２］。而在个性化旅游路线推荐领域,并没有相关文献介绍使用朴素贝叶斯方法对旅游路线进行推荐。

当前有多种途径可以挖掘到游客的旅游路线信息, 如:上传的旅游景点图片、基于GPS的旅游轨迹,以及旅游攻略与旅游日志［３］。因为上传的旅游景点图片只是旅游路线的部分景点,不是完整路线,作为训练数据会降低个性化推荐的准确性。而旅游攻略是对旅游过程的完整描述,旅游路线及游客兴趣等特征都容易获取,非常适合朴素贝叶斯方法。因此在本系统中,将以蜂窝网的旅游攻略作为数据来源［４］。

1系统概述

基于朴素贝叶斯方法的个性化旅游路线推荐系统由以下4部分组成,分别为:用户界面模块、游客旅游路线数据库、朴素贝叶斯训练模块、旅游路线排序模块［５］。不同模块在系统中承担不同功能。

该系统操作流程如下:1系统提供一个用户操作界面,在界面提供了旅游周期、人均旅游预算、游客关系、游客喜欢的景点类型、旅游季节、游客之间的关系等选项供用户选择。当用户按照提示将信息填写完整后,可以进入下一步;2系统后台调用数据库中存储的旅游路线信息,通过朴素贝叶斯模块预测用户在指定条件下最有可能选择的旅游路线;3界面将按照旅游路线的可能性降序排列,如果存在可能性一样的路线,将以旅游路线的获赞数为第二关键字降序排列,用户可根据自身需要选择合适的旅游路线。

该系统的核心模块是朴素贝叶斯训练模块。为方便实验,选择蜂窝网上1 000份张家界旅游攻略,作为贝叶斯模块学习的训练数据。而在训练过程中,最关键的部分是对训练数据的要求。不仅要求大量的训练样本,而且要求训练样本特征项与旅游路线相关。

为了得到充足的符合要求的旅游路线训练数据,进行了如下工作:首先利用网络爬虫技术［６］从蜂窝网上抓取1 000份张家界旅游攻略,然后通过人工方式将每一份攻略进行文本处理,挖掘与旅游路线相关的特征信息,具体特征包括旅游季节、旅游时间、旅游预算、游客之间关系、旅游路线、旅游路线获赞数、游客收入(可通过攻略内容进行推测)、游客职业、游客喜欢的旅游类型等,最后按一份攻略一条记录的形式存放在MySql数据库中。

因为不同特征项会产生不同的旅游路线,从而影响用户决策［７］,所以本系统首先全面考虑影响旅游路线选择的相关因素,然后通过特征项的选择算法C4.5算法进行甄选,最后产生了如下特征项:1旅游时间;2旅游季节、旅游时间;3每天的人均旅游预算;4游客喜欢的景点类型之间的关系;5游客年龄构成,具体而言指是否包含儿童或老年人。

2朴素贝叶斯学习模块实现过程

2.1朴素贝叶斯方法原理

朴素贝叶斯方法即在满足用户指定的特征项条件下, 求不同类别出现的概率,选择出现概率最大的类别作为预测结果。例如,本系统中假设用户指定特征项如下:旅游时间为1天,携带小孩老人,每天人均预算为400元人民币, 喜欢的景点类别为自然风光。而在数据库存储的所有旅游路线记录中,满足上述条件的旅游线路有3条,它们出现的概率分别是0.2、0.5、0.3。贝叶斯方法即将满足用户条件下出现概率最大的第2条旅游路线作为预测结果［２］。

2.2朴素贝叶斯定义

设T = {x１,x２...xｍ}为特征项集合,集合中的每一项xｉ都是一个特征属性。本系统中假设用户输入T集合的特征属性与值如表1所示。

设C = {y１,y２,..,yｎ}为类别集合,yｊ为一个分类。搜索数据库存储的训练样本,对旅游路线进行分类,集合C中的部分旅游线路如表2所示。

其中序号1的路线为y１,其它依此类推。

2.3计算过程

在上述定义基础上分别计算P(y１|T)、P(y２|T)、 P(yｎ|T)。最后求解yｋ,使满足公式(1):

2.4条件概率计算

在计算过程中,最关键的是计算满足特定条件下的分类概率,即条件概率。以计算P(y１|T)为例说明计算条件概率的过程,其它依此类推。P(y１|T)表示满足表1的特征条件下,游客选择序号为1的路线概率。根据贝叶斯定理,可以推导出公式(2):

而不妨假设本系统中的6个特征属性都相互独立,根据独立性推导出公式(3):

3推荐结果评价

推荐结果评价标准是召回率和准确率。召回率指系统推荐符合需求的旅游路线的数目除以系统中与需求相符合的旅游路线总数,而准确率则是系统推荐符合需求的旅游路线除以系统推荐的旅游路线总数。笔者通过随机模拟100个客户的需求方式,计算系统推荐的召回率与准确率。结果显示,100个随机模拟的用户产生推荐结果的准确率为0.73,召回率为0.61,结果较为理想。该结果也进一步说明采用朴素贝叶斯方法进行个性化旅游路线的推荐是可行的。

4结语

本文为个性化旅游路线的推荐提供了一种新的思路,即利用机器学习中的朴素贝叶斯方法实现个性化旅游路线推荐系统。本文介绍了该系统的基本功能,重点描述了朴素贝叶斯方法在预测旅游路线中的实现过程,并利用准确率与召回率两个指标对系统推荐效果进行评估。结果表明,使用朴素贝叶斯方法实现个性化旅游路线推荐是可行的。

参考文献

[1] 项亮.推荐系统实践[M].北京:人民邮电出版社,2012.

[2] JIAWEIHAN,MICHELINE KAMBER.数据挖掘概念与技术[M].范明,孟小峰,等,译.北京:机械工业出版社,2001.

[3] 李春明,王亚军,刘尹,等.基于地理参考照片的景区游客时空行为研究[J].旅游学刊,2013,10(28):30-35.

[4] 蚂蜂窝[EB/OL].http://www.mafengwo.cn/.

[5] CHAKPABORTY B.Integrating awareness in user oriented route recommendation system[C].The International Joint Conference on Neural Networks,New Jersey:IEEE Press,2012:1-5.

[6] 罗刚,王振东.自己动手写网络爬虫[M].北京:清华大学出版社,2010.

实例讨论朴素贝叶斯模型及其缺陷第4篇

一、两种模型

想要知道一只羊是绵羊还是山羊,可以从判别模型的方法来分析,从数据中来判别,然后通过观察这只羊的特征来预测这只羊是哪一种羊的概率。也就是说我们可以根据山羊的特征来学习一个山羊模型,再根据绵羊特征学习一个绵羊模型。最后从这只羊的特征中进行提取,放到山羊模型中看概率是多少,再放绵羊模型中看概率是多少,谁的概率大就是谁.

常见的判别模型有线性回归、对数回归、线性判别分析等等.常见的生成模型有朴素贝叶斯模型,高斯混合模型等等.

接下来我们重点介绍朴素贝叶斯模型.

二、朴素贝叶斯模型

假设要分类正常邮件和垃圾邮件,分类邮件是文本分类的一种应用.

假设采用最简单的特征描述方法,首先找一部英语词典,将里面的单词全部列出来。然后将每封邮件表示成一个向量,向量中每一维都是字典中的一个词的0/1值,1表示该词在邮件中出现,0表示未出现.

比如一封邮件中出现了“a”和“b u y”,没有出现“aardvark”、“aardwolf”和“zygmurgy”,那么可以形式化表示为:

假设字典中总共有5000个词,那么x是5000维的。这时候如果要建立多项式分布模型(二项分布的扩展).

某随机实验中有k个可能结果A1,A2,…,AK,它们概率分布分别是k,,,ppp21(43),那么在N次采样的结果中,A1出现n1次,而A2出现n2次,……,AK出现nk次,这个事件出现的概率公式为:

我们看出朴素贝叶斯假设是约束性很强的假设,“buy”一般来讲与“price”有关系,而我们假设条件独立.

于是建立模型的形式来表示:

想要数据上概率的乘积能最大,求最大似然估计为:

联合概率分布乘积最大,说明朴素贝叶斯是生成模型.

最后的式子是表示y=1的样本数占全部样本数的比例,前两个表示在y=01或的样本中,特征=1yX的比例.

而我们的要求是:

求出分子或分母,结论都是一样的。

如果把朴素贝叶斯方法扩展到x和y都有多个离散值的情况,对特特征是连续值的情况,可以采取分段的方式将连续值化为离散值,再采用信息增益的度量方法来转化为最优,这里不再叙述.

三、朴素贝叶斯的缺陷(拉普拉斯平滑)

朴素贝叶斯方法有个很明显且致命的缺陷,那就是对数据稀疏问题太敏感.

例如前面提到邮件分类,如果现在来了一封新邮件,标题为“NIPScallforpapers”。使用更大的网络字典(数目由5000变成35000)来分类,假设NIPS这个词在字典中的位置是35000。然而NIPS这个词没有在数据中出现过,这封邮件第一次出现了NIPS.那我们计算概率:

由于NIPS在以前的两种邮件(垃圾与正常)都没出现过,那么结果就是0.显然最后条件概率也是0.

因为我们特征概率条件独立,使用的是相乘来得到结果.

为了解决这个问题,给未出现的特征值,赋予一个小的值,而不是0.

具体的平滑方法:

假设离散型随机变量z有(1,2,3……k)个数.我们用来表示每个数的概率.假设有m个训练样本,z的观测值是,其中每一个观察值对应k个数中的一个.则根据原来的估计方法得到:

回到邮件分类的问题,则修改后的公式为:

基于群的朴素贝叶斯分类第5篇

对称性使人们在观察自然和认识自然过程中产生的一种观念, 自然界千变万化的运动, 从一个侧面来说, 往往显示出各式各样的对称样, 同时又通过这些对称性的演化和残缺来反映出运动演化的特点。对称性的描述定义有很多种, 从物理学出发, 对称性可以概括为:如果某一现象 (或系统) 在某一变换下不改变, 则说该现象 (或系统) 具有该变换所对应的对称性。

每一种对称性都和某种特定的变换相联系, 对称性的千差万别也就集中在与之相联系的各种变换上, 因此可以根据变换所涉及的对象以及变换的性质对对称性进行研究与分类。对于对称性的描述与研究最有效的数学工具是群论与群表示论。物理学中对称性研究相当多的部分运用群论来分析, 概括和研究物理学的规律。例如, 晶体中的对称性, 根据对称性的结构对晶体进行分类, 以及利用群论结果确定晶体中电子的波函数。另外一方面, 根据群论的抽象机制对宇宙中粒子的运动行为作出预测。

统计学家运用对称性对数据进行分析, 并且专门开发了一个研究方向:数据分析的对称性研究。对称性研究主要运用统计与代数分析复杂的结构性数据, 例如DNA分子结构, Sloan字体等具有对称性的数据。这些数据 (x) 由一个有限集合V作为索引或者标注, 有限集合V具有可以有群刻画的对称性, 或者V可以构成一个群。简而言之, 对称性研究利用具有对称性的数据索引方便的对数据{x (s) , s∈V}进行分类, 解释, 统计性分析。目前对称性研究主要用于短核苷酸序列索引的数据分析, 由Sloan字体的对称性索引的对比敏感度与熵的分析, 地质成分熵的分解, 初等平面图像对称索引的数据的分类与统计分析等。

既然物理学家与统计学家能够运用群论认识自然界数据的规律, 那么我们从数据分析的角度看, 利用数据中的对称性, 结合机器学习方法, 对数据进行分析, 其目的就是揭示这些数据具有的规律, 从而帮助用户提供解释的依据。对于具有复杂结构的某些数据, 我们采用李群, 李群结构是对学习问题很有用的一套理论工具, 李群之所以受人们关注, 一方面是李群有好的数学结构, 另一方面受到物理学家和化学家广泛使用李群方法来处理物理学中的晶体数据、有机物和无机物的数据、药物分子结构数据等这些复杂数据的启发。如何把李群运用到机器学习中, 以下文献提供了一个参考作用。

对于构成李群的数据, 我们采用李群学习范式分析数据的维数, 紧致性, 连通性, 子群, 陪集。但仍有一个问题必须解决:如何确保计算复杂度问题。李群存在着复杂的代数结构, 代数结构对于数据的分析有着至关重要的作用, 但与统计对比, 机器学习的代数方面的研究涉及的很少, 只保留在理论层面上, 原因之一是由于对象的巨大数量, 很难计算。

2 基于群的朴素贝叶斯学习基本框架

设想学习问题定义如下, 学习器L工作在实例空间X和假设空间H上, H上假设X上定义的某种实数值函数 (即H中每一个h为一函数:h, XR其中R代表实数集) , L面临的问题从H中抽取的目标函数h。如果实例空间X是一个可以用群G刻画的对称空间, 或者实例X是一个群, 则可以利用群作用于实例空间, 产生实例空间X的商空间X/G, 则假设空间H的h变换为h:X/GR。本文学习算法的基本框架见图2.1。

一般来说, 给定的样本数据具有隐藏的对称性, 无法直接作为实例空间X, 如DNA分子序列, 实例空间X的每个实例都相当于该样本数据提取的一个特征, 所以构造一个有序的实例空间 (特征空间) , 能够极大程度的反映不同DNA分子的差异。

2.1 构造实例空间X:

由于我们的算法主要针对分子序列分类, 所以直接从样本数据出发。

任何一个长度为的分子序列可以有一个函数s:PA表示, 其中P={1, 2, , }是字母表A的每个字母所处的有序位置的集合。典型的字母表比如:DNA分子序列的字母:A={A, G, T, C}, RNA分子的字母表:A={A, G, T, U}, 或者简单的二元字母表A={U, Y}, 嘌呤 (U=A或者U=G) 与嘧啶 (Y=C或者Y=T) 。Doi (1991) 提出有效的局部序列长度为2, 3, 4, 5, 6。│A│表示字母表中字母的个数。X表示长度为L的所有│A│-序列构成的空间。实例空间X有│A│个实例。

2.2 构造X的商空间

已知实例空间X具有│A│个实例 (特征) , 当较大时, 则会出维数灾难问题, 为了解决这个问题, 可以根据实例空间X的规律, 构造感兴趣的群对X进行划分, 不同的群将会对实例空间X产生不同的划分, 要结合具体问题构造不同的群。例如对于DNA分子序列构造的实例空间, 我们感兴趣的是序列中符号的构成关系, 所以一般选择n阶置换群Sn (n=2, 3, 4) 。

定义: (群作用) 群在一个集合V的作用是一个映射:φ:GVV, 且φ满足以下条件:对所有的s∈V, φ (1, s) =s, 对于所有的τ, δ∈G, s∈V, φ (σ, φ (τ, s) ) =φ (δτ, s) 。

根据φ, 对于s∈X, 群G作用在实例空间上产生的轨道为o={φτ (s) ;τ∈G}, 轨道空间中的任两个实例都是等价的, 在某一个群G作用下, X的所有轨道集合构成了一个X的另一个空间:商空间X/G, 即X=o1∪o2∪∪oλ, λ表示轨道的个数, oi (i=1, , λ) 表示第i个轨道空间, 则每一个轨道空间的实例 (特征) 都是等价的。如何确定轨道的个数λ, 我们引用Burnside引理:

Burns ide引理:若一个有限群作用实例空间X上, 则X中轨道的个数:

其中fix (τ) ={s∈X;φτ (s) =s}, 表示具有对称性τ的X中实例集合, │fix (τ) │表示具有对称性τ的X中实例的个数, │G│表示群G中元素的个数。

由于轨道oi的每个实例 (特征) 都是等价的, 则每个轨道就可以作为DNA分子序列的一个特征 (属性) , 使用字母ai表示。X的商空间的维数为λ, DNA分子序列的属性为 (a1, a2, , aλ) 。

2.3 构造假设空间H

由于H中的假设为X上定义的某种实数值函数h, 学习器L学习的空间X已经变成商空间X/G, 则h变化为:h:X/GR;X商空间的每个轨道oi作为一个函数h的一个变量xi (i=1, 2, , λ) , H的变量数为λ。由于我们采用群的划分方法, 轨道之间相互独立, 则变量之间相互独立。假设每个变量xi服从均值为μi, 方差为δi的高斯分布, 空间的H的个假设h的表达式为:

本文采用一般的统计学方法计算每个变量xi的均值μi与δi值, 举一个简单的例子说明:对于每个核苷酸, 统计每个实例空间中每个实例在DNA分子中出现的频数, 比如, 已知DNA分子序列,

则每个实例的频数为

构造的实例空间X为:X={s:QA}, 其中Q={1, 2, 3}, A={a, g, c, t}, 构造的实例空间共有64个实例, 构造的群为S3={1, (12) , (13) , (23) , (123) , (132) }, 则由Burnside引理计算出λ=35, 轨道划分如下:同一个轨道内的实例的频数相加。则可以计算出变量xi (i=1, 2, , λ) 的样本值, 然后使用统计的方法估计出每个变量的均值与方差。

2.4 朴素贝叶斯分类

朴素贝叶斯分类器应用到学习任务中, 每个样本数据由属性值的合取描述, 而目标函数h从商空间X/G中取值, 学习器L被提供一系列关于目标函数的训练样例以及新实例 (描述为属性值的元组) , 然后对新实例分类。贝叶斯方法的分类目标在给定描述实例 (DNA分子序列) 的属性值, 得到做可能的目标值hMAP。

使用贝叶斯公式重写为:

朴素贝叶斯分类器基于一个简单的假设:在跟定目标值时属性值之间相互条件独立。换言之, 该假定在给定实例的目标值情况下, 观察到联合的a1, a2, , aλ的概率等于每个单独属性的概率乘机:

将其代入式 (2.2) , 可以得到朴素贝叶斯所使用的方法:

其中hNB表示朴素贝叶斯分类器输出的目标值。

将2.1式代入式2.4得到:

基于群的朴素贝叶斯算法如下:

Exam ple s是不同的DNA分子序列的集合以及类别名。H是所有可能假设的集合此函数作用提取DNA分子的属性, 构造假设空间H, 计算属性分布的高斯参数。变量n表示每种类别的DNA分子序列。

1.依据Exam le s构造实例空间X= (w1, w2, , wn) ;

2.构造群G

3. 计算假设空间H的每个hj的每个变量xi的均值ui, 方差δi

对于H中每个假设hj:

对于类别为hj的每个example:

统计实例空间X每个实例wi的频数;

根据群G与wi计算轨道数λ;

划分实例空间X=o1∪o2∪∪oλ;

计算每个轨道oi的频数;

变量xi=oi (i=1, 2, , λ) ;

计算假设hj的每个变量的均值ui, 方差δi

对于DNA分子, 返回其估计的类别。

计算变量xi的值;

朴素贝叶斯方法第6篇

关键词：朴素贝叶斯,维规约,条件信息熵,主成分分析,独立成分分析

0 引言

在众多分类方法和理论中, 朴素贝叶斯NB (Naïve Bayes) 由于计算高效、精度高和具有坚实的理论基础而得到了广泛应用[1]。它基于一个简单的假定:在给定分类特征条件下属性之间相互独立。在现实世界中, 这种独立性假设经常是不满足的。因此, 许多学者研究学习贝叶斯网络 (Bayes Network) 来改进其分类性能, 然而要学习得到一个最优贝叶斯网络是个NP-hard问题[2]。如何能既保持朴素贝叶斯计算的简单性, 又可以提高其分类性能, 成为改进朴素贝叶斯学习的重要研究方向。

高维度数据中的信息往往主要包含在一个或几个低维结构中[3], 因此维规约技术是处理高维数据的一个重要手段。其形式分为属性选择和维变换[4]两种。对于属性选择, 文献[5]提出了基于条件信息熵的选择朴素贝叶斯算法。对于维变换, 主要有主成分分析 (PCA) 和独立成分分析 (ICA) 方法[6]。显然, 并不是这些方法对任何数据集 (或实际问题) 都有很好的效果。本文从避免 (或减弱) 朴素贝叶斯条件独立性假设出发, 从维规约的两个方向, 分别就基于条件信息熵的选择朴素贝叶斯 (CIESNB) 、基于主成分分析的朴素贝叶斯 (PCANB) 和基于独立成分分析的朴素贝叶斯 (ICANB) 的维规约效果和分类性能进行了研究。并通过在UCI数据集上的仿真实验, 详尽地分析、比较了几种维规约方法的降维效果和对朴素贝叶斯分类性能的影响。以利于根据数据本身特点, 采用不同的维规约方法提高朴素贝叶斯的分类性能。

1 朴素贝叶斯的相关模型

1.1 朴素贝叶斯模型

贝叶斯分类是基于贝叶斯公式, 即:

$Ρ (C | X) = \frac{Ρ (X | C) Ρ (C)}{Ρ (X)}$

其中, P (C|X) 为条件X下C的后验概率, P (C) 为C的先验概率, P (X|C) 为条件C下X的后验概率, P (X) 表示X的先验概率。

为叙述方便, 对符号作如下约定:用大写字母表示变量, C表示类别变量, A表示属性变量, 假定共有m个属性变量, A=<A1, A2, , Am>;用小写字母表示变量取值, Val (C) ={c1, c2, , cl}, Val (A) ={ai1, ai2, , aik}分别表示类别变量和属性变量的值域;用X表示待分类样本集, x=<a1, a2, , am>表示待分类样本;用T表示训练样本集, ti=<a1, a2, , am, cl>表示训练实例。在朴素贝叶斯中假设各属性相对于类别条件独立, 则有:

P (x $c_{l}) = \prod_{i = 1}^{m} Ρ (a_{i}$ cl) (1)

在实践中, 由于经常会对数值型变量进行分析, 则假设在m维空间中, ai对于x的似然函数呈多元正态分布, 则[7]:

P (x $c_{l}) = \frac{\exp (- \frac{1}{2} (x - μ_{l})^{Τ} \sum_{l}^{- 1} (x - μ_{l}))}{(2 π)^{m / 2} | \sum_{l} |^{1 / 2}} (2)$

其中, μl=E[x]是cl类的均值, ∑l是mm维协方差矩阵, 定义为∑l=E[ (x-μl) (x-μl) T]。

根据后验概率公式, 测试样本E被分在后验概率最大的类中, 则朴素贝叶斯分类模型为[1]:

$V_{n b} (E) = \underset{c}{\arg} \max Ρ (c) \prod_{i = 1}^{m} Ρ (a_{i}$ c) (3)

1.2 基于维规约的朴素贝叶斯模型

对高维度数据, 维度之间的条件独立性假设往往不成立, 同时由于维度高会给分类带来很大困难。然而, 高维度数据中的信息往往主要包括在一个或几个低维结构中[3], 因此从高维数据中提取有效信息的维规约技术是处理高维数据的一个重要手段。维规约技术, 从数学角度讲就是对于给定m维的数据向量x={x1, x2, , xm}, 在某种条件下, 寻找一个能反映原始数据信息的较低维的表示, 即s={s1, s2, , sp}, 使得pm (理想情况p<<m) , s的向量有时又被称为潜隐向量。基于维规约的朴素贝叶斯模型就是先对高维数据进行维规约, 再进行朴素贝叶斯分类, 其问题的关键就在于选择合适的维规约算法。

2 维规约算法

2.1 基于条件信息熵的属性选择算法

选择朴素贝叶斯的关键就在于如何选择属性, 即如何进行属性约简。文献[5]中提出了一种基于条件信息熵的决策表约简算法, 核心思想是根据决策表决策属性相对于条件属性的条件熵的确定性 (不变性) 进行约简。先求决策表的属性核, 而后根据其他条件属性相对于决策属性的条件熵从小到大逐个加入, 直到所选条件属性集相对于决策属性的条件熵与所有条件属性对决策属性的条件熵相等为止。

2.2 基于主成分分析的维变换算法

因此, 基于主成分分析方法是对原始数据进行预处理, 可以从原始观测数据的m元数据中抽取出互不相关的p元特征, 即原始数据的主成分[7]。具体步骤如下:

Step1 原始数据的标准化处理, 使每个属性均值为0, 方差为1;

Step2 计算Step1中得到的数据集X的相关系数矩阵R;

Step3 计算R的特征值λi及其对应的特征向量μi, i=1, 2, , m, 并将特征值按由大到小的顺序排列, 即λ1>λ2>>λm;

Step4 计算主成分的方差贡献率和累计方差贡献率, 主成分p值的选取一般为累计方差贡献率>85%的前p个特征值;

Step5 利用前p个特征值对应的特征向量u1= (u11, u12, , u1m) T, u2= (u21, u22, , u2m) T, , up= (up1, up2, , upm) T, 按Y=UX计算原始数据的主成分y1, y2, , yp。

2.3 基于独立成分分析的维变换算法

ICA最早是由文献[8]提出, 其目的是为非高斯分布数据找到一种线性变换, 使成分之间尽可能统计独立。统计上相互独立是一种比不相关更强的条件。独立肯定意味着不相关, 但反之不然。只有当f (x1, x2, , xm) 服从高阶正态分布, 两者才等价。对于高斯分布主成分分析就是独立成分分析。

ICA的一般线性模型 (不考虑噪声) 为X=AS, 其中X=[x1, x2, , xm]T为观测信号, S=[s1, s2, , sm]T为独立的源信号且各分量服从非高斯分布, A是nm混合矩阵。ICA的目的就是在仅知道X的情况下, 寻找nm混合矩阵A或mn解混矩阵 (又称为分离矩阵) W, 使Y=WX, 其中Y= (y1, y2, , ym) T且Y的各分量尽可能相互独立, 而Y逼近S, 从而得到源信号[8]。

问题的关键是如何度量分离结果的独立性, 鉴于ICA理论的基本出发点, 信号的独立性度量是通过它的非高斯性度量来实现的, 本文采用其中的负熵度量准则。我们采用一种快速ICA算法FastICA[9]对训练样本集进行独立分量提取。具体算法参见文献[9]。

3 仿真实验

为了对比分析前述几种维规约算法对朴素贝叶斯分类性能的影响, 选用了UCI机器学习数据库 (http://www.ics.uci.edu/～mlearn/MLRepository) 中的14个数据集作为测试数据, 这些数据集的基本信息如表1所示。

测试步骤:

Step1 对数据的预处理: (1) 用重庆邮电大学计算科学技术研究所研发的“基于Rough Set 的智能数据分析系统 (RIDAS) ”对数据集进行预处理 (用“条件组合补齐算法”进行补齐, 对基于条件信息熵的属性选择算法中用“基于属性重要性”的方法进行离散化, 其它两种算法无需离散化) ; (2) 如果某个属性的取值个数与样本数相等时, 它对分类的作用很小, 于是先将这样的属性去掉。

Step2 为了研究属性间相关系数的大小对维规约及分类性能的影响, 计算属性间的绝对平均相关系数 $| \bar{R} |$ 。

Step3 维规约:分别按第2节介绍的算法进行维规约, 其维规约后的属性数见表2。

Step4 将约规约后的数据集采用5重交叉验证 (5-fold cross-validation) 测试方法, 取5次测试精度的平均值作为这个数据集的测试结果, 详见表2。

注:1) NB, CIESNB, PCANB, ICANB分别表示朴素贝叶斯、基于条件信息熵的选择朴素贝叶斯、基于主成分分析和独立成分分析的朴素贝叶斯方法; $2) | \bar{R} |$ 表示属性间的绝对平均Pearson相关系数。

对几种算法的维规约效果和分类精度进行比较, 结果如表3、表4和图1所示。在表3和表4中w-t-l分别表示当前行所在方法比当前列所在方法性能优、相当和劣的数据集个数, 如表上中的“11-3-0”表示CIESNB算法比NB算法在11个数据集上能简化属性个数, 3个数据集上与NB算法相当的属性数目, 比NB属性数多的为0个数据集。

通过对几种算法测试结果的比较分析, 可以得出以下结论:

(1) CIESNB、PCANB和ICANB均能较大程度降低决策表中条件属性数的同时, 提高其分类精度;

(2) 在降维效果上, 基于主成分分析方法的作用最明显, 平均维数只占原来维数的37.5%, 独立成分分析方法其次;

(3) 在分类精度上, ICANB比PCANB和CIESNB方法都高, 其次是PCANB;

(4) 属性间相关性的大小对PCANB和ICANB分类性能影响较大, 当相关系数较大时, PCANB和ICANB改善分析性能的效果较显著;

(5) 在处理具有连续值属性时, 由于CIESNB需先对属性进行离散化, 这会导致部分信息的丢失, 反而会影响其分类性能。

4 结论及展望

本文从三种主要的维规约方法入手, 对基于条件信息熵的属性选择算法、基于主成分分析的维规约算法和基于独立成分分析的维规约算法对朴素贝叶斯分类性能的影响作了研究。并以UCI中的14个数据集为测试数据, 通过实验比较了几种维规约算法对朴素贝叶斯分类的降维效果和分类精度的影响。实验表明:几种方法均能在较大程度降低属性维数的同时提高其分类精度;在降维效果上主成分分析方法最明显, 在分类精度上独立成分分析方法最优。本文的另一重大发现是属性间相关性大小对基于主成分和独立成分算法的降维和分类性能有较大影响, 相关性越大效果越显著。最后, 在处理具有连续属性的数据集时, 如果对其进行离散化, 可能会导致部分信息丢失, 反而影响其分类性能。

由于改进朴素贝叶斯模型还很多, 如树增强型朴素贝叶斯、加权朴素贝叶斯等, 本文只研究了降维对贝朴素贝叶斯的影响, 是否可在降维的基础上再应用到其它改进模型上;此外, 由于本文所选用的数据集只有14个, 在其它数据集上的性能如何还需进一步研究;最后, 如何根据实际问题数据集的自身特点选择合适的维规约算法也是我们下一步努力的方向。

参考文献

[1]史忠植.知识发现[M].北京:清华大学出版社, 2002:169-220.

[2]Chickering D M.Learning Bayesian networks is NP-complete[M].NewYork:Springer.1996:121-130.

[3]李国英.关于高维、相依的不完全数据的统计分析[J].数学进展, 2002, 31 (3) :193-199.

[4]Ye J P, Li Q, Xiong H, et al.IDR/QR:An Incremental Dimension Re-duction Algorithm via QR Decomposition[J].IEEE Transactions onKnowledge and Data Engineering, 2005, 17 (9) :1208-1222.

[5]邓维斌, 黄蜀江, 周玉敏.基于条件信息熵的自主式朴素贝叶斯分类算法[J].计算机应用, 2007, 26 (4) :888-891.

[6]Bura E.Dimension Reduction Techniques:ARewies[EB/OL].2006.ht-tp://srccs.snu.ac.kr/Work-shop/04Statistics/7.pdf.

[7]Sergios Theodoridis, Konstantinos Koutroumbas.模式识别[M].3版.北京:电子工业出版社, 2006:7-44.

[8]Jutten C, Herault J.Independent component analysis versus PCA[C]//Proc of European Symposium on Signal Processing.1988:287-314.

朴素贝叶斯方法第7篇

1 基于分布估计算法的朴素贝叶斯分类器

1.1 分布估计算法

随着基础理论研究所取得的一系列进展,分布估计算法(estimation of distribution algorithms)以其较强的理论基础逐渐成为进化计算研究领域的一个新的研究方向,并成为当今国际进化算法研究的新热点。分布估计算法的基本思想就是使用概率的方法描述和表示每一代群体,并从个体中学习基因之间关系以及个体的适应度信息,利用学习到的信息生成性能更好的下一代群体[1,2]。

分布估计算法是遗传算法和统计学习的结合,通过统计学习的手段建立解空间内个体分布的概率模型,然后对概率模型随机采样产生新的群体,如此反复进行,实现群体的进化。分布估计算法中没有传统的交叉、变异等遗传操作,是一种全新的进化模式。这种优化技术能够通过概率图模型对变量之间的关系进行建模,从而能有效的解决多变量相关的优化问题[3]。周树德等全面系统的介绍分布估计算法这一新技术[4],并总结该算法的研究现状和未来的研究方向。文献[5]提出了一种自适应实值分布估计算法,借鉴遗传算法中关于种群多样性的性能指标,并根据该指标相应改变采样时方差的值,从而扩大搜索空间,提高种群多样性。文献[6]提出一种新的基于最大熵的分布估计算法,主要用基于最大熵估计种群中的模式概率分布,取代贝叶斯网络分布估计算法中的贝叶斯概率图模型。该算法无需进行贝叶斯网络学习,大大减少了计算量,而且还能获取更准确的概率分布估计。

分布估计算法在算法设计、理论研究和实际应用方面仍需要做很多工作。作为一种新型的优化技术,分布估计算法的核心是解空间的概率模型。针对特定的优化问题,综合考虑搜索空间的结构、概率模型的学习算法、样本产生算法等。选择合适的概率模型,是发挥分布估计算法性能的关键所在。分布估计算法的本质是统计学习与进化算法的结合,通过统计学习手段对群体中的数据进行分析和建模,以挖掘搜索空间结构的相关知识。采用机器学习的方法分析数据、指导搜索已经成为设计新算法的趋势。

1.2 基尼指数

基尼指数是一种非纯度的属性分裂方法,适用于类别、二进制、连续数值等类型的字段,是Breiman等人于1984年提出的,被广泛应用在CART算法、SLIQ算法、SPRINT算法和Intelligent Miner的决策树算法中。Gini指数度量数据划分或训练数据集的不纯度。尚文倩在[7]中提到改进的基尼指数算法,采用测量属性对于分类来说的“纯度”的形式,即数值越大,“纯度”越大,信息量越丰富,属性越好.并提出了一种新型的文本分类模型(IGIC),取得了良好的分类效果。

1.3 贝叶斯分类器

近年来,数据挖掘成为一个新的研究热点。分类作为一种重要的数据分析形式,由于其具有大量的应用,也引起了研究者越来越多的关注。用于大型数据库,贝叶斯分类已表现出高准确率和高速度。贝叶斯分类法是一种统计学分类方法,是机器学习和数据挖掘中最有效地学习方法之一[8]。通过分类算法的比较研究发现,一种称作朴素贝叶斯分类法(Na觙ve Bayesian classifier)的简单贝叶斯分类算法可以与决策树和经过挑选的神经网络分类算法相媲美[9]。朴素贝叶斯分类法的“朴素”是指它的条件独立性假设,而实际的问题中这种朴素假设往往不能够成立,虽然在某些不满足独立性假设的情况下它仍然可能获得较好的分类性能,但是,仍然需要通过各种方法来提高朴素贝叶斯分类器的性能[4,9,10]。

文献[11]提出一种改进的朴素贝叶斯模型,它对样本空间中那些可能有助于提高分类准确率的子集给予更多的关注,从而达到提高模型分类准确率的目的。文献[12]介绍了一种使用贝叶斯假设选择子集概率的方法。文献[12]提出了一种提高朴素贝叶斯分类器准确率的新算法BoostFSNB,并与相关算法进行了对比,结果表明该算法的应用能够提高分类器的准确率。文献[14]通过分析比较得出10折交叉验证能够获得更好的无偏性。董立岩等为了降低朴素贝叶斯分类模型的独立性假设约束,提出一种混合式朴素贝叶斯分类模型[15]。通过分析贝叶斯定理,该模型把条件属性集合划分成若干个独立的属性子集,然后用树增广朴素贝叶斯分类对属性子集分别进行分类学习,最后通过公式进行整合。张明卫等提出了一种基于相关系数的加权朴素贝叶斯分类模型[16],通过计算条件属性和决策属性之间的相关系数,对不同的条件属性赋予不同的权重,从而在保持简单性的基础上有效地提高了朴素贝叶斯算法的分类性能。文献[17]提出了一种属性加权朴素贝叶斯算法,该算法通过属性加权来提高朴素贝叶斯分类器性能,从训练数据中直接学习得到加权参数。权值可以看作是计算某个类的后验概率时某属性取值对该类别的影响程度。对各属性的每个取值采取不同的加权值,从而体现出各个属性的不同取值对分类的影响。文献[18]对分类方法的新发展进行了较详细的归纳,并总结了分类方法发展的趋势。

文献[19]提出学习近似模糊规则的混合遗传算法来生成模糊分类器。它使用一种新的方法来促进种群间的共同进化,即通过个体运行的混合进化机制来发现多个规则。为了提高学习规则的质量,它提出一种通过每一代的遗传操作产生性能优良的后代的局部搜索方法,最后从最后一代生成的种群中抽取规则集形成模糊分类器。文献[20]对8种离散化方法进行了对比研究,并将其分别应用到NB/FNB,LBR和AODE三种分类器上进行对比实验。文献[21]归纳总结了现有的改进贝叶斯算法,并提出了一个新的贝叶斯模型即隐式朴素贝叶斯。它由每个属性产生的父母来使其与其他属性结合在一起产生权重,并通过大量实验以不同的评价方法分别验证了该算法的有效性。文献[22]介绍了利用ROC曲线评价分类器性能的方法。文献[23]介绍了一种比分类精度更能准确反应分类器性能的新方法AUC评价。

1.4 贝叶斯与进化算法的结合

文献[24]首次将分布估计算法引入到分类器系统中,并与遗传算法进行了对比,结果显示分布估计算法要优于遗传算法。文献[25]提出了一个在基于概率的优化问题中使用贝叶斯推理技术的框架。基于这个框架,描述了一个简单的连续贝叶斯分布估计算法。文献[26]介绍了一个基于贝叶斯分类器在每一代进化中进行学习和模拟的新的进化计算方法。朱允刚提出了用遗传算法简化搜索空间然后进行贝叶斯结构学习算法[27],该算法的搜索空间小于目前多数算法的搜索空间。金哲提出了一种基于遗传算法的BAN分类器算法[28]。该算法对TAN分类器的结构进行了扩展,得到了一种受限制的BAN分类器。针对这种分类器的结构学习,设计了结合对数似然的适应度函数,并给出了网络结构的编码方案,设计了相应的遗传算子,使得该算法能够收敛到全局最优。文献[29]提出一种新的算法,该算法为避免数据预处理时,训练集的噪声及数据规模使属性约简的效果不太理想,并进而影响分类效果,在训练集上通过随机属性选取生成若干属性子集,并以这些子集构建相应的贝叶斯分类器,然后采用遗传算法进行优选。

2 结论

朴素贝叶斯在文本分类中的应用第8篇

文本分类是指在给定分类体系下, 根据文本内容确定文本类别的过程。目前, 文本分类的研究工作主要是研究如何运用统计学和机器学习的方法利用计算机对文本进行自动分类。文本分类是一个有指导的学习过程, 它根据一个已经被标注的训练文本集合, 找到文本属性 (特征) 和文本类别之间的关系模型 (分类器) , 然后利用这种学习得到的关系模型对新的文本进行类别判定。文本分类一般包括两个步骤:第一步, 通过样本训练, 利用样本和类别之间的联系, 建立一个样本分类函数;第二步, 通过样本分类函数, 对新文本进行分类。

贝叶斯理论被用于机器学习中, 是一种基于统计的机器学习技术, 由于其简单高效, 在很多领域都有广泛运用。在文本分类中, 根据贝叶斯公式, 分别计算文本属于不同类别的概率, 将文本归类于概率值最大的那一个类别。

1 贝叶斯理论

贝叶斯定理设样本空间为S, A为一个事件, B1, B2, , Bn为S的一个划分, 且P (A) >0, P (Bi) >0 (I=1, 2, , n) , 则

P (Bi) 是先验概率, P (Bi|A) 是后验概率, 是在事件A发生情况下Bi的概率, 公式 (1) 是贝叶分类算法的数学基础。贝叶斯分类就是利用已经观察到的样本信息, 根据贝叶斯公式来计算后验概率, 并以计算结果作为选择依据把样本归属到某个类别。

2 朴素贝叶斯文本分类器

构成文本的有意义的单元是词语, 文本的类别和文本出现的词语是有关联性的。假定文本可以用一组能表示文本类别的特征词来表示, 可以把这组特征词定义成文本的特征向量T (t1, t2, , tn) 。假设训练样本集中有m个不同的类别, C1, C2, , Cm, 要确定特征向量T属于哪个类别, 只需要计算每个类别的条件概率P (Ci|T) , 选取概率值最大的类别作为文本的类别。根据贝叶斯定理可得文本分类函数:

由全概率公式可知, 公式 (2) 可以写成:

朴素贝叶斯理论有一个重大假设, 即向量T是独立不相关的, 因此:

对于任意类别Ci的条件概率P (Ci|T) 都有相同的因子P (T) , 而确定文本类别的过程中关心的是P (Ci|T) 中哪个值最大, 而并不关心其具体值。为简化计算, 公式 (3) 可以写成:

公式 (5) 就是文本分类函数, 在分类函数中要先训练样本, 根据训练结果估算P (Ci) 和P (tj|Ci) 。朴素贝叶斯分类算法有两种模型:一种是贝努力事件模型, 一种是多变量事件模型。两种模型对P (Ci) 和P (tj|Ci) 估算方式不一样, 本文采用贝努力事件模型。

从公式 (5) 中可见, 贝叶斯分类中所有的特征词都对分类有贡献作用, 并不是一个或几个特征词决定分类, 因此特征词选取关系到分类准确性。术语停用词专指那些从文本分割出来的对分类不起作用的词语。对于停用词必须剔除掉, 一方面可以减少对分类的干扰, 另一方面可以降低特征向量的维数以减少计算量。

2.1 样本训练

分析训练集, 统计类别个数、类别名称等信息。利用分词工具将训练集S中每一篇样本切割成词语串, 去掉无意义的停用词, 形成文本的特征向量Ti (ti1, ti2, , tin) 。统计每个类别Ci中出现的特征词t以及t出现的次数;统计每个类别Ci的样本数量ni和训练集S中的样本总量N;统计每个类别Ci的特征词总数。样本训练的算法步骤如下:

S1:分析训练集, 统计类别信息;

S2:进入子类别;

S3:统计子类中的样本数量;

S4:读取样本, 文本切分, 形成特征向量;

S5:分析特征向量, 记录特征词t, 更新特征词t出现的次数, 记录样本特征词数量;

S6:重复S4, 对子类中所有的样本遍历一次, 统计子类中的特征词总量;

S7:重复S2, 对训练集中所有子类遍历一次, 统计训练集合中的样本总量。

2.2 分类计算

首先对测试文本进行文本切分, 去掉那些对文本归类不起作用的停用词, 形成文本的特征向量T (t1, t2, , tn) , 利用样本训练的结果, 对每个类别Ci计算条件概率P (Ci|T) 。

在计算条件概率P (Ci|T) 过程中需要计算类别Ci的先验概率P (Ci) , 利用公式 (6) 计算先验概率P (Ci) 。

其中, Ci表示类别i, ni表示类别Ci中的样本数量, N表示训练集中的样本总数。

对于每个特征词tj, 需要计算在类别Ci的条件概率P (tj|Ci) , 利用公式 (7) 可以计算条件概率P (tj|Ci) 。

其中, nji表示类别Ci中含特征词tj的样本数量, ni表示类别Ci中的单词数量, r为常量。

根据公式 (6) 、 (7) 的计算结果, 利用公式 (5) 计算出测试文本的特征向量T (ti, ti, , ti) 在每个类别Ci的条件概率P (Ci|T) , 比较每个类别的概率值, 取概率值最大的那一个类别作为测试文档归属的类别。算法步骤如下:

S1:分割测试文本, 形成特征向量T;

S2:计算类别Ci的先验概率P (Ci) ;

S3:计算特征词tj的条件概率P (tj|Ci) ;

S4:重复S3, 直至所有的特征词计算完毕;

S5:利用公式 (5) 计算出条件概率P (Ci|T) , 保存计算值;

S6:重复S2, 直至所有的类别都被计算一次;

S7:利用S5的计算值, 选择概率值最大的类别作为文档的类别。

2.3 具体实现

以Java作为开发语言实现了一个朴素贝叶斯文本分类器, 文本分类器由两个模块组成, 为训练模块和分类计算模块。图1是文本分类器的结构示意图。

样本训练模块完成对样本集的训练, 模块的输入是训练样本集, 模块的输出是训练结果, 作为分类计算模块的输入数据。在样本训练模块中, 设计了TrainedResult类作为保存训练结果的数据结构。在训练过程中需要对文本切分, 形成特征向量, 为此设计了DocmentSeperator类和StopWordsHandler类。每个类的功能如下:

StopWordsHandler类。停用词处理类, 剔除对分类不起作用的停用词。停用词包括单个汉字, 单个汉字容易被识别剔除掉, 对于词语只能编制停用词表, 通过词表判断是否属于停用词语。

DocmentSeperator类。文本切分类, 完成文本切分, 形成词语串。在这个类中使用了第三方的分词工具, 即中科院的汉语分词开源系统ICTCLAS。

TrainedResult类。训练结果类, 用于保存训练的结果。需要保存的样本信息包括每个类别C中出现的特征词t以及t出现的次数、每个类别C的样本数量、训练集S中的样本总量、每个类别C的特征词总数。

Trainer类。样本训练类, 完成对样本集的分析, 统计样本类别、样本数量。通过调用TrainedResult类和StopWordsHandler类提供的功能, 生成样本的特征向量, 分析特征向量, 统计特征词和特征词出现的次数, 形成训练结果。

分类计算模块完成对测试文本的分类计算, 模块的输入是测试文本和训练结果, 输出是类别的后验概率。分类计算模块只设计了ClassCalculate类, 该类对外提供类别Ci的后验概率P (Ci|T) 。内部实现包括计算类别Ci的先验概率、特征词tj的后验概率P (tj|Ci) , 并利用公式 (5) 计算P (Ci|T) 。

在分类计算模块中可以对测试文本的后验概率的计算做一定优化, 对于分类贡献大的特征词提高其权重。TF-IDF (term frequency-inverse document frequency) 是一种常用的加权技术, 其思想是:特征词在某一特定文件内是高频词, 而在整个文件集合中是低频词, 这个特征词对分类贡献大, 应该取得大的权重。TF-IDF倾向于过滤掉常见词语, 保留重要词语。文档频率TF (term frequency) 是指在某篇文档中, 某特征词出现的频率, 特征词t在TF中的计算公式TFt=|Dit|/|Di|, 其中|Dit|表示特征词t在文档Di出现的次数, |Di|表示文档Di中出现的词语总数。逆文档频率IDF (inverse document frequency) 是用来度量特征词的普遍重要性, 特征词t的IDF计算公式IDFt=log ( (|D|) /1+|Dt|) , 其中|D|表示文档总数, |Dt|表示包含特征词t的文档数量。TF-IDF表示TFt和IDFt的乘积, 能够体现特征词t对文本分类的贡献, 可以提高分类的性能。在实现过程引入了TF-IDF作为权重, 对公式 (5) 作了修正。

文本分类器由NaiveBayesClassifier类实现, 完成样本集的训练和测试文本的分类计算, 数据的输入是训练样本集和测试集。

3 试验结果

试验语料采用搜狗实验室免费共享的语料库, 语料库中的文档分为9个类别, 共计17 910篇文档, 从每个类别中抽取一部分作为训练样本, 余下的作为测试样本。试验测试数据显示, 平均分类正确率到达74.2%以上。在分类器的实现中还可以作进一步的改进, 为了节省训练时间, 训练模块可以把训练结果用中间文件保存起来, 在训练之前对中间文件做一个判断, 如果存在中间文件, 直接加载中间文件, 否则按提供的样本集训练。

4 结语

用朴素贝叶斯进行文本分类有较好的分类效果, 但这种文本分类方法还有很大的改进余地, 可以进一步提高分类的效率和精度。分类函数要能体现每个特征词对分类的贡献程度, 形成非线性的加权公式。特征词提取要尽可能去掉对分类无意义的词语, 降低特征向量的维度。朴素贝叶斯理论假设特征词是相互独立的, 即一个词语的出现与其它词语的出现无关, 这在实际情况中往往不成立。

摘要：朴素贝叶斯理论是一种典型机器学习技术, 能够应用于文本分类中。运用朴素贝叶斯理论阐述了贝叶斯分类器的样本训练和分类计算的过程, 构造了一个文本分类器。试验表明, 朴素贝叶斯理论在文本分类中有较好的分类效果。

关键词：中文信息处理,文本分类,机器学习,朴素贝叶斯

参考文献

[1]张征杰, 王自强.文本分类及算法综述[J].电脑知识与技术, 2012, (4) .

[2]刘颖.贝叶斯方法在文本分类预处理中的应用[J].电脑与信息技术, 2010 (6) .

[3]杨凯峰, 张毅坤, 李燕.基于文档频率的特征选择方法[J].计算工程, 2010 (17) .

[4]搜狗实验室语料库[DB/OL].http://www.sogou.com/labs/dl/c.html.

[5]陈叶旺, 余金山.一种改进的朴素贝叶斯文本分类方法[J].华侨大学学报:自然科学版, 2011 (4) .

朴素贝叶斯方法

朴素贝叶斯方法第1篇

朴素贝叶斯方法第2篇

朴素贝叶斯方法第3篇

实例讨论朴素贝叶斯模型及其缺陷第4篇

基于群的朴素贝叶斯分类第5篇

朴素贝叶斯方法第6篇

朴素贝叶斯方法第7篇

朴素贝叶斯在文本分类中的应用第8篇

朴素贝叶斯方法

猜你喜欢

栏目

最近更新

热门标签

朴素贝叶斯方法

朴素贝叶斯方法 第1篇

朴素贝叶斯方法 第2篇

朴素贝叶斯方法 第3篇

实例讨论朴素贝叶斯模型及其缺陷 第4篇

基于群的朴素贝叶斯分类 第5篇

朴素贝叶斯方法 第6篇

朴素贝叶斯方法 第7篇

朴素贝叶斯在文本分类中的应用 第8篇

朴素贝叶斯方法

猜你喜欢

栏目

最近更新

热门标签

朴素贝叶斯方法第1篇

朴素贝叶斯方法第2篇

朴素贝叶斯方法第3篇

实例讨论朴素贝叶斯模型及其缺陷第4篇

基于群的朴素贝叶斯分类第5篇

朴素贝叶斯方法第6篇

朴素贝叶斯方法第7篇

朴素贝叶斯在文本分类中的应用第8篇