, 汤建国3, 唐加福11. 东北大学 信息科学与工程学院, 辽宁 沈阳 110819;
2. 杭州电子科技大学 管理学院, 浙江 杭州 310018;
3. 云南中烟工业有限责任公司 技术中心, 云南 昆明 650231
收稿日期：2016-07-11
基金项目：国家自然科学基金资助项目(71771070)。
作者简介：张忠良(1986-)，男，浙江嘉兴人，东北大学博士研究生;
雒兴刚(1971-)，男，新疆奇台人，东北大学教授，博士生导师;
唐加福(1965-)，男，湖南东安人，东北大学教授，博士生导师。
摘要：针对智能卷烟感官评估系统中涉及的多分类问题, 采用“一对一”(one-versus-one, OVO)分解策略将复杂的多分类问题分解成多个易于处理的二分类子问题, 然后针对这些子问题分别建立二值分类器, 最后采用一定的聚合策略将二值分类器组合成多类分类器.此外, 分别采用基于动态分类器选择和基于距离相对竞争力加权法对OVO中的冗余二值分类器进行处理, 从而降低其对OVO系统的消极影响.为了验证所采用的方法在智能卷烟感官评估中的有效性, 采用国内某烟草公司提供的数据集进行对比实验.实验结果表明, 在智能卷烟感官评估中基于OVO分解策略的多分类方法比传统方法具有更优的分类性能.
关键词：多分类一对一分解聚合策略卷烟感官质量智能评估
Intelligent Cigarette Sensory Evaluation Method Based on OVO Decomposition Strategy
ZHANG Zhong-liang1,2, LUO Xing-gang1,2
, TANG Jian-guo3, TANG Jia-fu11. School of Information Science & Engineering, Northeastern University, Shenyang 110819, China;
2. School of Management, Hangzhou Dianzi University, Hangzhou 310018, China;
3. Technology Center, China Tobacco Yunnan Industrial Co., Ltd., Kunming 650231, China
Corresponding author: LUO Xing-gang, professor, E-mail: xgluo@mail.neu.edu.cn
Abstract: Intelligent cigarette sensory evaluation system involves multi-class classification problems. The one-versus-one (OVO) decomposition strategy was employed to divide the multi-class classification problem into several easier-to-solve binary sub-problems. Then binary classifiers were established for these sub-problems. Finally, an aggregation strategy was adopted to combine the binary classifiers to be a multi-class classifier. In addition, dynamic classifier selection for OVO strategy (DCS-OVO) and distance-based relative competence weighting for OVO strategy (DRCW-OVO) were used to reduce the negative effect of the non-competent classifiers. In order to verify the effectiveness of the employed method in intelligent cigarette sensory evaluation, the experimental comparison by using the dataset from a Chinese tobacco company was carried out. The results indicate that the OVO decomposition strategy outperforms the classical methodology in intelligent cigarette sensory evaluation.
Key Words: multi-class classificationone-versus-one(OVO) decompositionaggregation strategycigarette sensory qualityintelligent evaluation
感官品质是评价卷烟质量的重要标准.然而, 由于烟草的物化指标与卷烟的感官质量之间存在着极其复杂的非线性关系, 很难建立起两者之间有效的数学模型.目前, 人们主要通过人工评吸的方式对卷烟新产品开发和产品维护过程中涉及的卷烟感官质量进行评估.然而, 这种完全依赖评吸专家经验的方式容易受到其主观因素以及客观环境的影响, 同时也对评吸专家的身体健康产生一定的负面影响.此外, 现代企业面对着越来越复杂的市场环境, 需要卷烟企业在新产品开发和产品维护中, 具有更高的效率和灵活性.
为了解决上述问题, 研究人员开始采用数据挖掘技术对卷烟感官质量进行评价[1], 试图从大量积累的烟草数据中获得烟叶物理化学指标和卷烟感官质量之间的映射关系, 以辅助或代替评吸专家完成对卷烟感官质量的评价.当前主要以神经网络[2]或支持向量机[3]来解决成品卷烟的智能化感官评估问题.
然而, 卷烟感官质量具有多个等级, 历史数据涉及多分类问题, 而目前的研究主要采用分类算法直接处理多分类问题.由于多分类问题的复杂性, 采用这种直接的方式进行卷烟感官质量预测往往不能获得预期的效果.另一方面, 研究表明[4]采用一对一(one-versus-one, OVO)分解策略可以有效提高分类算法处理多分类问题的性能.因此, 本文采用OVO分解策略将智能卷烟感官评估中涉及的多分类问题分解成多个易于处理的二分类子问题, 然后对每个子问题分别建立二值分类器, 并采用聚合策略将二值分类器组合成多类分类器.
为了验证本文所采用方法在智能卷烟感官评估中的有效性, 将其应用在烟草公司采集的数据集上, 并比较了6种不同的聚合策略的效果.此外, 为了分析基分类器对本文方法的影响, 分别采用决策树、神经网络和支持向量机作为基分类器进行了实验比较.结果表明, 不管采用何种基分类器, 采用OVO分解策略均比经典的多类分类器的预测效果具有明显的优势.
1 数据和方法1.1 数据本文所采用的实验数据是国内某烟草公司在2010~2012期间所采集的日常检测数据, 包括成品烟的常规化学成分以及相应的卷烟感官质量, 数据样本个数为684个.其中, 常规化学成分包括总糖量等13项指标, 将作为训练分类器时的输入属性; 每个样本对应包括5项卷烟感官质量评估指标, 分别为光泽、香气、杂气、刺激性、余味, 作为分类器的决策属性.针对每项评估指标, 首先由多名卷烟感官评估专家根据感官质量评判标准(如表 1所示)分别进行独立评估, 然后通过计算所有专家给出的结果的平均值, 从而得到相应指标的最终评估结果.由于针对卷烟感官质量的评估指标有5项, 因此本文共采用5组数据集.
表 1(Table 1)
 表 1 感官质量判定标准Table 1 Assessment criteria for sensory quality
