数据稀疏情况下的关联规则扩展与应用

在网络学习平台中,如何有效推荐学习资源具有重要意义。为进一步提高在数据稀疏情况下的关联规则推荐效率,从相似性角度出发,引入学习资源文本信息,通过构建学习资源相似度矩阵,提出一个基于资源相似度的关联规则扩展方法,从而在历史数据稀疏的情况下生成关联规则推荐。实践结果表明,基于同一数据对象进行研究,通过扩展关联规则方法可以提高推荐的有效性和实用性。

用户交易数据不足情况下的商品关联规则扩展与应用

在电子商务环境下,如何有效地对商品进行推荐具有重要意义。然而传统的关联规则推荐算法往往需要大量的用户交易数据作为支撑,对交易数据不足的商品,比如刚上架不久的新品却无法生成关联规则。从相似性的角度出发,引入商品文本信息,以关联规则推荐算法中经典的Apriori算法为基础,通过构建商品间相似度矩阵,提出一个基于商品相似度的关联规则扩展方法,从而实现对用户交易数据不足的商品生成可靠的关联规则推荐。最后以淘宝平台上的真实数据为例,验证该方法的有效性和实用性。

基于多维关联规则的本体规则扩展方法

目前扩充和丰富本体存在很大的局限性.对此,文中提出采用多维关联规则技术扩展本体规则方法.通过对本体规则提取,在本体指导下的一致性处理,规则映射的建立,以及对概念本体的重新识别和更新等技术和方法充实和扩展概念本体.茶病虫害预测本体的实验结果表明该方法易于实现且具有较高的可行性和有效性.

基于扩展规则的模型计数与智能规划方法

提出命题扩展规则方法ER的一种高效实现.在此基础上,研究了扩展规则方法在3个领域的应用:提出一次性求解一系列相近SAT问题的快速算法nER;提出基于扩展规则的模型计数算法#ER,同时结合#ER和#DPLL的优点提出算法#CDE;设计基于扩展规则方法的Conformant规划系统.实验结果表明:使用nER算法一次性求解的时间远小于使用ER方法单独求解每个问题的总时间;对于互补因子较高的问题,#ER优于#DPLL;#CDE融合了#ER和#DPLL的优点.研究表明扩展规则方法对于互补因子较高的问题具有较大的优势,具有广阔的应用前景.

基于超扩展规则的动态在线推理算法

为了提高扩展规则的扩展性能,提出了超扩展规则,并证明了其与扩展负超归结之间的关联关系。KCER算法中使用扩展规则扩展子句,利用超扩展规则替换扩展规则能够更清晰地展示扩展过程,因此提出了基于超扩展规则的动态在线推理算法IKCCER。IKCCER采用离线编译和在线推理过程交互执行的方式,在保持推理效率不变的同时,其空间复杂性为KCCER算法空间复杂性的2/(n+1),其中n为输入子句集的子句数。

一种基于扩展规则的#SAT求解系统

#SAT问题是SAT问题的扩展,需要计算出给定命题公式集合的模型个数.通过将问题求解沿着归结的反方向进行,并利用容斥原理解决由此带来的空间复杂性问题,提出了一种基于扩展规则的模型计数和加权模型计数问题求解框架,可以看作是目前所有模型计数问题求解方法的一种补方法.证明了该方法的完备性和有效性,设计了基于扩展规则的#SAT求解系统:JLU-ERWMC.实验结果表明,JLU-ERWMC在有些问题中优于目前最为高效的#SAT问题求解系统.

一种新的基于扩展规则的定理证明算法

基于扩展规则的定理证明方法是一种与归结方法互补的新的定理证明方法.首先通过对扩展规则的深入研究,给出了扩展规则的一个重要性质,设计并实现了该性质的判定算法.此外,从理论上分析及证明了该判定算法的时间和空间复杂性.基于此,提出了一种新的基于扩展规则的定理证明算法NER,将判定子句集可满足性问题转化为一系列文字集合的包含问题,而非计数问题.实验结果表明,算法NER的执行效率较原有扩展规则算法IER和基于归结的有向归结算法DR有明显提高,有些问题可以提高两个数量级.

基于超扩展规则的知识编译方法

