基于粗糙集的决策树在产品缺陷检测中的应用

吴学辉

(运城学院 计算机科学与技术系,山西 运城 044000)

基于粗糙集的决策树在产品缺陷检测中的应用

吴学辉

(运城学院 计算机科学与技术系,山西 运城 044000)

将数据挖掘中的决策树与粗糙集理论进行了有机结合,提出了一种基于粗糙集技术的决策树构造算法,并将该算法应用于胶合板缺陷检测．通过粗糙集属性约简,找出造成胶合板缺陷的关键因素;再基于约简后的决策表,使用该决策树算法构建决策树,从而提取分类规则,指导决策过程．通过实验验证了,该算法可以有效对胶合板的缺陷进行检测．

粗糙集;决策树;属性约简

0 引言

当前,数据挖掘技术在许多领域得到广泛应用,如教育、零售业、医疗、保险、股票等．它可以从各行业积累的大量数据中发现隐藏的知识．数据挖掘中的决策树技术可以对数据进行分类,提取有用规则．粗糙集作为处理不完备信息的有效工具,已经广泛应用于知识发现、问题求解等领域[1，2]．粗糙集属性约简通过删除不相关或不重要的属性,简化原有系统．通过它可以对决策树分类属性进行约简,从而使构造的决策树模型简单,预测分类精度更高．

在胶合板生产过程中,胶合板在生产线上以2～3 m/s的速度运行,人工检测的时间非常短,大约只有1～2 s,更主要的是这种单调重复的工作容易引起工人的误分类,相关实验表明人工检测缺陷的准确率只有68%．为了减轻工人的检测负担,提高检测缺陷的准确率,采用自动检测系统是非常必要的．自动检测系统得到大量数据,如何对这些大量数据进行分类是检测面临的最大问题．本文将基于粗糙集的决策树算法应用于胶合板缺陷检测分类．利用粗糙集属性约简确定最简决策表,最后通过决策树方法提取规则,指导决策过程．

1 基本概念

1.1粗糙集理论

粗糙集理论是由波兰教授Pawlak Z提出的一种数据挖掘新方法．它是当前处理不完全和不精确信息的一种有效工具,已经广泛应用于知识发现、模式识别、专家系统以及不确定推理等领域[3，4]．本文研究中所涉及的粗糙集相关理论如下:

定义 1一个信息系统S可表示为:S=〈U,R,V,f〉．其中:

1)U为对象的集合．

2)R=C∪D,C为条件属性集合,D为决策属性集合．

4)f:U×R→V是一个信息函数．

[x]R⊆X}

定义 4(属性核)P和Q是论域U上的两个等价关系簇,如果Q⊆P独立,并且IND(P)=IND(Q),则称Q是P的约简,在每个约简中都不可缺的关系集合称为核,记为COREQ(P)．其中COREQ(P)=∩REDQ(P),P的所有Q约简关系簇为REDQ(P)．

1.2决策树算法

决策树作为一种分类方法,已经在许多领域得到广泛应用．它是一种基于知识表示的树,用于表示分类规则．叶节点代表类标号,而其他节点代表与被分类对象相关联的属性．从决策树的根节点到叶节点的一条路径就是一条决策规则[5]．

ID3算法是决策树的经典算法,它以信息熵和信息增益度为标准,对数据进行归纳分类．信息量和熵定义如下:

信息量:information=-log2pi

熵:Entropy=-∑pilog2pi

1)数据集S划分前的熵:

其中,pi=ni/n．因为信息以二进制编码,所以对数的底为2．

2)数据集S划分后的熵:

3)数据集S划分前后的熵差:Gain(S,A)=E(S)-E(S,A),Gain(S,A)为信息增益,用系统墒的减少值描述．表示系统由于分类获得的信息量,Gain(S,A)是指熵的期望压缩,其值越大,表明属性A对分类提供的信息量越大．ID3算法的核心思想就是选择信息增益最大的属性作为结点,再在每个分支中采用递归方法构建决策树．

