基于归纳逻辑程序设计的特异规则挖掘.pdf

第29卷第4期 北京工业大学学报 Vol29N04 2003年12月 JoURNALOFBEUINGUNⅣERSlTYoF Dec TECHNOLolW 2003 基于归纳逻辑程序设计的特异规则挖掘 黄明新，刘椿年 (北京工业大学计算机学院多媒体与智能软件技术北京市重点实验室，北京100022) 摘要：从关系数据挖掘的角度提出了挖掘特异规则的方法，该方法通过面向属性的方法来识别特异数据．借 鉴clli2箅法的思想实现了特异数据的离散，并定性地描述了数据的特异程度，结台经典的归纳逻辑程序设计系 统FoIL自然地挖掘出了特异规则，突破了传统命题级数据挖掘的框架．‘试验结果表明利用该，f法能够发现被 传统的关联规则挖掘算法所忽略的有价值的知识 关键词：归纳逻辑程序设计；关系数据挖掘；特异规则 中围分类号：TP39 文献标识码：B 文章编号：0254一0037(2003)03—0495一05 discoverfrom 关联规则…是知识发现(knowledge 低支持度的项集在传统的关联规则挖掘中通常被忽略，而在这些被忽略的项集间蕴藏着有价值的知识． 述的特异情形，并且不同于数据集中的其他对象的数据称为特异数据，挖掘特异规则则是发现蕴藏在特异 数据中且被传统的关联规则挖掘算法所忽略的有价值的知识．传统的数据挖掘算法只能处理单表中的数 据，而在现实数据库系统中，特异数据则是分布在多个表中，如果进行多表合一的预处理，将存在许多潜在 的问题¨1．将归纳逻辑程序设计(induc廿ve109ic 据挖掘(rel撕0nal 的模式，并且能运用逻辑程序表达有用的背景知识，同时还能运用强有力的逻辑语言来描述发现的模 式…，克服了命题逻辑表示模式弱表达能力的缺陷，其中FOIL【“是最具有代表性的ILP系统之一．作者 从关系数据挖掘的角度，结合经典的归纳逻辑程序设计系统FoIL来挖掘特异规则． 1 特异数据和特异规则 特异数据代表了相对较少对象所描述的特异情形，并且不同于数据集中的其他对象，是数据集的一个 特异性． 设4．是数据库中某表的一个属性(列)。Z={五，五．，…，置．)表示爿．的属性值集合，共有n个不同的 』一r———————————一 值．数据‘，的特异性通过F(x，，)来衡量·F(％)=∑√Ⅳ(x。，，x。，)．式中，如果属性爿，是数值属性且无 女=1 背景知识可用，则Ⅳ(矗，％)=I‘，一气小如果属性爿，是符号属性，Jv(西，吒，)表示‘，与≮，之间由背景知识 给出的概念距离(concepnlaldistaflce)，如无背景知识可用，则．Ⅳ(‘．，t．)=1． 在评价x中每个数据的PF的值后，通过设置该属性的特异阈值，就可得到该属性的特异数据．阈值的 异数据，将属性值中有特异数据的属性称为特异属性．文献[6】详述了特异规则与普通关联规则的区别． 收稿日期：2002一11—28． 基金项目：国家自然科学基金资助项目；北京市自然科学基金资助项目(4022003)， 作者简介：黄明新(1977一)，男，湖北钟样人，硕士生；刘椿年(19“)，男，江苏连云港人，教授，博士生导师 万方数据 北京工业大学学报 2003年 2 FoIL简介 FoIL的问题陈述如下． 已知：目标谓词p；正例集合矿和负例集合E一(p的基原子所构成的两个集合)；背景知识占(Pmlog 基原子有限)． 寻找：假设汀(p的定义子句)，使得H对E+和E一都正确，即 1)u日对E+完备(即对于所有P∈矿，Hu曰蕴涵P)，也称Hu占覆盖所有正例． 2)u B对E一一致(即不存