超扩展规则是对扩展规则的扩充,基于超扩展规则能够求得任意两个非互补且不相互蕴含的子句所能扩展出极大项集的交集与差集,并将所得结果以EPCCL理论的形式保存.该文首次提出了扩展反驳方法,是一种新型推理方法,并在该推理方法与知识编译之间建立了联系.基于超扩展规则的性质,该文还提出了两种知识编译算法:求并知识编译算法UKCHER和求差知识编译算法DKCHER,是两种新的知识编译算法.算法UKCHER是目前为止唯一一个可并行的EPCCL理论编译算法,算法DKCHER对于相变点附近的难解问题具有较高的编译效率和编译质量.实验结果表明:UKCHER算法的编译效率和编译质量均优于Lin等人提出的KCER算法;当子句数和变量数的比值较大时,DKCHER算法的编译效率和编译质量是最优的,相比于现有EPCCL理论编译算法,该算法具有较强的竞争力.

基于IMOM和IBOHM启发式策略的扩展规则算法

基于扩展规则的方法是一种定理证明方法.在IER(improved extension rule)扩展规则算法的基础上,提出了IMOM(improved maximum occurrences on clauses of maximumsize)和IBOHM(improved BOHM)启发式策略,并将两种启发式策略用于IER算法中,有指导性地选择限定搜索空间的子句,设计并实现了算法IMOMH_IER和IBOHMH_IER.实验结果表明,由于这两种启发式策略能够选择较为合适的搜索空间,可以尽快地判定出原问题是否可满足,故其速度平均能够达到原有算法DR(directional resolution)和IER的10～200倍.

基于MCN和MO启发式策略的扩展规则知识编译方法

在基于扩展规则的知识编译算法的基础上提出了2种启发式策略:MCN策略和MO策略.MCN策略和MO策略利用子句集的信息分别选择相应子句和变量,减少扩展规则的使用次数,进而降低知识编译后目标子句集的规模.在此基础上,设计并实现了MCN_KCER,MO_KCER和MCN_MO_KCER算法.实验结果表明:2种启发式策略都可以大幅度减小编译后的子句集规模,同时使用它们的效果更为明显,经过编译后得到的子句集规模是原算法的1/3～1/39,从而大幅度提高之后的在线推理阶段的效率.

可能性扩展规则的推理和知识编译

在扩展规则的基础上提出了可能性扩展规则.给出了基于可能性扩展规则的可能性逻辑推理方法,利用互补因子的概念来估价推理问题的复杂度.扩展了经典逻辑的蕴含可控制类和可满足可控制类的定义,提出了可能性蕴含可控制类、不一致性程度计算可控制类的概念.在可能性扩展规则的基础上提出了EPPCCCL(each pair of possibilistic clauses contains complementary literals)理论,并证明了该理论是在最优化形式蕴含可控制类和不一致性程度计算可控制类中的,可以作为可能性知识编译的目标语言.

描述元数据结构及其扩展规则研究

设计描述元数据的首要关键点是元数据的结构及其扩展规则 ,本文就此问题进行探讨 ,并以古文献元数据为例说明描述元数据规范的基本结构、元素组成和扩展规则 ,以此增强不同资源对象元数据之间的互操作性 ,进一步实现资源共享的目的。

基于半扩展规则的定理证明方法

自动定理证明一直是人工智能领域中最重要的问题之一,基于归结的方法是通过推出空子句的方法来判定子句集的可满足性.基于扩展规则的定理证明方法在一定意义上是和归结原理对偶的方法,是通过子句集能否推导出所有极大项组成的子句集来判定可满足性.通过对扩展规则的研究给出了半扩展规则的概念,并提出了基于半扩展规则的定理证明算法SER.然后分析及证明了该算法的正确性、完备性和复杂性.实验结果表明,算法SER的执行效率较基于归结的有向归结算法DR和基于扩展规则算法IER,NER有明显的提高.

结合互补度的基于扩展规则#SAT问题求解方法

#SAT问题又称模型计数(model counting)问题是人工智能领域的研究热点之一,在人工智能领域被广泛应用.在对基于扩展规则的#SAT问题求解方法 CER(counting models using extension rules)深入研究的基础上,提出一种结合互补度的#SAT问题求解方法.在计算给定子句集的模型个数时,利用SE-Tree(set enumeration tree)形式化地表达计算过程,逐步生成需要计算的子句集合,并在SE-Tree中添加终止结点,避免大部分含互补文字子句集合的生成,且不会因剪枝而导致求解不完备.提出互补度的概念,在扩展SE-Tree结点时按照互补度由大到小的顺序扩展,较早地生成含互补文字且长度较小的子句集合,有效减少枚举树生成的结点个数,进而减少对子句集合判断是否含互补文字的计算次数.实验结果表明:与CER方法相比该方法效率较好,且进一步改进了CER方法在互补因子较低时求解效率低下的不足.

扩展规则方法研究综述