1.3基于粗糙集的决策树算法

决策树进行分类时,生成的分类模型简单,精度也较高,但当决策属性过多时,生成的分类模型复杂,而粗糙集在消除决策表冗余属性方面有其特殊优势[6]．

本文将二者结合起来,首先通过属性约简去掉冗余属性,得到属性核,接着利用ID3算法对约简后的决策表进行决策树的构建,产生相应的分类规则．

基于粗糙集的决策树算法描述如图1所示．

该算法的基本步骤如下:

1)收集相应的训练数据集,删除重复记录．

2)对训练集进行离散化处理．

3)将离散化的数据用粗糙集属性约简算法求出属性核．

4)依据约简后的核属性,筛选新的数据集.

5)对此数据集进行决策树的构建,建立决策树模型．

6)用该决策树模型对测试数据集进行预测分类．

2 实验结果与分析

2.1决策表离散化

本文抽取某企业胶合板缺陷检测数据作为样本数据,并利用谱系聚类法[7，8]对每条记录进行离散化,离散化的结果如表1所示．论域U={1,2,3，…,10},条件属性C={灰度均值,灰度中值,灰度最频值,灰度标准差,偏度,峰度,黑像素数,亮像素数,最低灰度值,最高灰度值,直方图黑区尾部长度,直方图白区尾部长度,均值为域值的边缘像素数,以μ-σ为阈值后像素数,特征14的边缘像素数,以μ+σ为阈值后像素数,特征16的边缘像素数},在表中用1-17来表示．决策属性D={检测类型}．其值为1,2,3,4,其中,1表示树皮缺陷,2表示无缺陷,3表示有彩色条纹,4表示有皱状纹理．

2.2属性约简

属性约简常用算法有盲目法和启发式约简算法[9，10]．前者在时间和空间上开销较大,因此本文采用后者对表1进行约简,最后得到的决策表如表2所示．

从约简后的结果可以看出,属性2,3,4,8,12,14是冗余属性,对于决策属性是不必要的,而属性1,5,6,7,9,10,11,13,15,17是核属性．对决策属性是必要的．

2.3构建决策树

针对表3,用ID3算法构建决策树,过程如下:计算各个条件属性的信息增益,Gain(11)=0.724,Gain(17)=0.701,Gain(9)=0.608,Gain(10)=0.537,Gain(15)=0.451,Gain(7)=0.449,Gain(1)=0.429,Gain(6)=0.194．条件属性11的信息增益最大,因此将条件属性11将作为决策树的根节点,当分类属性11为2时,论域子集{2,8},由于该子集中的决策属性为同一类,所以停止选择属性．当分类属性11为1时,论域子集{1,3,4,5,6,7,9,10},由于它的决策属性不为一类,继续选择属性分类,依据ID3算法再次选择信息增益最大的属性17,作为决策树的根节点,递归地构建决策树,以此类推,最终构造的决策树如图2所示．

从构造的决策树可以看出,如果只用ID3算法则由于条件属性有17个,构造出的决策树很复杂,而用粗糙集属性约简后,只有10个必要属性,用约简后的决策表,构造的决策树简单,计算复杂度明显降低．

2.4规则提取

从图2构造的决策树,得到以下分类规则:

1)IF直方图黑区尾部长度=“2”THEN检测类型=“彩色条纹”．

2)IF直方图黑区尾部长度=“1”AND特征16的边缘像素数=“1”AND最低灰度值=“2”THEN检测类型=“树皮缺陷”．

3)IF直方图黑区尾部长度=“1”AND特征16的边缘像素数=“1”AND最低灰度值=“1”AND最高灰度值=“1”THEN检测类型=“树皮缺陷”．