| 表 1 感官质量判定标准 Table 1 Assessment criteria for sensory quality | ||||||||||||||||||||||||||||
1.2 方法1.2.1 OVO分解策略OVO分解策略针对多分类问题, 将其分解成多个二分类子问题.其基本思想如图 1所示:首先将m类问题分解成m(m-1)/2个二分类子问题, 然后对每个子问题分别独立地建立二值分类器.这样复杂的多分类问题就被分解成多个较易识别的二分类子问题.
图 1(Fig. 1)
 | 图 1 “一对一”分解策略示意图Fig.1 Illustration of "one versus one" decomposition |
为了识别未标识样本, OVO方法一般需要两个步骤.1)利用分类算法训练二值分类器用以区分成对类{Ci, Cj}; 2)集成阶段.置信度rij∈[0, 1]表示二值分类器相对于类别j将未标识样本预测为类别i的概率, 并且rji=1-rij.对每个成对类别分别进行相同的操作, 就可以得到一个完整的分值矩阵:
 | (1) |
1.2.2 聚合策略由上文可知, OVO分解策略的关键是将分值矩阵集成得到最终的输出结果.本文采用以下几种方法.
1) 投票法(voting strategy, VOTE)[4].该方法利用投票机制获得最终类别标识, 获得最多投票的类别作为输出结果.预测类别为
 | (2) |
2) 加权投票法(weighted voting, WV)[5].在加权投票法中, 每个二值分类器以置信度的形式给出结果, 预测结果如式(3)所示:
 | (3) |
 | (4) |
 | (5) |
 | (6) |
 | (7) |
 | (8) |
 | (9) |
 | (10) |
 | (11) |
1) 动态分类器选择的OVO策略(dynamic classifier selection for OVO strategy, DCS-OVO)[10], 该方法考虑避免没有竞争力的子分类器对最终结果的负面影响.首先, 在训练集中确定待测样本的k个最近邻, 然后观察邻域中包含的类别, 最后将原始分值表中删去邻域中没有的类别的相应信息, 从而获得新的分值表.这里采用的最近邻数为类别数的3倍, 如果邻域中只有一个类别, 则最近邻数扩大到6倍.最后针对新的分值表采用WV获得最终的输出结果.
2) 基于距离相对竞争力加权的OVO策略(distance-based relative competence weighting for OVO strategy, DRCW-OVO)[11], 该方法将距离引入到权值的计算中.对于待测样本, 训练集中与其越接近的样本所对应的类别将获得更大的权值.对于训练集中的每一个类别, 计算与待测样本最邻近的k个样本, 并计算出该类别与待测样本的平均距离.然后对于训练集中m个类别都进行如上操作, 获得平均距离向量d=(d1, …, dm)新的分值表就由rij·wij构成, 采用WV获得最终的预测结果.
 | (12) |
