计算机职称论文：粗集数据挖掘之MIE-RS实施

数据挖掘一般是指从大量的数据中通过算法搜索隐藏于其中信息的过程。数据挖掘通常与计算机科学有关，并通过统计、在线分析处理、情报检索、机器学习、专家系统(依靠过去的经验法则)和模式识别等诸多方法来实现上述目标。以下是小编今天为大家精心准备的计算机职称相关论文：粗集数据挖掘之MIE-RS实施。内容仅供阅读与参考!

粗集数据挖掘之MIE-RS实施全文如下：

1、方法原理

1.1 粗集基本理论

信息系统定义为,其中U是有限的例子集合.C是条件属性集合,D是决策属性集合,V是C和D的值域.函数f:U(C∪D→V,定义每个例子的属性值.定义属性集R C∪D上的等价关系为:R～={(xi,xj)∈U×U: a∈R,f(xi,a)=f(xj,a)}.R~的等价类的集合记作R*,它是U上的一个划分.设Y U,Y关于R的下近似集合RY定义为:RY=∪{E∈R*: E Y}.即下近似集合包含所有根据R的信息能准确划分到Y的例子.定义集合X关于集合Y的分类正确程度c(X,Y)为:c(X,Y)= X∩Y / X .其中 表示集合中元素的个数.给定分类正确标准α,Y U ,根据粗集扩展模型,定义Y关于R的α-下近似RαY为:RαY=∪{E∈R*: c(E,Y) α},即Y的α-下近似包含所有能以不小于α的正确率划分到Y中的等价类集合.

1.2 MIE-RS的理论基础

令Yk U表示U中某一决策类(概念),k表示其决策类别是第k类.定义1:决策类Yk U的核定义为:Core〔k〕={a: CYk ≠ C-{a}Yk },即核Core〔k〕中属性对决策类Yk而言是不可缺少的,否则会导致Yk中某些原可正确分类的例子现在不能被正确分类.定义2:属性集P C是决策类Yk的一个覆盖,当且仅当 PYk = CYk ,并且对 P’ P, P’Yk ( CYk .这说明若P是决策类Yk的一个覆盖,则P具有与C同样的区分决策类Yk的能力.因此可用P代替C来产生Yk的分类规则,这时规则的条件部分具有最小描述长度.按如下原则生成决策类Yk的分类规则:令E表示P*中的等价类,Des(E)表示对等价类E的描述,即等价类E对应的各条件属性的特定取值;Des(Yk)表示对决策类Yk的描述,即第k类对应的各决策属性的特定取值.则对每个E∈PYk建立如下的决策规则:r: Des(E)→Des(Yk)对于不一致例子集,给定分类正确标准α,令CαYk中的每个例子的决策类别都是第k类,即把CαYk中那些原来决策类别不是第k类的例子改为第k类,形成新的该决策类(第k类)的集合Y’k Yk,此时CαYk=CY’k(.再按上述方法求Y’k的覆盖P,对每个E∈PY’k建立如下的决策规则:r’: Des(E)→Des(Yk)定理1:规则r’的可信度大于等于α.证明: E∈P Y’k,因为P Y’k=C Y’k,P C,所以PY’k中的等价类E是C Y’k中的一个或多个等价类Ei的并集,记作,E=YiEi,Ei∈C Y’k.又因为CαYk=CαY’k,即Ei∈CαYk,则有: Ei∩Yk ≥α Ei (1) 规则r’的可信度:cf= E∩Yk / E = (YiEi)∩Yk / YiEi = YiEiI Yk / YiEi =∑i Ei∩Yk /∑i Ei 由(1)式,cf ∑iα Ei /∑i Ei =α.得证.

2、MIE-RS的设计与实现

2.1 算法设计

MIE-RS算法:输入:非一致的例子集U,分类正确标准α.输出:满足α的简化的分类规则集.(1)用户选择待挖掘的条件属性集C和决策属性集D.(2)计算U关于C和D的等价类C*和D*.对U中每个决策类Yk∈D*,修改使CαYk中的每个例子的决策类别都是第k类.经此操作后有些决策类集合Yk发生了改变.(3)计算每个决策类Yk的核属性集Core〔k〕.(3.1)计算每个决策类Yk关于条件属性集C的下近似集合CYk中的元素个数LANum(C,k);(3.2) Core〔k〕= ;(3.3) for each a∈C do{计算每个决策类Yk关于C-{a}的下近似集合中的元素个数LANum(C-{a},k);if (LANum(C-{a},k)! =LANum(C,k)) Core〔k〕=Core〔k〕+{a};}(4)对每个决策类Yk,计算Yk的覆盖,生成Yk的分类规则.(4.1) for each Ykdo {(4.2)用户选择感兴趣的属性集合Interest;(4.3) Candidates =C-Core〔k〕-Interest;(4.4) P =Core〔k〕+Interest;(4.5)计算LANum(P,k);(4.6)while(LANum(P,k)! =LANum(C,k)){ for each a∈Candidates do 计算LANum(P+{a},k); 选取属性b,使LANum(P+{b},k)值最大; P=P+{b}; Candidates=Candidates-{b};}(4.7) for each a∈P do if(a不在Core〔k〕+Interest中) { P=P-{a}; 计算LANum(P,k); if (LANum(P,k)! =LANum(C,k)) P=P+{a}; }(4.8) for each E∈PYkdo 生成Yk的决策规则;}

2.2 用Hash表实现算法

在上述算法中,求等价类(进而求下近似集合)是个最基本的操作,提高该操作的效率是个关键问题.容易看出,直接求某属性集的等价类的时间复杂度为O(n2).若采用本文的Hash表方法求等价类,可将时间复杂度降为O(n).另外,本文提出的方法,不需要具体求出各个等价类集合,而是直接求出各个下近似集合中的元素个数,从而避免了频繁进行集合的交运算,提高了效率.首先对例子集U进行预处理.设用户选择了条件属性集C和决策属性集D.将用户选择的每个属性j的各值转换为从0开始的整数,生成转换表T.属性j的不同值的个数cnt〔j〕等于转换后该属性具有的最大整数值加1.j=1,2,..., C + D .如3.4节例子所示.任给条件属性集C和决策属性集D,建立并初始化Hash表E及EandY.E的大小为cnt〔1〕*cnt〔2〕*...*cnt〔 C 〕.EandY大小为cnt〔1〕*cnt〔2〕*...*cnt〔 C 〕*cnt〔 C +1〕*...*cnt〔 C + D 〕.Hash表中的每个存储单元初始化为0.对表T中每个记录r,用a(i)表示记录r第i个属性的值,构造如下两个Hash函数:H1(r)=(((a(1)*cnt〔1〕+a(2))*cnt〔2〕+a(3))*cnt〔3〕+...)*cnt〔 C -1〕+a( C )H2(r)=(( H1(r)*cnt〔 C 〕+a( C +1))*cnt〔 C +1〕+...)*cnt〔 C + D -1〕+a( C + D )

利用Hash表,我们采用如下方法求每个决策类Yk关于某属性集C的下近似集合CYk中的元素个数LANum(C,k).(1)扫描一遍转换表T,对每个记录r,按照计算出的Hash地址H1(r)和H2(r),把相应的两个存储单元的值各加上1.扫描完成后,T关于属性集C的任一等价类(设记录r为其任一代表元)中元素的个数就存放在Hash表E的相应位置(H1(r))中;同理,表T关于属性集C∪D的任一等价类(设记录r为其任一代表元)中元素的个数就存放在Hash表EandY的相应位置(H2(r))中.(2)再一次扫描表T,对每个记录r,设其类别为第k类,计算Hash地址H1(r)和H2(r),取出相应存储单元的值进行比较,若E〔H1(r)〕=EandY〔H2(r)〕,说明记录r属于CYk,则LANum(C,k)=www.51lunwen.com/database/ LANum(C,k)+1.容易看出,计算LANum(C,k)只需扫描表T两遍,设 T =n,则时间复杂度为O(n).

2.3算法分析

令 U =n , C + D =m1+m2=m,决策类别个数为d.对MIE-RS算法采用Hash方法实现,各步骤的时间复杂性分析如下:首先,对每个属性进行预处理所需时间为O(m*n(n-1)/2)=O(mn2).其中n(n-1)/2=0+1+...+(n-1)为查找比较次数.步骤(2)是对不一致例子的处理过程.有了Hash表E和EandY,对表中每条记录r,设其属于第k类,若EandY〔H2(r)〕≠E〔H1(r)〕且EandY〔H2(r)〕/E〔H1(r)〕≥α,则记录r所在的关于C的等价类〔r〕C∈CαYk,根据2.2节,对表中任一记录r’,若H1(r’)=H1(r),但EandY〔H2(r’)〕/E〔H1(r’)〕<α,则在表T中将记录r’的决策类别改为第k类.此步骤在最坏情况下的时间复杂度不超过O(n2).对步骤(3),由3.2节的分析可知,(3.1)的复杂度为O(n),(3.3)的复杂度为O(m1n)

3、结语

对于基于粗集的数据挖掘算法,目前也有一些研究〔3,4〕.本文提出了一个新的从不一致例子中挖掘规则的粗集方法MIE-RS.MIE-RS的特点在于:一是有效地统一处理了一致和不一致的例子,生成满足给定可信度的可能性规则;二是将求所有例子的覆盖化为求各个决策类的覆盖,使挖掘出的规则更简单;三是巧妙构造了Hash函数来实现算法,大大降低了算法的时间复杂度.我们在自行研制开发的数据挖掘服务器中实现了MIE-RS,并用多个实际数据集进行了测试,效果良好,挖掘出来的规则简单、实用.

参考文献：

1 Z. Pawlak. Rough sets. Int. J〔J〕.Computer and InformationScience, 1982,Vol 11,No5,341～356.

2 W. Ziarko. Variable precision rough set model〔J〕. Journal ofComputer and System Sciences. 1993.46,39～59.

3 Chien-Chung Chan, Jerzy W. www.51lunwen.com/database/ Grzymala-Busse. On the lowerboundaries in learning rules from examples〔A〕. In IncompleteInformation. Rough Set Analysis ,Chapter 2, 1998, 58～74.

4 Xiaohua Hu. Knowledge discovery in databases: an attribute-oriented rough set approach〔D〕. Ph. D Thesis, in ComputerScience, University of Regina, Canada. June,1995.