基本信息
- 项目名称：
- 一种基于集合运算的分类规则处理方法
- 来源：
- 第十二届“挑战杯”省赛作品
- 小类：
- 信息技术
- 大类：
- 自然科学类学术论文
- 简介：
- 分类规则是数据挖掘主要任务之一，消除分类规则集中的冗余规则，提高分类效率是一项重要的研究内容。本文通过分析分类规则与训练集之间的映射关系，采用集合的相关运算寻找特征规则及相应特征集，从而消除分类规则集中存在的冗余，并在此基础上提出了基于集合运算的分类规则处理算法（PASO）。最后，以恒星光谱数据为背景，实验验证了该方法的正确性和可行性。
- 详细介绍：
- 一种基于集合运算的分类规则处理方法 摘要 分类规则是数据挖掘主要任务之一，消除分类规则集中的冗余规则，提高分类效率是一项重要的研究内容。本文通过分析分类规则与训练集之间的映射关系，采用集合的相关运算寻找特征规则及相应特征集，从而消除分类规则集中存在的冗余，并在此基础上提出了基于集合运算的分类规则处理算法（PASO）。最后，以恒星光谱数据为背景，实验验证了该方法的正确性和可行性。 关键字 数据挖掘；分类规则；集合；恒星光谱数据 A Processing Method of Classification Rule based on Set Operation Abstract: Classification is one of the main tasks in the fields of data mining, and to eliminate the redundant rules in classification rule set is one of study focuses. In this paper, a processing algorithm of classification rule based on set operation is presented by analyzing the mapping relationship between rules and training data，and using set operations to get characteristic rule and its characteristic set，so that the redundant rules may be discovered and eliminated. In the end, experimental results validate its correctness and efficiency by using star spectra data as the decision system. Keywords: DM (Data Mining); Classification Rule; Set; Star Spectra Data 1引言 分类是用来抽取能够描述重要数据集合的模型，用于预测未知数据对象的离散类别，是数据挖掘和机器学习领域中的重要研究内容之一，在市场营销、金融投资、天文、地理的数据分析与决策等领域有着广泛应用[1]。 近年来国内、外学者在该领域做了大量研究，如何提高分类效率及分类质量是一个重要研究目标。采用分类规则获取方法的不同，分类质量及效率各有优劣。如概念格[2]，通过格结点间的关系获取的分类规则，具有精确性、分类质量高的特点，但是知识集容量较大；决策树分类方法[1，3], 采用贪心算法思想，自顶向下递归的方式造决策树，起源于概念学习系统，其获取的规则具有可理解性强的特征；贝叶斯分类法[1,4]是一种统计学分类方法，用于大型数据库中具有较高分类质量；此外，较常用的获取分类规则的方法还有粗糙集理论、模糊集、蚁群算法等[5-7]。在通过上述方法获取的分类规则集中，往往存在功能完全相同或a规则的功能是b规则功能子集的冗余现象，以及规则前件完全相同，但规则后件不同的冲突现象，导致在分类和预测过程中出现错误判断、效率低下等问题。消除这类问题的方法分为两大类：直接处理和后处理[8]。直接处理指的是在分类规则生成的过程中进行剪枝操作，即规则提取和规则剪枝同时进行，也即对原提取方法的改进，对分类的研究主要集中在分类质量。算法C4.5[9]中，Quinlan提出在生成规则的过程中，通过对规则的剪枝来消除冗余，并且Liu B [8]等在构造CBA分类器的过程中也采用这种技术来消除冗余；在一些关联规则的剪枝中也采用了这种方法，例如Calders等，在生成频繁项目集的过程中进行了剪枝操作[11]；后处理在已获取分类规则集后进行的，如Thabtah.F[12]在文中对挖掘出来的分类规则集进行剪枝，根据分类规则之间的关系，对规则集进行约简，消除规则集内存在的冗余； Bruha，Famili[13]提出的规则过滤方法，Huawen Liu等[8]采用闭集的方法对关联、分类规则进行约简，都是典型的规则后处理例子。 实际上，分类规则集与训练集之间存在一种映射（规则与记录间的适应关系）关系，本文在对这种映射关系进行分析的基础上，通过该映射，利用分类规则集将训练集划分为训练子集群，并利用子集群中各集合间的各种运算特征，描述并消除分类规则集中的冗余规则。在分类规则集后处理过程中，由于充分考虑了训练集数据的特征，可有效地提高分类效率。采用恒星光谱数据，实验验证该方法正确可行，从而为提高分类效率提供了一条有效途径。 2分类规则问题描述 分类是数据挖掘的一项重要任务，参照文献[1]，首先给出分类问题的相关定义： 定义1 设三元组T=(O,R,K)，其中O={x1,x2,… xn}表示数据集，R={r1,r2,…rn}表示规则集，KO×R是一个在O和R之间的二元关系，K={<x,r>|M(x,r)=1xOrR}，M(x,r)=1表示规则r能对数据x进行分类，否则M(x,r)=0，称该三元组T为分类背景。 在T中，二元关系K中的元素均为二元序偶，其第一元素与第二元素之间是一种数据记录与规则的映射关系。 定义2 设三元组 T=(O,R,K)是一个分类背景，在R®O上，算子f(r)={x|<x,r>K, xO,rR}，是O中适应规则r的所有记录集，在O®R上，算子g(x)={r|<x,r>K, xO,rR }，是R中记录x适应的所有规则集。 一条分类规则r能对多条数据进行分类，而能对一条数据x分类的规则也可能有多条。 定义3 设三元组 T=(O,R,K)是一个分类背景，P(O)={s|sO}为O的幂集，P(R)={s| sR}是R的幂集，在P(R)®P(O)上，f(Y)={x |"rY,(x,r)K，xO，YP(R) }，表示规则集Y中所有规则都适应的记录集；在P(O)®P(R)上g(X)={r|"xX,(x,r)K，rR，XP(O) }，表示记录集X所有记录都适应的规则集。 当|Y|=1时，f(Y)就表示能被规则Y分类的数据的集合，当|Y|>1时，即Y={r1,r2,…rm}，则f(Y)=f(r1)∩f(r2)∩…∩f(rm)；对于一条分类规则rR，规则的支持度为supp(r)=|f(r)|，其含义为能被规则r分类的数据的个数。而集合Y的支持度supp(Y)=|f(Y)|，含义为能被集合Y中所有规则分类的数据的个数。 定义4对于T=(O,R,K)，规则r1,r2R，若f(r2)f(r1)，称规则r1覆盖规则r2，记为r1 r2特殊地，若f(r1)=f(r2)，称r1与r2等价，记为r1 = r2。 规则r1覆盖规则r2，即对于任意的一条数据x，如果有(x,r2)K，则必有(x,r1)K，但是反之并不一定成立，且必有supp(r1)≥supp(r2)。两条规则r1和r2等价，如果一条数据能被规则r1进行分类，(x,r1)K，那么必有(x,r2)K，反之也一样成立，且必有supp(r1)=supp(r2)。 易见，对任意两条规则r1、r2，若r1 r2或 r1 = r2，所有能被r2分类的记录均可被r1分类，r2是冗余的。 定义5 任意YR，且Y中所有规则的决策属性相同，如果在Y中存在一个规则r，对于"r′Y都有f(r′)f(r)，且规则r的条件属性不多于规则r′的条件属性，称规则集Y为规则r的特征集，规则r称为Y的特征规则。 定理1：设Y是规则r的特征集，且|Y|>1，则规则集Y是可约简的，并且特征规则r与特征集Y的分类能力是等价的。 证明：由定义5中易得，"r′Y, f(r′)f(r)，则f(Y) f(r)；又rY，故f(Y) =f(r)，证毕。 3分类规则处理算法 3.1算法思想 通过各种工具获取的分类规则集中，存在大量的冗余规则，由上节定理1，首先在分类规则集中寻找特征规则及相应的特征集，然后保留特征规则，删除特征集中其余冗余规则，从而达到约简分类规则集的目的。 在寻找特征规则及相应特征集的过程中，首先对每条规则r，求解f(r)；将所有规则按其决策属性值（类属性）进行分组，并按规则前件容量（条件属性个数）进行升序排列，在寻找特征规则时，优先考虑条件属性个数较少的规则；选择某类小组为当前组，依次选择每条规则为假想特征规则，为其寻找特征集，并删除特征集中规则；如此反复，直至所有类小组全部过滤结束。 3.2算法描述 ALGORITHM: PASO(a Processing Algorithm based on Set Operation) INPUT：分类规则集R，训练数据集O OUTPUT：约简分类规则集R′ BEGIN 1.for(i=0;i<|O|;i++) 2. for(j=0;j<|R|;j++) 3. if(R[j]能对O[i]进行分类) 4. {将O[i]写入R[j]的分类记录集} 5.对规则集按类属性分组，并按条件属性个数进行升序排列 6.for(k=0;k<|R|;k++) 7． 初始化特征集Y=，将R[j]并入Y 8. for(m=k+1;m<|R|;m++) 9. if((R[j]覆盖R[m]) 10. 将R[m]并入Y中 11. if (|Y|>1) delete all rules in Y from R END. 算法的功能是分三步实现的，首先用规则集内的各个规则扫描数据库的各条数据，计算f(r)的过程，设规则集内有i条规则，数据集内有j条数据，则其时间消耗为O(i*j)；其次是对规则集内的规则进行分组排序的过程，主要时间消耗为O(j*j)；最后，特征规则及相应特征集的发现并消除冗余规则，消耗的时间为O(j*j)。因此，该影响该算法的主要因素为规则数及训练集记录数，时间复杂度可表示为O（j*j+ i*j）。 4实验分析 在Pentium(R)D-3.0G CPU，512M 内存，Windows XP操作系统，DBMS为ORACLE9i，用Visual C++实现了概念格和包含集的挖掘及处理算法。选用由国家天文台提供的SDSS恒星光谱数据作为实验数据集，并经过以下预处理后构成该实验中的数据集：1)选定间隔为20 Å的200个波长3810，3830，…7790 Å，依据流量、峰宽和形状，将每个波长离散化为十三种值；2)恒星的任意类型温度等间隔离散化为三种值，七类恒星温度离散化为二十一种值；3)根据恒星的光度、化学分度、微湍流、其它参数等间隔离散化为三种值。为了验证算法的正确性和有效性，对由概念格提取的分类规则集进行处理，处理前后对比结果如表1所示。 表1 分类规则集处理前后对比表 Table 1 the Compared Table of Classification Rule Sets 记录数 规则处理前 规则处理后 规则数 正确率 错误率 平均使用规则数 规则数 正确率 错误率 平均使用规则数 1000 1933 98.8% 1.2% 766.7 263 98.8% 1.2% 41.9 2000 4103 84.1% 15.8% 2503.3 486 84.1% 15.8% 89.7 3000 6105 81.9% 17.4% 3498.5 817 81.9% 17.4% 113.6 4000 7810 93.1% 6.7% 3578.9 1165 93.1% 6.7% 215.3 表1的实验结果可以看出：1）处理后规则数大幅减少，即减小了目标分类器的大小；这是因为原先的规则集中存在着大量的冗余规则，这大大增加了分类器内规则的数量，所以当对冗余规则进行处理之后，分类器的大小明显减小；2）在对分类规则结果进行测试过程中，避免了处理前对冗余规则的匹配，因此降低了平均使用规则数，从而有效地提高了分类效率；3）因为被处理的规则都为包含或者是等价规则，所以在处理后规则集的分类质量并没有改变。 5小结 分类是数据挖掘的主要任务之一，针对获取的分类规则中存在的冗余，通过采用集合的相关运算，寻找特征规则及相应特征集，从而消除冗余。该方法在对分类规则集进行后处理过程中，充分考虑到训练集的数据特征，有效地约简了分类规则集，有效地提高了分类效率。 参考文献 [1]J Han, M. Kambr. Data Mining Concepts and Techniques. Morgan Kaufmann Publishers. 2000 [2]张继福，马洋.一种基于约束概念格的恒星光谱数据自动分类方法[J], 光谱学与光谱分析， 2010,30 (2): 559-562 [3] Quinlan J R. Introduction of decision trees [ J ]. Machine Learning, 1986，1 (1): 84 - 100. [4] Rudy Sicard, Thierry Artières, Eric Petit. Learning iteratively a classifier with the Bayesian Model Averaging Principle[J], Pattern Recognition,2008,41(3):930-938 [5] HUANGLONG-JUN, ZHOU CA I-YING, HUANGMING-HE, et al.A new method for constructing decision tree based on rough set theory[J ]. Journal of Nanchang Institute of Technology, 2006, 25 (2) : 122 -125 [6]李洁，邓一鸣，沈士团.基于模糊区域分布的分类规则提取及推理算法[J]，计算机学报，2008，31（6）：934-941 [7]吴正龙，王儒敬等. 基于蚁群算法的分类规则挖掘算法[J]，计算机工程与应用，2004，40（20）：30-33 [8] Huawen Liu, Jigui Sun, HuijieZhang. Post-processing of associative classification rules using closed sets [ J ]. Expert Systems with Applications, 2008, 36 (3): 6659-6667 [9] Quinlan J R. C4. 5: Programs for Machine Learning [M]. SanMateo, Calif. :Morgan Kaufmann, 1993: 17 - 42. [10] Liu B,Hsu W,Ma Y.Pruning and summarizing the discovered association.In ACM SIGKDD International Conference on Knowledge Discovery & Data Mining,1999,p.125-134 [11] Calders,T,Rigotti,C,Boulicaut,J.F.A survey on condensed representations for frequent sets.Lecture Notes in Computer Science,2006,3848：64-80 [12]Thabtah,F.Rule Pruning in Associative Classification Mining.Proceedings of the IBIMA conference,2005,101-107 [13]Bruha,I,&Famili,A.Post processing in machine learning and data mining.ACM SIGKDD Explorations Newsletter,2000,p.110–114
作品图片
作品专业信息
撰写目的和基本思路
- 采用集合的相关运算寻找特征规则及相应特征集，从而消除分类规则集中存在的冗余，提高分类效率
科学性、先进性及独特之处
- 提出了基于集合运算的分类规则处理算法（PASO）
应用价值和现实意义
- 为提高分类效率提供了一条有效途径。
学术论文摘要
- 通过分析分类规则与训练集之间的映射关系，采用集合的相关运算寻找特征规则及相应特征集，从而消除分类规则集中存在的冗余，并在此基础上提出了基于集合运算的分类规则处理算法（PASO）。最后，以恒星光谱数据为背景，实验验证了该方法的正确性和可行性。
获奖情况
- 已投稿
鉴定结果
- 无
参考文献
- 数据挖掘；分类规则；集合；恒星光谱数据
同类课题研究水平概述
- 分类是用来抽取能够描述重要数据集合的模型，用于预测未知数据对象的离散类别，是数据挖掘和机器学习领域中的重要研究内容之一，在市场营销、金融投资、天文、地理的数据分析与决策等领域有着广泛应用。 近年来国内、外学者在该领域做了大量研究，如何提高分类效率及分类质量是一个重要研究目标。采用分类规则获取方法的不同，分类质量及效率各有优劣。如概念格，通过格结点间的关系获取的分类规则，具有精确性、分类质量高的特点，但是知识集容量较大；决策树分类方法, 采用贪心算法思想，自顶向下递归的方式造决策树，起源于概念学习系统，其获取的规则具有可理解性强的特征；贝叶斯分类法是一种统计学分类方法，用于大型数据库中具有较高分类质量；此外，较常用的获取分类规则的方法还有粗糙集理论、模糊集、蚁群算法等。在通过上述方法获取的分类规则集中，往往存在功能完全相同或a规则的功能是b规则功能子集的冗余现象，以及规则前件完全相同，但规则后件不同的冲突现象，导致在分类和预测过程中出现错误判断、效率低下等问题。消除这类问题的方法分为两大类：直接处理和后处理。直接处理指的是在分类规则生成的过程中进行剪枝操作，即规则提取和规则剪枝同时进行，也即对原提取方法的改进，对分类的研究主要集中在分类质量。算法C4.5中，Quinlan提出在生成规则的过程中，通过对规则的剪枝来消除冗余，并且Liu B 等在构造CBA分类器的过程中也采用这种技术来消除冗余；在一些关联规则的剪枝中也采用了这种方法，例如Calders等，在生成频繁项目集的过程中进行了剪枝操作；后处理在已获取分类规则集后进行的，如Thabtah.F在文中对挖掘出来的分类规则集进行剪枝，根据分类规则之间的关系，对规则集进行约简，消除规则集内存在的冗余； Bruha，Famili提出的规则过滤方法，Huawen Liu等采用闭集的方法对关联、分类规则进行约简，都是典型的规则后处理例子。 实际上，分类规则集与训练集之间存在一种映射（规则与记录间的适应关系）关系，本文在对这种映射关系进行分析的基础上，通过该映射，利用分类规则集将训练集划分为训练子集群，并利用子集群中各集合间的各种运算特征，描述并消除分类规则集中的冗余规则。在分类规则集后处理过程中，由于充分考虑了训练集数据的特征，可有效地提高分类效率。 实验验证该方法正确可行，从而为提高分类效率提供了一条有效途径 。