归结方法是自动推理的重要方法之一,而扩展规则是与归结对称的方法,近年来引起了研究者的广泛关注。从扩展规则的相关概念、在命题逻辑中的发展以及在一阶逻辑、描述逻辑、模态逻辑、可能性逻辑和多值逻辑中的应用3个方面论述分析了扩展规则10年来的研究现状,重点阐述扩展规则用于求解SAT、相近SAT和#SAT问题各种算法的优缺点,最后指出相关的研究热点与发展趋势。

基于扩展规则的启发式#SAT求解算法

#SAT在人工智能领域取得了广泛应用,很多现实问题可以规约成#SAT进行求解,得到命题理论的模型个数.通过对基于扩展规则的#SAT求解器的深入研究,发现选择规约子句的顺序对极大项空间的大小有着较大的影响,因此提出两种加速#SAT求解的启发式策略:MW和LC&MW.MW每次选择具有最大权值的子句作为规约子句;LC&MW每次选择最长子句作为规约子句,若最长子句存在多个,则在多个最长子句中选择具有最大权值的子句作为规约子句.利用MW策略设计了算法CER_MW,利用LC&MW策略设计了算法CER_LC&MW.实验结果表明,CER_MW和CER_LC&MW相对于先前的#SAT求解算法在求解效率和求解能力上都有显著的提高.在求解效率方面,CER_MW和CER_LC&MW的求解速度是其他算法的1.4倍~100倍.在求解能力方面,CER_MW和CER_LC&MW在限定时间内可解的测试用例更多.

两种新的基于扩展规则#SAT问题求解算法

提出一种新的基于扩展规则的#SAT求解算法NCER,该算法在#ER的基础上加入启发式策略.该策略每次选择当前子句集的最长子句来减小极大项空间,使得递归调用的次数减少,从而加快求解效率.为解决基于扩展规则的#SAT求解器在互补因子较小的样例上的不良表现,结合NCER和CDP的优点提出混合#SAT求解算法NCDPER.实验结果表明:NCER较先前的#ER在所有85个随机SAT测试用例上有了显著的提高.通过与目前最好的基于扩展规则的#SAT求解器的比较,该求解器具有更好的性能.

半扩展规则下分解的定理证明方法

基于扩展规则的定理证明方法在一定意义上是与归结原理对偶的方法,通过子句集能否推导出所有极大项来判定可满足性.IER(improved extension rule)算法是不完备的算法,在判定子句集子空间不可满足时,并不能判定子句集的满足性,算法还需重新调用ER(extension rule)算法,降低了算法的求解效率.通过对子句集的极大项空间的研究,给出了子句集的极大项空间分解后子空间的求解方法.通过对扩展规则的研究,给出了极大项部分空间可满足性判定方法 PSER(partial semi-extension rule).在IER算法判定子空间不可满足时,可以调用PSER算法判定子空间对应的补空间的可满足性,从而得到子句集的可满足性,避免了不能判定极大项子空间可满足性时需重新调用ER算法的缺点,使得IER算法更完备.在此基础上,还提出DPSER(degree partial semi-extension rule)定理证明方法.实验结果表明:所提出的DPSER和IPSER的执行效率较基于归结的有向归结算法DR、IER及NER算法有明显的提高.

扩展型关联规则和原关联规则及其若干性质

已有的关联规则模型所反映的基本上是频繁事件中所隐藏的一种积极或肯定关系 ,而没有反应其隐含的否定关系 ,在实际应用中 ,这种否定关系与肯定关系一样也是很重要的 ,在此论述的扩展型关联规则模型就能反映上述两种关系 ,据此可以得到更多的规则知识 ;此外 ,由于 Apriori关联规则生成方法产生的关联规则具有较大的冗余性 ,论述的原关联规则可以消除关联规则的这种冗余特性 ,挖掘原关联规则既能大大减少关联规则的数目 ,又能节省规则生成时间 ;把扩展型关联规则和原关联规则相结合 ,可使得对扩展关联规则的挖掘更加有效 .

基于BK树的扩展置信规则库结构优化框架

针对扩展置信规则库(extended belief rule base,EBRB)系统在规则数较多时推理效率不理想的问题,引入BK树数据结构,提出了一种基于BK树的结构优化框架。首先根据置信规则在度量空间中彼此的距离建立EBRB的树形索引结构,然后通过设置阈值减少EBRB系统推理时搜索规则的数量,并激活关键规则,最终达到提高EBRB系统推理效率的目的。以非线性函数拟合、输油管道泄露仿真实验及分类数据集的对比实验,验证结构优化框架在EBRB系统中的有效性,实验结果表明,所提框架能够优化EBRB系统推理效率并提高决策准确性。