4)IF直方图黑区尾部长度=“1”AND特征16的边缘像素数=“1”AND最低灰度值=“1”AND最高灰度值=“3”AND特征14的边缘像素数=“1”AND黑像素数=“1”THEN检测类型=“有皱状纹理”．

5)IF直方图黑区尾部长度=“1”AND特征16的边缘像素数=“1”AND最低灰度值=“1”AND最高灰度值=“3”AND特征14的边缘像素数=“1”AND黑像素数=“3”THEN检测类型=“树皮缺陷”．

6)IF直方图黑区尾部长度=“1”AND特征16的边缘像素数=“2”AND最低灰度值=“1”THEN检测类型=“树皮缺陷”．

7)IF直方图黑区尾部长度=“1”AND特征16的边缘像素数=“2”AND最低灰度值=“2”THEN检测类型=“无缺陷”．

2.5模型准确性评估

数据挖掘最后一个步骤就是对模型准确性评估．模型准确性评估就是利用已生成的决策规则来预测未知数据,判断未知数据属于哪一分类,再通过预测结果与实际情况吻合的比率来判断该模型是否有效．在WEKA软件中,将胶合板缺陷检测数据中的前10%作为训练集,剩余90%作为测试集．实验证明,用基于粗糙集的决策树算法进行分类后,预测准确率达88.3%,比人工检测缺陷的准确率提高将近20个百分点．

3 总结

本文提出了将粗糙集和决策树结合,利用粗糙集对决策表中的条件属性进行约简,去除多余属性后,再用ID3算法构造决策树,提取规则,并将其用于胶合板缺陷检测,并最终为企业提供决策支持．实验表明该方法快速有效,生成的规则简单准确,计算复杂度明显降低．

[1] QUINLAN J R.Induction of decision trees[J].Machine Learning,1986(1):81-106

[2] 王熙照,杨晨晓.分支合并对决策树归纳学习的影响[J].计算机学报,2007,30(8):1251-1258

[3] ZIARKO W.Variable precision rough set model[J].Journal of Computer and System Sciences,1993,46(1):39-59

[4] 高 隽.智能信息处理方法导论[M].北京:机械工业出版社,2004:254-255

[5] 翟俊海,王熙照,张沧生.基于粗糙集技术的决策树归纳[J].计算机工程与应用,2009,45(11):45-47

[6] 周玉敏.基于Rough集的数据挖掘在教学评价中的应用[J].重庆邮电大学学报,2008,11(3):155-156

[7] 韩中华,马 斌.基于谱系聚类的粗糙集数据挖掘预处理方法[J].计算机工程与应用,2008,32(8):23-25

[8] 何 明.一种改进的粗糙集属性约简启发式遗传算法[J].西安石油大学学报,2004,19(3):80-86

[9] 黄宇颖.基于粗糙集的决策树算法在体检系统中的研究[J].计算机工程与应用,2008,44(25):78-80

[10] 吴尚智.粗糙集和信息熵的属性约简算法及其应用[J].计算机工程,2011,37(7):56-61

The Application of Decision Tree Technology Based
on Rough Sets in Detection of the Plywood Defect

WU Xuehui

(Department of Computer Science and Technology, Yuncheng University, Yuncheng 044000, China)

Through the combination of the Decision Tree and Rough Set Theory in Data Mining, a decision tree construction algorithm based on Rough Set technology is proposed. And the algorithm is applied to the detection of the plywood defect. Rough set attribute reduction is used to find out the key factors caused the plywood defect. Then on the foundation of the reduction decision table, the decision tree is constructed by use of this algorithm, so as to extract the classification rules and to guide the decision-making process. In the end, the experiments prove that the algorithm can detect the plywood defect effectively.

rough set;decision tree;attribute reduction

2015-07-29

吴学辉(1978-),男,山西运城人，硕士,太原理工大学计算机与软件学院讲师，主要从事数据挖掘，粗糙集研究.

1672-2027(2015)03-0037-05

TP18

A