改进项编码及粗糙集算法在病害蔬菜叶片图像挖掘中的应用

罗晓丽

（福州职业技术学院 计算机系，福建 福州 350108）

温室蔬菜生产由于是在人为控制生产，周年生产、难以轮作等因素，使得病害极易发生，传统的病虫害检测是通过专家观察，凭经验根据感病蔬菜叶片上病斑的颜色或形状判断病害的种类。笔者在大量的数据基础上，在项编码基础上，利用粗糙集约简的方法进一步挖掘出病害受损程度的图像特征属性及特征区间。

1 基于项编码的的Apriori算法及改进算法

1.1 Apriori算法原理

Agrawal等首次提出将关联规则[1]应用于解决挖掘顾客交易数据中项目集间问题，其核心是基于2阶段频繁集思想（即发现频繁项目集和生成关联规则）的递推算法，其典型算法是Apriori算法，该算法的主要内容如下：（1）使用逐层搜索的迭代方法。首先过扫描数据库，计算出各个频繁1-项集的支持度，找出所有频繁1-项集L1，得到频繁1-项集的集合。（2）连接步。由2个只有一个项不同的频繁1-项集进行JOIN运算得到的候选频繁2-项目集C2。（3）剪枝步。对C2进行修剪得到频繁项集L2。（4）通过扫描数据库，计算各个项集的支持度，将不满足支持度的项目集去掉，通过迭代循环，重复步骤2～4，直到找到最大频繁项集，此时算法停止。

随着扫描的数据量增大，Apriori算法也呈现出明显不足：（1）候选集Ck中的每个元素都必须通过扫描数据库一次计算支持度，来确定其是否能成为频繁项集 Lk中的元素，而多次扫描事务数据库，需要很大的I/O负载。（2）随着扫描数据库的事务量增大，可能有庞大的候选集产生。规模巨大的候选项集，不仅处理需要占用大量的主存空间，而且算法必须耗费大量的时间来处理。例如：对于1-频繁项集个数如果是10 000个，那么可能产生的候选集就会有个。

1.2 基于项编码的CA算法

基于项编码的 CA算法[2]，只需要扫描数据库一次，并对每个项完成编码转换，根据它在数据库中出现的事务记录用0和1进行编码，以后的过程都是针对编码进行运算，统计1的个数计算支持数k项频繁项集，通过编码与运算生成K+1项频繁项集，不需要再次扫描数据库。其具体特点如下：（1）编码运算。该算法只需要扫描一次数据库，并对每个项在某个事务记录中是否出现进行编码，以“出现为1，不出现为0”的原则进行编码，以后的过程都是针对编码进行与运算。与Apriori算法相比，该算法仅扫描数据库一次，因而减少了算法的I/O负载。（2）连接前剪枝。CA算法在对频繁(k-1)-项集Lk-1通过与运算进行连接，得到候选频繁k-项集Ck，并对Lk-1中1的个数进行计数处理，根据计数结果删除Lk-1中包含出现次数小于(k-1)的项的项集，以减少参加连接的(k-1)项的数量，从而降低了组合的数据量，也减小了候选频繁 k-项集 Ck的大小。但该算法在进行编码转换时需要消耗大量时间，而且编码数位过长，I/O的负载过大；同时由于编码过长，造成与运算的繁复，可见记录的个数极大地影响了该算法运行的时间。

1.3 改进算法

通过上述分析可知，要提高算法的运行效率，可从如下方面进行处理：（1）降低扫描事务的记录数；（2）计算支持度时减少扫描数据库的次数。由此笔者提出通过减少数据库的记录数来减小编码转换时间的改进算法，其基本思路是先进行一次扫描，计算出候选频繁1-项目集，将含有1-项目集的记录重新组合生成新的数据库（比原来的数据库记录大为减少，尤其是海量数据库减少的记录数量更多），并利用CA算法对新生成数据库进行编码转换。这样以后不再扫描的数据库，而是通过编码与运算生成候选频繁项集，通过统计项编码中1的个数计算支持度。由于只进行一次扫描，且缩小了扫描范围，因而加快了运算速度，提高数据挖掘的效率。

改进算法的具体描述如下：

输入：事务数据库D；最小支持度阈值min_sup

输出：D中的频繁项集L

{C1=candidate1-Itemsets}；//生成候选频繁1-项目集，一般情况下，令T1={{I1},{I2},{I3}…{Im}}，即T1为所有项目的集合。

L1={p∈T|Sup (p)≥min_sup}；//扫描事务数据库D一次，生成频繁1-项集。

Copy * to D2for c ∈L1//生成缩小的新的数库，并对该数库进行编码转换。

2 粗糙集约简算法[3]

2.1 决策表

设Q=（U, A, V, f）是一个信息系统，U为论域，即为数据库所有对象集合，A为属性集，C为条件属性，D为决策属性，V为属性集的值域，f:U×A→V，A=C∪D。

2.2 等价类及相关概念

设数据库U={x1, x2, x3, x4, x5, x6,…}，属性集A={a1,a2, a3, a4, a5, a6,…}，条件属性C={a0, a1, a2, a3, a4, a5,a6, …}，决策属性D={am}，属性集的值域V={V1, V2, V3,V4, V5, ……}。

