资源描述：
《数据库中关系规则的数据挖掘》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第25卷第5期鞍山钢铁学院学报Vol.25No.52002年10月JournalofAnshanInstituteofI.&S.TechnologyOct.,2002数据库中关系规则的数据挖掘刘 悦,李桂丽(鞍山科技大学计算机科学与工程学院,辽宁鞍山 114044)摘 要:关联规则算法是数据挖掘中的核心技术,本文给出了数据库中挖掘关系规则的一种新算法,该算法通过二次扫描,第一次将可能出现的频繁项目集加入到ISC中,第二次扫描采用逐步求精算法将频繁项目集加到项目集中,减少了数据库的扫描次数.关键词:数据
2、挖掘;关联规则;知识发现中图分类号:TP311 文献标识码:A文章编号:1000O1654(2002)05O0369O03 大量数据的产生和收集导致了信息爆炸.面对信息的海洋,如何有效地组织和利用这些资源成为信息时代的重要课题.KDD(KnowledgeDiscoveryinDatabases)自动地从大量的信息中发现有用的知识,是有效利用信息的新方法.其中,相联规则的提取是KDD近期研究的一个重要课题.在实际的大型数据库(如超级市场的事务数据库)中,发现如“购买物品A和B的客户87%同时也购买C和
3、D”这样的规则.随着数据库技术的广泛应用,各行各业都积累了大量的数据,这些数据的内在联系可能就是有价值的知识,运用数据挖掘技术,发现并提取这些知识,对于分类设计、商店布局、隶属邮寄、市场分析等方面有很大作用.数据挖掘(DataMining)就是从大量的数据中提取隐含的、未知的、对决策有潜在价值的知识和规则的过程.数据挖掘的主要技术包括:聚类、粗糙集、关联规则、统计分析、神经网络、模糊数学等.1 涉及的概念111 关联规则的定义 设I={i1,i2,⋯,im}是由m个不同的项目组成的集合(称I为项集)
4、.给定一个数据库D,其中的每一个记录T是I中一组属性的集合,即TAI,T有一个唯一的标识符TID.若集合XAI且XAT,则记录T包含集合X.一条关联规则就是形如X]Y的蕴涵式,其中XAI,YAI,X∩Y=Φ.关联规则成立的条件是:(1)具有支持度S,即在数据库D中至少有S的记录包含X∪Y;(2)具有置信度C,即在数据库D中包含X的记录至少有C的同时也包含Y.习惯上将关联则表示为X]Y(S,C)X∪Y支持度S=×100%(1)DX∪Y置信度C=×100%(2)X其中支持度定义了项目在整个数据库中所占的比
5、例;置信度定义了发现规则的强度.关联规则挖掘就是找出数据库D中所有满足用户给定支持度S和可信度C的所有X]Y.112 项目集 项目集是I的一个子集,若Itemset出现在某个交易中,则称此T支持此Itemset.113 频繁项目集(Frequ-Itemset)是指满足用户给定支持度的Itemset.数据挖掘中重点就是找出频繁项目集.各种数收稿日期:2002-06-27.作者简介:刘悦(1970-),女,辽宁鞍山人,讲师;李桂丽(1968-),女,山东牟平人,副教授.©1995-2005Tsinghu
6、aTongfangOpticalDiscCo.,Ltd.Allrightsreserved.· 鞍山钢铁学院学报 第370·25卷据挖掘算法的研究都是为了尽可能地减少数据库的扫描次数来找出所有的频繁项目集.114 项目集集合ISC(ItemSetCollect)项目集中的每一个元素(Node)可以表示为如下结构:Node(ItemsetFirstvalueCountMax),其中Itemset用于表示项目集,在项目集中不允许有两个相同的元素存在.Fi
7、rstvalue用于表示将Itemset第一次加入项目集时的正在处理的交易序号.Count(Itemset)用于表示Itemset加入项目集时支持此项目交易的数量.Max用于表示Itemset加入项目集前支持此项目的交易的最大可能交易数量. 用这四个属性可以推算出相应的项目集的最大可能支持度和最小可能支持度Smax-pro和Smin-pro,其中Smax-pro=(max+count)/id;Smin-pro=count/id(id用于表示当前正在处理的交易序号).在四个属性中max是数据挖掘算法中
8、关键.2 算法描述 本文提出的算法第一次扫描将可能出现的频繁项目集加入到ISC中,第二次扫描,Freq-Itemset均被添加到项目集集合中. 第一次扫描算法:扫描前ISC的内容为空,算法依次读取数据库中的每一个交易.每个交易用项目集T来表示,用I表示当前交易序号.在读取每一个交易时将进行加入新结点、计数及修剪等3种操作. 现就加入一个新结点t时确定max的算法加以阐述:对于T的每一个子集t,若t不在ISC中则将t加入到ISC中;如果t的所有子集t