2 实验测试与分析2.1 数据预处理由前文所述可知, 卷烟感官质量评估历史数据是多个评估结果的平均值, 因此原始数据集中的数据不是离散值.然而, 针对卷烟感官质量的评估结果应该为离散值, 因为卷烟感官质量评估专家基于表 1以0.5为间隔对评估指标进行评价打分.基于此, 本文从卷烟感官质量评估的实际出发, 采用等间隔的离散方法对决策属性进行离散化处理, 离散结果如表 2所示.以光泽为例, 打分评判标准为3~5, 因为实际数据集中没有小于3.75的数据, 因此, 将[3.75, 4.25]内的样本标记为类别1, (4.25, 4.75]标记为类别2, (4.75, 5.00]标记为类别3.
表 2(Table 2)
表 2 离散化结果Table 2 Results of the discretization
| 表 2 离散化结果 Table 2 Results of the discretization |
根据表 2离散化之后的5组数据集的基本信息如表 3所示.
表 3(Table 3)
表 3 数据集信息描述Table 3 Summary description of datasets
| 表 3 数据集信息描述 Table 3 Summary description of datasets |
此外, 需要对每一个条件属性进行归一化处理, 归一化方法:
 | (13) |
本文采用“交叉验证法”(cross validation)进行实验评估.首先, 将数据集按照分层抽样的方式划分成大小相似的互斥子集; 然后, 每次采用其中的4个子集的并集作为训练分类器的训练数据集, 剩下的那个子集作为测试数据集; 最后, 计算5次实验的平均分类准确率.重复进行5次这样的实验, 5次的平均结果作为最终分类预测准确率.
2.2 基分类器及其参数设置为了分析不同基分类器的影响, 分别采用决策树、神经网络以及支持向量机作为基分类器进行实验.所采用的基分类器的参数设置如表 4所示.
表 4(Table 4)
表 4 基分类器的参数设置Table 4 Parameters setting for the base classifiers
| 表 4 基分类器的参数设置 Table 4 Parameters setting for the base classifiers |
2.3 实验结果采用分类准确率作为各个方法的评价指标, 即分类准确率=(正确分类样本数/样本总数)×100%.表 5~表 7是本文实验的结果, “Base”表示直接采用基分类器得到的结果, 由于目前还没有有效的方法将支持向量机直接运用于多分类问题, 所以表 7中没有“Base”列.另外, 每个结果后面括号内的数值表示该方法在对应数据集中的效果的排列名次.
表 5(Table 5)
表 5 以决策树为基分类器的卷烟感官质量分类准确率Table 5 Classification accuracy of cigarette sensory quality with decision tree as the base classifier
| 表 5 以决策树为基分类器的卷烟感官质量分类准确率 Table 5 Classification accuracy of cigarette sensory quality with decision tree as the base classifier |
表 6(Table 6)
表 6 以神经网络为基分类器的卷烟感官质量分类准确率Table 6 Classification accuracy of cigarette sensory quality with neural network as the base classifier
| 表 6 以神经网络为基分类器的卷烟感官质量分类准确率 Table 6 Classification accuracy of cigarette sensory quality with neural network as the base classifier |
表 7(Table 7)
表 7 以支持向量机为基分类器的卷烟感官质量分类准确率Table 7 Classification accuracy of cigarette sensory quality with support vector machine as the base classifier
| 表 7 以支持向量机为基分类器的卷烟感官质量分类准确率 Table 7 Classification accuracy of cigarette sensory quality with support vector machine as the base classifier |
从表 5~表 7中可以清楚地看出, 在3种不同的基分类器的情况下, 无论是针对每一个感官指标的预测效果, 还是总体的平均结果, 基于OVO分解策略的预测效果都明显优于传统的方法.另外, 不同的聚合策略所产生的效果也不尽相同:当决策树作为基分类器时, DRCW-OVO的效果最好, 其平均结果比经典的分类器(Base)提高了5.32%;当神经网络作为基分类器时, 虽然DRCW-OVO取得了最好的平均结果, 但是ND在香气和余味两个指标上优于DRCW-OVO, 另外, DRCW-OVO的平均结果比经典分类器提高了11.13%;当SVM作为基分类器时, 除香气指标外, DRCW-OVO均获得了最好的效果.综上所述, 基于OVO分解策略的多分类方法能够有效提高智能卷烟感官评估中对感官指标的预测效果.
3 结论本文采用了一种基于OVO分解策略的多分类方法对卷烟感官质量进行预测并进行了详细的实验比较.为了验证本文方法的稳定性, 分别以决策树、神经网络和支持向量机作为基分类器进行了实验.分析了4种不同的聚合策略的性能，以及2种冗余分类器处理技术在智能卷烟感官质量预测中的性能.实验结果表明, 无论采用何种基分类器, 与经典分类器应用于预测卷烟感官质量相比, 基于OVO分解策略的多分类技术在智能卷烟感官质量预测中具有明显的优势.并且, 采用冗余分类器处理技术可以进一步提升系统的性能.
参考文献
| [1] | 王强, 李孟军, 陈英武. 卷烟配方数据挖掘技术研究进展[J].中国烟草科学, 2007, 28(4): 14–17. ( Wang Qiang, Li Meng-jun, Chen Ying-wu. Research progress in data mining technology on cigarette formulation[J].Chinese Tobacco Science, 2007, 28(4): 14–17.) |
| [2] | 邵惠芳, 许自成, 李东亮, 等. 基于BP神经网络建立烤烟感官质量的预测模型[J].中国烟草学报, 2011, 17(1): 19–25. ( Shao Hui-fang, Xu Zi-cheng, Li Dong-liang, et al. The establishment of BP neural network based models for predicting tobacco leaf sensory quality[J].Acta Tabacaria Sinica, 2011, 17(1): 19–25.) |
| [3] | 赵青松, 李兴兵, 唐小松. 基于支持向量机的烟叶感官品质评价[J].计算机工程与应用, 2007, 43(10): 236–240. ( Zhao Qing-song, Li Xing-bing, Tang Xiao-song. Tabacum sensory evaluation based on the support vector machine[J].Computer Engineering and Applications, 2007, 43(10): 236–240.DOI:10.3321/j.issn:1002-8331.2007.10.071) |
| [4] | Galar M, Fernández A, Barrenechea E, et al. An overview of ensemble methods for binary classifiers in multi-class problems:experimental study on one-vs-one and one-vs-all schemes[J].Pattern Recognition, 2011, 44(8): 1761–1776.DOI:10.1016/j.patcog.2011.01.017 |
| [5] | Hüllermeier E, Vanderlooy S. Combining predictions in pairwise classification:an optimal adaptive voting strategy and its relation to weighted voting[J].Pattern Recognition, 2010, 43(1): 128–142.DOI:10.1016/j.patcog.2009.06.013 |
| [6] | Huhn J C, Hüllermeier E. FR3:a fuzzy rule learner for inducing reliable classifiers[J].IEEE Transactions on Fuzzy Systems, 2009, 17(1): 138–149.DOI:10.1109/TFUZZ.2008.2005490 |
| [7] | Hüllermeier E, Brinker K. Learning valued preference structures for solving classification problems[J].Fuzzy Sets and Systems, 2008, 159(18): 2337–2352.DOI:10.1016/j.fss.2008.01.021 |
| [8] | Orlovsky S. Decision-making with a fuzzy preference relation[J].Fuzzy Sets and Systems, 1978, 1(1): 155–167. |
| [9] | Fernández A, Calderón M, Barrenechea E, et al. Solving multi-class problems with linguistic fuzzy rule based classification systems based on pairwise learning and preference relations[J].Fuzzy Sets and Systems, 2010, 161(23): 3064–3080.DOI:10.1016/j.fss.2010.05.016 |
| [10] | Galar M, Fernández A, Barrenechea E, et al. Dynamic classifier selection for one-vs-one strategy:avoiding non-competent classifiers[J].Pattern Recognition, 2013, 46(12): 3412–3424.DOI:10.1016/j.patcog.2013.04.018 |
| [11] | Galar M, Fernández A, Barrenechea E, et al. DRCW-OVO:distance-based relative competence weighting combination for one-vs-one strategy in multi-class problems[J].Pattern Recognition, 2015, 48(1): 28–42.DOI:10.1016/j.patcog.2014.07.023 |