定义1 对于属性集A中任意一个属性a，若xi和xj所对应属性a的取值相等，则有xi，xj基于属性a等价。

定义 2 属于同等价类的记录归为一类，论域基于属性A的划分可表示为U={U1, U2, U3, U4, U5, U6, ……}。

2.3 属性约简与规则生成

（1）对于每一个 a∈C，按属性值个数排列，排序后为{a0, a1, a2, a3, a4, a5, a6, ……ak}；

（2）令a0=0, a1=1……ak-1=k-1, j=0, c=aj+1, aj+1=aj

If aji=a(j+1)i ‘判断决策表是否相容

相容：a(j+2)i=a(j+2-1)i……, aki=a(k-1)i，则合并相同的行

不相容：a(j+1)i=c

令j=j+1, if j=k，则输出a0, a1, a2, a3, a4, a5, a6, …ak-1

Else goto (2)

3 研究目标与方案确定

研究目的是找出病斑受病害程度严重与其他特征的关联规则。运用改进的Apriori算法得到极大相关组，其属性值的划分过细，存在数据冗余现象，进一步通过属性约简，可以得到更为客观科学的关联规则。因此本文采用粗糙集约简理论合理划分属性区间，以使挖掘出的规则更科学。

4 应用

4.1 图像数据挖掘

传统的数据挖掘[4]称为数据库中的知识发现（Knowledge Discovery in Database，KDD），是从存放在数据库、数据仓库或其他信息库中的大量复杂的原始的数据中，提取出对人们的决策有价值的知识或规则的过程。而这种知识或规则是人们事先不知道的但又对决策者分析历史或现在数据，挖掘出有价值的数据模型，对现在的决策或将来的预测有价值的规则或知识。随着图形图像及多媒体信息的日益发展，图像数据挖掘显得越来越重要。从图像数据库中取得一些先验知识对图像信息的进一步提取的准确性及时效性显得尤为重要。图像数据库的建立有微观和宏观角度两种，微观是把图像看成由无数个象素点作为对象的数据库，研究每个象素点的灰度、颜色、像距等；宏观可以把图像的局部作为对象创建数据库，进而研究对象的灰度、颜色、大小、纹理等属性。

4.2 实验步骤及结果

（1）实验环境：在同样的实验条件下（服务器：P4 2.0 GHz、4 G内存、SQL Server2000；客户机： P4 3.9 GHz、2 G内存）。

（2）实验数据预处理：选用563片黄瓜霜霉病叶片利用photoshop工具分离病斑图像共计2 457块病斑连通图像区域数据，取得图像特征属性：面积A、颜色C、亮度B、位置P、周长G、灰度均值H、形状R等。如表1。

表1 黄瓜叶片病斑图像特征

（3）运用改进的Apriori算法得到支持度大于30%的极大相关组{ACHR}，表明受害程度与亮度、位置无关，与面积、颜色、灰度均值、形状极大相关。

（4）并根据每个特征最大与最小值，划属性区间，将属性值离散化，将颜色属性定为决策属性按浅绿和浅黄、棕色和褐色C={1,2,3}（颜色的深浅表明受害程度的大小），D={A, P, H, R }为条件属性，如面积按[0, 0.5]，[0.5, 1]，[1，1.5]，[1.5, 2]，[2, +∞]区间离散 A={1, 2, 3, 4, 5}；灰度均值按[120，130]，[130，140]，[140，150]，[140，150]，[160，+∞]区间离散 H={1，2，3，4，5, 6, 7}；形状按圆形、三角形、长条形得到集合R={1, 2, 3}。原始数据初始化如表2。

表2 黄瓜叶片病斑受害情况决策表

（5）利用粗糙集约简算法，对上述表中属性进行约简，发现相对于颜色决策属性，面积属性值1、2合并，3、4、5合并约简，灰度均值1、2合并，3、4合并，5、6合并，形状属性值2、3、4合并约简。

挖掘结果：病斑面积较小低于1时，形状接近圆形，且颜色较浅，颜色偏绿色黄色，灰度均值在区间[12，140]，受害程度较轻。而当面积较大超过1时，形状不规则，且颜色较深，颜色偏棕褐色，灰度均值在[140，+∞]，受害程度较为严重。

5 结论

借鉴经典的Apriori算法及其优化解决方案，提出了一种保留含有频繁1-项集的数据库作为扫描的数据库，不仅缩小了扫描数据库的规模，而且减少了编码转换位长，逐步缩小了数据库搜索的时间和进行运算的时间，从而极大提高了算法的运行效率。对于图像数据量大、繁杂，这种算法尤为适合。对于图像数据预处理，使用粗糙集约简算法得出的挖掘规则，可以科学动态地划分离散区间，从而挖掘出的结果更具科学性。

[1] 黄建明.关联规则挖掘算法的研究与应用[D].西安:西安建筑科技大学,2009.

[2] 李磊,向正义.一种基于二项编码的改进设计[J].微计算机信息,2009(21):214-215.

[3] 张亦军.基于粗糙集和遗传算法的大数据集数据挖掘应用研究[D].太原:太原理工大学,2012.

[4] 韩家玮.数据挖掘·概念与技术[M].北京:机械工业出版社,2006:66-69.