《人工智能原理.pptx》由会员分享，可在线阅读，更多相关《人工智能原理.pptx（146页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、会计学1人工智能原理人工智能原理2小小 结结1 1、盲目搜索、盲目搜索2 2、启发式搜索、启发式搜索 总之搜索策略是人工智能研究的核心问题之一，已有许多成熟的结果，并在解决人工智能的有关问题中得到广泛应用。但目前仍有若干深入的问题有待发展，特别是结合实际问题，探索有效实用的策略仍是一个研究和开发的工作，还应当给予足够的重视。第1页/共146页31 搜索引擎搜索引擎n n搜索引擎系统一般由蜘蛛（也叫网页爬行器）、切词器、索引器、查询器几部分组成。蜘蛛负责网页信息的抓取工作，一般情况下切词器和索引器一起使用，它们负责将抓取的网页内容进行切词处理并自动进行标引，建立索引数据库。查询器根据用户查询条件
2、检索索引数据库并对检索结果进行排序和集合运算，如并集、交集运算，再提取网页简单摘要信息反馈给查询用户。第2页/共146页41 搜索引擎搜索引擎n nGoogleGoogle搜索引擎从功能上同样分为三大部分：网搜索引擎从功能上同样分为三大部分：网页爬行、标引入库和用户查询。网页爬行主要负页爬行、标引入库和用户查询。网页爬行主要负责网页的抓取，由责网页的抓取，由URLURL服务器、爬行器、存储器、服务器、爬行器、存储器、分析器和分析器和URLURL解析器组成解析器组成,n n爬行器是该部分的核心；标引入库主要负责对网爬行器是该部分的核心；标引入库主要负责对网页内容进行分析，对文档进行标引并存储到数
3、据页内容进行分析，对文档进行标引并存储到数据库里，该模块涉及许多文件和数据；用户查询主库里，该模块涉及许多文件和数据；用户查询主要负责分析用户输入的检索表达式，匹配相关文要负责分析用户输入的检索表达式，匹配相关文档，把检索结果返回给用户，由查询器和网页级档，把检索结果返回给用户，由查询器和网页级别评定器组成，其中别评定器组成，其中网页等级的计算网页等级的计算是该部分的是该部分的核心。核心。第3页/共146页51 搜索引擎搜索引擎n n搜索引擎的主要工作流程是：首先从蜘蛛开始，蜘蛛程序搜索引擎的主要工作流程是：首先从蜘蛛开始，蜘蛛程序每隔一定的时间（每隔一定的时间（googlebotgoogle
4、bot）自动启动并读取网页）自动启动并读取网页URLURL服务服务器上的器上的URLURL列表，按深度优先或广度优先算法，抓取各列表，按深度优先或广度优先算法，抓取各URLURL所指定的网站，将抓取的网页分配一个唯一文档所指定的网站，将抓取的网页分配一个唯一文档ID(DocId)ID(DocId)，压缩存入文档数据库。并将当前页上的所的超链接存入，压缩存入文档数据库。并将当前页上的所的超链接存入到到URLURL服务器中。在进行抓取的同时，切词器和索引器将已服务器中。在进行抓取的同时，切词器和索引器将已经抓取的网页文档进行切词处理，并按词在网页中出现的经抓取的网页文档进行切词处理，并按词在网页中
5、出现的位置和频率计算权值，然后将切词结果存入索引数据库。位置和频率计算权值，然后将切词结果存入索引数据库。整个抓取工作和索引工作完成后更新整个索引数据库和文整个抓取工作和索引工作完成后更新整个索引数据库和文档数据库，这样用户就可以查询最新的网页信息。查询器档数据库，这样用户就可以查询最新的网页信息。查询器首先对用户输入的信息进行切词处理，并检索出所有包含首先对用户输入的信息进行切词处理，并检索出所有包含检索词的记录，通过计算网页权重和级别对查询记录进行检索词的记录，通过计算网页权重和级别对查询记录进行排序并进行集合运算，最后从文档数据库中提取各网页的排序并进行集合运算，最后从文档数据库中提取各
6、网页的摘要信息反馈给查询用户摘要信息反馈给查询用户第4页/共146页6什么是什么是PageRank?n nPageRank(PageRank(网页级别网页级别)是是GoogleGoogle用于评测一个网页用于评测一个网页“重要性重要性”的一种方法。的一种方法。在揉合了诸如在揉合了诸如TitleTitle标识和标识和KeywordsKeywords标识等所有其它因素之后，标识等所有其它因素之后，GoogleGoogle通过通过PageRankPageRank来调整结果，使那些更具来调整结果，使那些更具“重要性重要性”的网页在搜索结果中令网站排的网页在搜索结果中令网站排名获得提升，从而提高搜索结果
7、的相关性和质量。名获得提升，从而提高搜索结果的相关性和质量。n n简单说来，简单说来，GoogleGoogle通过下述几个步骤来实现网页在其搜索结果页通过下述几个步骤来实现网页在其搜索结果页(SERPS)(SERPS)中的排名：中的排名：n n1)1)找到所有与搜索关键词匹配的网页找到所有与搜索关键词匹配的网页n n2)2)根据页面因素如标题根据页面因素如标题 关键词密度等排列等级关键词密度等排列等级n n3)3)计算导入链接的锚文本中的关键词计算导入链接的锚文本中的关键词n n4)4)通过通过PageRankPageRank得分调整网站排名结果得分调整网站排名结果第5页/共146页7Page
8、Rank from googlePageRankPageRank，有效地利用了，有效地利用了 WebWeb所拥有的庞大链接构造的特所拥有的庞大链接构造的特性。性。从网页从网页A A导向网页导向网页B B的链接被看作是对页面的链接被看作是对页面A A对页面对页面B B的的支持投票，支持投票，GoogleGoogle根据这个投票数来判断页面的重要性。可根据这个投票数来判断页面的重要性。可是是 GoogleGoogle不单单只看投票数不单单只看投票数(即链接数即链接数)，对投票的页面也进，对投票的页面也进行分析。重要性高的页面所投的票的评价会更高，因为行分析。重要性高的页面所投的票的评价会更高，因为
9、接受这个投票页面会被理解为重要的物品。接受这个投票页面会被理解为重要的物品。根据这样的分析根据这样的分析,得到了高评价的重要页面会被给予较高得到了高评价的重要页面会被给予较高的的 PageRank(PageRank(网页等级网页等级)，在检索结果内的名次也会提高。，在检索结果内的名次也会提高。PageRankPageRank是是 GoogleGoogle中表示网页重要性的综合性指标，而且中表示网页重要性的综合性指标，而且不会受到各种检索不会受到各种检索(引擎引擎)的影响。倒不如说，的影响。倒不如说，PageRankPageRank就是就是基于对基于对“使用复杂的算法而得到的链接构造使用复杂的算
10、法而得到的链接构造”的分析，从而的分析，从而得出的各网页本身的特性。得出的各网页本身的特性。当然，重要性高的页面如果和检索词句没有关联同样也没当然，重要性高的页面如果和检索词句没有关联同样也没有任何意义。为此有任何意义。为此 GoogleGoogle使用了精练后的文本匹配技术，使用了精练后的文本匹配技术，使得能够检索出重要而且正确的页面。使得能够检索出重要而且正确的页面。从许多优质的网页链接过来的网页，必定还是优质网页从许多优质的网页链接过来的网页，必定还是优质网页从许多优质的网页链接过来的网页，必定还是优质网页从许多优质的网页链接过来的网页，必定还是优质网页 第6页/共146页8PageRa
11、nk 概念图概念图(引自 Page et al.(1998)Figure 2 Simplified Page Calculation)第7页/共146页9PageRank的计算方法的计算方法PageRank(A)=(1-d)+d(PageRank(T1)/C(T1)+.+PageRank(A)=(1-d)+d(PageRank(T1)/C(T1)+.+PageRank(Tn)/C(Tn)PageRank(Tn)/C(Tn)其中其中PageRank(A)PageRank(A)表示给定页面表示给定页面A A的的PageRankPageRank得分；得分；DD为阻尼因子，一般设为为阻尼因子，一般设为
12、0.850.85；PageRank(T1)PageRank(T1)表示一个指向表示一个指向A A页的网站其本身的页的网站其本身的PageRankPageRank得分；得分；C(T1)C(T1)表示该页面所拥有的导出链接数量；表示该页面所拥有的导出链接数量；PageRank(Tn)/C(Tn)PageRank(Tn)/C(Tn)表示为每一个指向表示为每一个指向A A页的页面重复相同的操页的页面重复相同的操作步骤。作步骤。第8页/共146页10n nA A页的外部链接页的外部链接B B能够带给能够带给A A的的PageRankPageRank得分与得分与B B的导出链接数量成反比，即随着的导出链接
13、数量成反比，即随着B B上导出链接数上导出链接数的增加，带给的增加，带给A A的的PageRankPageRank得分亦随之降低。这得分亦随之降低。这同样表明了一个网页的同样表明了一个网页的PageRankPageRank得分是该网页对得分是该网页对其它页面投票的一个基本的度量形式。一个网页其它页面投票的一个基本的度量形式。一个网页可以投票给一个或多个导出链接，但其总投票权可以投票给一个或多个导出链接，但其总投票权一定，并被平均分配给所有的导出链接。假设一定，并被平均分配给所有的导出链接。假设B B的的PageRankPageRank得分是得分是5 5，且，且B B上只有一条指向上只有一条指向
14、A A的链的链接，那么接，那么A A将获得将获得B B全部的全部的PageRankPageRank得分得分(B(B没有损没有损失任何东西，而失任何东西，而A A赢得了赢得了B B的的PageRankPageRank得分得分)。但。但如果如果B B上有上有NN个链接，则个链接，则A A只能得到只能得到B B的的PageRankPageRank得分的得分的NN分之一。分之一。第9页/共146页11导入链接导入链接n n导入链接时，一般总是容易陷入这样的误区：只看链接页的PageRank得分，得分越高就越好。而事实上，一个链接页的PageRank得分遵循平均分配原则被平均分配给该页面上的所有链接。所
15、以，只注重外部链接的PageRank得分的链接策略无疑是片面的。正确的做法应该是既要考虑链接页的PageRank，又要考虑该页的链接数量第10页/共146页12导出链接导出链接 导出链接并不会损失PageRank，但网站整体的PageRank将会降低。所以，选择导出链接时宜遵循这样的定律：1.尽量保持自己网站的PageRank 2.尽量使内部页面分得尽可能多的PageRank第11页/共146页13Suggestion from Google 选择导入链接时应首先考虑对方网站的内容如何，选择导入链接时应首先考虑对方网站的内容如何，然后再考察其导出链接的数量进行决策。而在建立然后再考察其导出链接
16、的数量进行决策。而在建立本站的导出链接时则应尽量使自己网站的本站的导出链接时则应尽量使自己网站的PageRankPageRank维持在最大回馈和最小流失上。维持在最大回馈和最小流失上。应确保合理的网站设计结构和内部联接方式。网应确保合理的网站设计结构和内部联接方式。网站的结构和内部联接方式也会对站的结构和内部联接方式也会对PageRankPageRank产生影响，产生影响，可利用其特性有效进行可利用其特性有效进行PagaRankPagaRank在网站内部页面的在网站内部页面的再分布及尽可能保持网站整体的再分布及尽可能保持网站整体的PageRankPageRank。网站的网站的PageRankP
17、ageRank的提升应与该网站的访问者体验的提升应与该网站的访问者体验息息相关。即使获得再高的息息相关。即使获得再高的PageRankPageRank，如果没有客，如果没有客户访问，一样毫无价值。所以网站的内容始终是提户访问，一样毫无价值。所以网站的内容始终是提升升PageRankPageRank最关键的因素之一。最关键的因素之一。第12页/共146页142 数据挖掘概念数据挖掘概念-定义定义数据挖掘数据挖掘数据挖掘数据挖掘-从大量数据中寻找其规律的技术，从大量数据中寻找其规律的技术，从大量数据中寻找其规律的技术，从大量数据中寻找其规律的技术，是统计学、数据库技术和人工智能技术的综合。是统计学
18、、数据库技术和人工智能技术的综合。是统计学、数据库技术和人工智能技术的综合。是统计学、数据库技术和人工智能技术的综合。数据挖掘与统计学数据挖掘与统计学数据挖掘与人工智能数据挖掘与人工智能数据挖掘与数据库技术数据挖掘与数据库技术数据挖掘与数据挖掘与数据挖掘与数据挖掘与KDDKDD第13页/共146页152 数据挖掘概念数据挖掘概念-原由原由数据挖掘数据挖掘数据库越来越大数据库越来越大有价值的知有价值的知识识可怕的数据可怕的数据第14页/共146页162 数据挖掘概念数据挖掘概念-原由原由数据爆炸，知识贫乏数据爆炸，知识贫乏 苦恼:淹没在数据中;不能制定合适的决策!数据数据知识知识决策决策n模式模
19、式n趋势趋势n事实事实n关系关系n模型模型n关联规则关联规则n序列序列n目标市场目标市场n资金分配资金分配n贸易选择贸易选择n在哪儿做广告在哪儿做广告n销售的地理位置销售的地理位置n金融金融n经济经济n政府政府nPOS.n人口统计人口统计n生命周期生命周期第15页/共146页172 数据挖掘概念数据挖掘概念-发展发展1989 IJCAI会议：会议：数据库中的知识发现讨论专题数据库中的知识发现讨论专题Knowledge Discovery in Databases(G.Piatetsky-Shapiro and W.Frawley,1991)1991-1994 KDD讨论专题讨论专题Advanc
20、es in Knowledge Discovery and Data Mining(U.Fayyad,G.Piatetsky-Shapiro,P.Smyth,and R.Uthurusamy,1996)1995-1998 KDD国际会议国际会议(KDD95-98)Journal of Data Mining and Knowledge Discovery(1997)1998 ACM SIGKDD,SIGKDD1999-2002 会议会议,以及以及SIGKDD Explorations数据挖掘方面更多的国际会议数据挖掘方面更多的国际会议PAKDD,PKDD,SIAM-Data Mining,(I
21、EEE)ICDM,DaWaK,SPIE-DM,etc.第16页/共146页18 n n关联规则发现的主要对象是交易型数据库，一个交关联规则发现的主要对象是交易型数据库，一个交易一般由交易处理时间，一组顾客购买的物品，有易一般由交易处理时间，一组顾客购买的物品，有时也有顾客标识号时也有顾客标识号(如信用卡号如信用卡号)组成。组成。n n定义定义3.23.2：关联规则关联规则关联规则关联规则是描述在一个交易中是描述在一个交易中物品之间同时出现的规律的知识模式，物品之间同时出现的规律的知识模式，更确切的说，关联规则是通过量化的数更确切的说，关联规则是通过量化的数字描述物品字描述物品X X的出现对物品
22、的出现对物品Y Y的出现有多的出现有多大的影响。大的影响。关关 联联 规规 则则第17页/共146页19 以零售业为例，体育用品商场通过对销以零售业为例，体育用品商场通过对销售数据进行关联分析通常可以发现这售数据进行关联分析通常可以发现这些数据中常常隐含形式如下的规律些数据中常常隐含形式如下的规律“购买篮球的顾客中有购买篮球的顾客中有70%70%的人同时的人同时购买篮球运动服，所有交易中有购买篮球运动服，所有交易中有40%40%的人同时购买篮球和篮球运动服的人同时购买篮球和篮球运动服”等等等。这些规律即等。这些规律即关联规则关联规则关联规则关联规则。关关 联联 规规 则则第18页/共146页2
23、0n n定定义义3.33.3：关联规则挖掘的交易数据集记为D（一般为交易数据库），DT1，T2，Tk，,Tn，Tk（k1,2,，n）称为交易，对应每一个交易有唯一的标识，记作TID。n n元素im（m1,2,，p）称为项。设I=i1，i2，im是D中全体项组成的集合，且TkI。交易号交易号（TID）项集合项集合（Itemsets）T100 I1，I2，I5 T200 I2，I4 T300 I2，I3 T400 I1，I2，I4 T500 I1，I3 设X是一个I中项的集合，如果XTk，那么称交易Tk包含项集X。若若X,Y为项集，为项集，X I,Y I，并且并且X Y=，则形如，则形如X=Y的表
24、达式称为的表达式称为关联规关联规关联规关联规则则则则。关联规则形式化定义关联规则形式化定义第19页/共146页21置信度置信度支持度支持度 关联规则度量关联规则度量规则XY在交易数据集D中的置信度置信度置信度置信度是对关联规则准确度的衡量。度量关联规则的强度。即在所有出现了X的活动中出现Y的频率，即规则XY的必然性有多大。记为confidence(Xconfidence(Xconfidence(Xconfidence(XY)Y)Y)Y)。计算方法：包含X和Y的交易数与包含X的交易数之比：confidence(XY)=P(YX)=|T:XYT，TD|/|T:XT，TD|100%规则XY在交易数据
25、集D中的支持度支持度支持度支持度是对关联规则重要性的衡量，反映关联是否是普遍存在的规律，说明这条规则在所有交易中有多大的代表性。即在所有交易中X与Y同时出现的频率记为：support(Xsupport(Xsupport(Xsupport(XY)Y)Y)Y)。计算方法：交易数据集中同时包含X和Y的交易数与所有交易数之比：support(XY)=P(XY)=|T:XYT，TD|/|D|100%（其中|D|是交易数据集D中的所有交易数）第20页/共146页22最小置信度阈值最小置信度阈值最小支持度阈值最小支持度阈值同时满足最小置信度阈值最小置信度阈值和最小支持度最小支持度阈值阈值的关联规则为强关联规
26、则强关联规则强关联规则强关联规则，是有意义有价值。关联规则度量关联规则度量第21页/共146页23 在给定一个交易数据集在给定一个交易数据集D D，挖掘关，挖掘关联规则问题就是产生支持度和置联规则问题就是产生支持度和置信度分别大于用户给定的信度分别大于用户给定的最小支最小支持度阈值持度阈值和和最小置信度阈值最小置信度阈值的关的关联规则。联规则。关联规则度量关联规则度量第22页/共146页24经常使用的“支持度-可信度”的框架。这样的结构有时会产生一些错误的结果。例：假设体育类用品零售商调查了10000名顾客在购买什么商品，得到的结果是6000名顾客购买篮球，7500名顾客购买足球，4000名顾
27、客购买篮球、足球。设最小支持度为30%，最小置信度为60%，可得到如下的关联规则：篮球足球（支持度40%，置信度为66%）这条规则其实是错误的，因为购买足球的比例是75%，甚至大于66%。关联规则度量关联规则度量第23页/共146页25名称描述公式置信度X出现的前提下，Y出现的频率P(Y|X)支持度X、Y同时出现的频率 P(XY)期望可信度 Y出现的频率 P(Y)改善度 置信度对期望可信度的比值 P(Y|X)/P(Y)关联规则度量关联规则度量第24页/共146页26找出所有具有最小支持度的项集找出所有具有最小支持度的项集(频繁项集频繁项集)。用用AprioriApriori、FP-Growth
28、等算法来找出频繁等算法来找出频繁项集。项集。使用频繁项集生成期望的关联规则使用频繁项集生成期望的关联规则对于每一个频繁项集对于每一个频繁项集l l，找出其中所有的非空，找出其中所有的非空子集；然后，对于每一个这样的子集子集；然后，对于每一个这样的子集a a，如果，如果support(l)support(l)与与support(a)support(a)的比值大于最小可信的比值大于最小可信度，则存在规则度，则存在规则a=(l-a)a=(l-a)。挖掘交易数据库挖掘交易数据库D D中所有关联规则的问题可以中所有关联规则的问题可以被划分为两个子问题：被划分为两个子问题：第25页/共146页27找出频繁
29、项集找出频繁项集AprioriApriori算法算法 n n Apriori性质性质n n Apriori算法基本思想算法基本思想第26页/共146页28交易号交易号项集合项集合T100 I1，I2，I5 T200 I2，I4 T300 I2，I3 T400 I1，I2，I4 T500 I1，I3 T600 I2，I3 T700 I1，I3 T800 I1，I2，I3，I5 T900 I1，I2，I3 表1交易数据库D例：例：找出频繁项集找出频繁项集AprioriApriori算法算法第27页/共146页29项集支持度计数I16I27I36I42I52项集支持度计数I16I27I36I42I5
30、2C1L1扫描D，对每个候选计数比较候选支持度计数与最小支持度计数找出频繁1项集的集合L1找出频繁项集找出频繁项集AprioriApriori算法算法例：最小支持度阈值为2第28页/共146页30项集支持度计数I16I27I36I42I52项集I1，I2I1，I3I1，I4I1，I5I2，I3I2，I4I2，I5I3，I4I3，I5I4，I5L1C2由L1产生候选C2Lk-1用于产生候选Ck找出频繁项集找出频繁项集AprioriApriori算法算法连接连接&剪枝剪枝第29页/共146页31项集支持度计数I1，24I1，34I1，41I1，52I2，34I2，42I2，52I3，40I3，51
31、I4，50项集支持度计数I1，24I1，34I1，52I2，34I2，42I2，52C2L2比较候选支持度计数与最小支持度计数扫描D，对每个候选计数第30页/共146页32项集支持度计数I1，I24I1，I34I1，I52I2，I34I2，I42I2，I52L2项集I1，I2，I3I1，I2，I5由L2产生候选C3C3连接连接&剪枝剪枝第31页/共146页33连接：C3L2 L2I1,I2,I1,I3,I1,I5,I2,I3,I2,I4,I2,I5 I1,I2,I1,I3,I1,I5,I2,I3,I2,I4,I2,I5=I1,I2,I3,I1,I2,I5,I1,I3,I5,I2,I3,I4,I
32、2,I3,I4,I2,I3,I5,I2,I4,I5第32页/共146页34剪枝：I1,I2,I3的2-项子集是I1,I2,I1,I3和I2,I3。I1,I2,I3的所有2-项子集都是L2的元素。因此，保留I1,I2,I3在C3中。I2,I3,I5的2-项子集是I2,I3,I2,I5和I3,I5。I3,I5不是L2的元素，因而不是频繁的。因此，由C3中删除I2,I3,I5。剪枝后C3I1,I2,I3,I1,I2,I5。第33页/共146页35项集支持度计数I1，I2，I32I1，I2，I52C3扫描D，对每个候选计数比较候选支持度计数与最小支持度计数项集支持度计数I1，I2，I32I1，I2，I
33、52L3对每个交易，使用对每个交易，使用subsetsubset函数找出交易函数找出交易中是候选的所有子集，并对每个这样的中是候选的所有子集，并对每个这样的候选累加计数，所有满足最小支持度的候选累加计数，所有满足最小支持度的候选形成频繁项集候选形成频繁项集L L。第34页/共146页36 输入：交易数据库D；最小支持度阈值min_sup。输出：D中的频繁项集L。方法：(1)找频繁项集1-项集;(2)apriori_gen(Lk-1,min_sup)函数做两个动作：连连连连接接接接和和和和剪剪剪剪枝枝枝枝。用于在第k-1次遍历中生成的Lk-1生成Ck(3)由Ck生成Lk AprioriAprio
34、ri算法详述算法详述第35页/共146页37 子集函数子集函数SubsetSubset？子集函数Subset用于确定在一个给定的交易t中包含了哪些Ck中的项。候选集Ck被存放在一棵hash树中，hash树中的结点分为两类：一类包含一个项集列表(叶结点)，另一类包含一张hash表(内部结点)。在内部结点上，hash表中的每一个桶都指向另一个结点。假定hash树的根结点的深度等于1，则一个深度为d的内部结点指向深度为d1的结点。项集都存放在叶子结点，当需要添加一个项集c的时候，就从根结点出发直到叶子结点。在一个深度为d的内部结点，对该项集的第d项应用hash函数来确定下一步遍历的分支。所有的结点最
35、初都被创建为叶子结点。当一个叶子结点的项集数目超出某一个阈值时，该结点将会转化为一个内部结点。从根结点开始，子集函数按照如下的方式找出包含在交易t中的所有的候选集。如果在叶子结点，找出该叶子结点中所有包含在交易t中的项集，并且为它们添加一个指向结果集的索引；如果通过散列第i项到达某个内部结点，则散列交易t中第i项后的每一项，并且将这个过程递归地应用于相应的桶。对于根结点，则散列交易t中的每一项。子集函数能够返回所需要的候选集的索引，对于任何交易t中包含的项集c，c的第一个项一定出现在t中。在根结点，通过散列交易t中的每一项，我们能够确定只忽略那些不是从t中的某一项开始的项集。同样的结论也适用于
36、hash树中位于其他层次的结点。由于在每一个项集中的项都经过排序，如果我们通过散列项i到达当前的结点，则以后只需要考虑交易t中出现在项i后的项。AprioriApriori算法详述（续）算法详述（续）第36页/共146页38步骤：a.对于每个频繁项集l，找出l的所有非空子集；b.对于l的每个非空子集a，如果 support_count(l)/support_count(a)min_conf，则输出规则“a（la）”。频繁项集产生强关联规则频繁项集产生强关联规则第37页/共146页39例：假定数据包含频繁集l I1,I2,I5，L的非空子集有I1,I2,I1,I5,I2,I5,I1,I2,和I5
37、。可以由l产生的关联规则：I1I2I5，confidence 2/4 50%；I1I5I2，confidence 2/2 100%；I2I5I1，confidence 2/2 100%；I1I2I5，confidence 2/6 33%；I2I1I5，confidence 2/7 29%；I5I1I2,confidence 2/2 100%；若最小置信度阈值为70%，则只有I1I5I2，I2I5I1，I5I1I2可输出，是强关联规则第38页/共146页40不需要生成大量候选项集的频繁项集挖掘。算法采用分而治之的策略。频繁模式增长（频繁模式增长（FP-GrowthFP-Growth）算法）算法第
38、39页/共146页41例：最小支持度阈值为3交易编号交易编号所有购物项所有购物项（排序后的）频繁项（排序后的）频繁项100f,a,c,d,g,i,m,pf,c,a,m,p200a,b,c,f,l,m,of,c,a,b,m300b,f,h,j,of,b400b,c,k,s,pc,b,p500a,f,c,e,l,p,m,nf,c,a,m,pFP-GrowthFP-Growth算法例算法例第40页/共146页42nullb:1f:3c:1b:1p:1f:1c:1m:1p:1a:1a:2b:1m:1f:2c:2a:3f:4c:3m:2p:21.f,c,a,m,p2.f,c,a,b,m3.f,b4.c,
39、b,p5.f,c,a,m,pFP-GrowthFP-Growth算法例算法例第41页/共146页43生成的FP树FP-GrowthFP-Growth算法例算法例节点链性质对任意频繁项ai，顺着ai的节点链，从ai的头开始，可以找到包含ai的所有频繁模式。第42页/共146页44项项条件模式库条件模式库条件条件FP树树p(f:2,c:2,a:2,m:2),(c:1,b:1)(c:3)|pm(f:4,c:3,a:3,m:2),(f:4,c:3,a:3,b:1,m:1)(f:3,c:3,a:3)|mb(f:4,c:3,a:3,b:1),(f:4,b:1),(c:1,b:1)a(f:3,c:3)(f:
40、3,c:3)|ac(f:3)(f:3)|cf第43页/共146页45包含m的所有频繁模式的集合有：(m:3),(am:3),(cm:3),(fm:3),(cam:3),(fam:3),(fcam:3),(fcm:3)。这表明对一个单独路径的FP树进行挖掘时，可以通过输出该路径上所有项的组合来实现。FP-GrowthFP-Growth算法例算法例第44页/共146页46前缀路径性质为计算路径p上的一个节点ai的频繁模式，只需要计算p中ai的前缀子树，并且前缀子树中的每个节点的频繁数和节点ai相同。FP-GrowthFP-Growth算法详述算法详述第45页/共146页47引理单单路路径径FP树树
41、的的模模式式生生成成假假设设一一个个FP树树T，只只有有一一条条路路径径P，通通过过列列举举P的的子子路路径径的的所所有有组组合合，可可以以得得到到T的的频频繁繁模模式式全全集集，它它们们的的支支持持度度等等价价于于子子路路径径中中的的所所有有项项的的最最小小支支持持度。度。FP-GrowthFP-Growth算法详述算法详述第46页/共146页48算法2：在FP树中挖掘频繁模式输入：用DB根据算法1构造的FP树和最小支持度阈值；输出：所有的频繁模式的集合；方法：调用FP-Growth(FP-Tree,null)；ProcedureFP-Growth(Tree,)(1)if(Tree只包含单路
42、径P)then(2)对路径P中节点的每个组合（记为）(3)生成模式，支持数中所有节点的最小支持度第47页/共146页49(4)else对Tree头上的每个ai，do(5)生成模式=ai，支持度ai.support；(6)构造的条件模式库和的条件FP树Tree；(7)ifTree(8)thencallFP-Growth(Tree,)FP-GrowthFP-Growth算法详述算法详述第48页/共146页503 归结原理归结原理n n1、一阶谓词基础n n2、置换与合一n n3、子句集n n4、归结原理n n5、归结反演第49页/共146页51一阶谓词基础一阶谓词基础1 1、谓词：表示个体对象之间
43、的关系、属性或状态。、谓词：表示个体对象之间的关系、属性或状态。其表示形式如下：其表示形式如下：P(x1,x2,x3,.xn)P(x1,x2,x3,.xn)其中：其中：P P是谓词符号，表示是谓词符号，表示x1,x2,x3,.xnx1,x2,x3,.xn个体对象之间的属性、状态或关系。个体对象之间的属性、状态或关系。x1,x2,x3,.xnx1,x2,x3,.xn是谓词的参量（或称项），一般表示个体，它可以是个体是谓词的参量（或称项），一般表示个体，它可以是个体常量、个体变量或是个体函数。个体变元的变化范围称为个体域常量、个体变量或是个体函数。个体变元的变化范围称为个体域（或（或论域论域论域论
44、域）例：例：P(x):P(x):表示表示x x是素数是素数 FRIEND(a,b)FRIEND(a,b)：表示：表示a a和和b b是朋友是朋友第50页/共146页52一阶谓词基础一阶谓词基础2 2、个体函数：表示项之间的关系、个体函数：表示项之间的关系 有了个体函数之后，谓词的表达能力更强。假如个体函数有了个体函数之后，谓词的表达能力更强。假如个体函数father(b)father(b)表表示示“个体个体b b的父亲的父亲”，则谓词，则谓词FRIEND(a,father(b)FRIEND(a,father(b)表示表示“a a和和b b的父亲的父亲是朋友是朋友”，显然表达能力更强了。，显然表
45、达能力更强了。约定：（约定：（1 1）谓词符号用大写字母表示，如）谓词符号用大写字母表示，如P P，QQ，R R，S S等；（等；（2 2）用）用小写字母小写字母x,y,zx,y,z等作为个体变元符号；（等作为个体变元符号；（3 3）用小写字母）用小写字母a,b,ca,b,c等作为个等作为个体常元符号；（体常元符号；（4 4）用小写字母）用小写字母f,g,hf,g,h表示个体函数符号。表示个体函数符号。第51页/共146页53一阶谓词基础一阶谓词基础3 3、量词、量词 全称量词：全称量词：“所有所有”,“,“一切一切”,“,“任一任一”,“,“全体全体”,“,“凡是凡是”等词称为全称量词，记为
46、等词称为全称量词，记为存在量词：存在量词：“存在存在”、“有些有些”、“至少有一个至少有一个”、“有的有的”等词统称为存在量词，记为等词统称为存在量词，记为引入量词和连接符（引入量词和连接符（蕴涵，蕴涵，合取，合取，析取，否析取，否定词定词）之后，谓词的表达能力大大扩充了。）之后，谓词的表达能力大大扩充了。第52页/共146页54一阶谓词基础一阶谓词基础4 4、谓词公式：用谓词、量词（存在量词，全称量词）、谓词公式：用谓词、量词（存在量词，全称量词）、联接词（、联接词（蕴涵，蕴涵，合取，合取，析取）连接而成析取）连接而成的复杂的符号表达式称为谓词公式。的复杂的符号表达式称为谓词公式。例子：知识
47、例子：知识“不存在最大的整数不存在最大的整数”的表示的表示 设：谓词设：谓词G(x):G(x):表示表示x x是整数，是整数，D(x,y)D(x,y)表示表示x x大于大于y y。则表示如下：则表示如下：第53页/共146页55命题逻辑的归结命题逻辑的归结1 1、基本概念、基本概念命题：不带参数命题：不带参数(肯定也不含量词肯定也不含量词)的谓词。的谓词。命题公式：由连接词命题公式：由连接词(蕴涵，蕴涵，合取，合取，析取，等析取，等 价价，否定词，否定词)将命题连接在一起构成将命题连接在一起构成 永真式：真值为永真式：真值为T T的命题公式称为永真式或重的命题公式称为永真式或重 言式或有效的。
48、言式或有效的。永假式：真值为永假式：真值为F F的命题公式称为永假式或不的命题公式称为永假式或不 可满足的。可满足的。非永真式：不是永真式的命题公式；非永真式：不是永真式的命题公式；可满足式：不是永假公式的命题公式；可满足式：不是永假公式的命题公式；第54页/共146页56命题逻辑的归结命题逻辑的归结原子公式：不含任何连接词的命题公式称为 原子公式或称原子.例如P,Q文字：原子公式及其否定形式称为文字.例如P,L子句：文字的析取称为子句.例如:PRQ互补文字：设L为一个文字，则称L与L为互 补文字。第55页/共146页57等价关系等价关系AA双重否定AAA等幂律AAAABBA交换律ABBA(A
49、B)CA(BC)结合律(AB)CA(BC)A(BC)(AB)(AC)分配律A(BC)(AB)(AC)A(AB)A吸收律A(AB)A(AB)AB摩根定律(AB)ABABAB蕴含表达式第56页/共146页58等价关系等价关系AB(AB)(BA)等价表达式ATAAFFATTAFAAAF矛盾律AAT排中律A(BC)ABC输出律(AB)(AB)A归谬律ABBA逆反律第57页/共146页59命题逻辑的归结命题逻辑的归结 n n命题逻辑中的归结推理方法n n若命题逻辑描述的命题A1,A2,.An和B,要证明在A1A2.An成立的条件下有B成立，或说A1A2.AnB。很显然A1A2.AnB等价于证明A1A2.
50、AnB是矛盾(永假)式。归结推理的方法就是从A1A2.AnB出发使用归结推理规则来寻找矛盾，从而证明A1A2.AnB的成立。第58页/共146页60命题逻辑的归结命题逻辑的归结1、归结式设有两个子句C1=LC1C2=LC2 从中消去互补对，所得新子句C12=C1C2，则称这一过程为归结。称C12为子句C1和C2的归结式，称C1和C2为C12的亲本子句。第59页/共146页61命题逻辑的归结命题逻辑的归结第60页/共146页62命题逻辑的归结命题逻辑的归结n n命题逻辑的归结推理过程命题逻辑的归结推理过程n n(1)(1)利用利用逻辑蕴含式和逻辑等价式逻辑蕴含式和逻辑等价式将命题公式化成将命题公