2016, Vol. 37
2.浙江大学 计算机科学与技术学院, 浙江 杭州 310058
2.College of Computer Science and Technology, Zhejiang University, Hangzhou 310058, China
数据挖掘是知识发现的一种手段，能够从大量数据中抽取隐含的、先前未知的、对决策有潜在价值的规则[1].数据分类和聚类均是数据挖掘的主要研究内容之一.前者主要是通过分析训练数据样本，构造一个分类模型，能够把新采集的数据映射到给定类别中的某一个.后者则是按照相似程度把大量的数据样本聚成几个类，使得同一类内样本的相似性较大，而不同类间样本的相似性较小.无论是分类所使用的训练数据集，还是聚类的结果数据集，它们所包含的每个元组都具有类标，即属于某一个类别，称此类数据集为类标数据集.针对类标数据集，如何建立一种知识模型，并设计其对应的挖掘方法，能够准确地反映各类标区别于其他类标的本质特征，帮助领域专家更好地认识各个类标，即类标特征分析将成为数据挖掘领域一个有实际应用需求和价值的问题.
以分类为例，应用不同的分类模型，比如决策树模型[2]、贝叶斯模型[3]、基于规则的模型[4]、神经网络模型[5]、K-近邻模型[6]和关联分类模型[7-8]等可以对类标数据集进行较高效、较准确地分类.然而，这些模型并不以各类标的解释和帮助领域专家对各类标的认知为目标，甚至建立的某些种类的分类模型很难被专家理解.以聚类为例，其是一种在没有预先指定类别的前提下，用“物以类聚”的思想来分析数据的常用方法.然而聚类所产生的结果--类标数据集的可解释性是聚类分析方法在应用层面上取得成功的关键.只有领域专家充分理解聚出来的各个类标，才能更好地应用该类知识进行给定领域的分析.现有的聚类模型有很多[9-12]，但缺乏对聚类知识描述和聚类结果解释的研究.因而，无论是针对分类的训练集、还是聚类的结果集或者其他类型的类标数据集，类标特征分析将促进相关知识模型在各领域的应用，成为一项有价值的数据分析方法，但现在尚缺乏针对性研究.
为了增强类标数据集面向领域专家的可解释性，本文从统计学角度提出一种面向主属性值的类标特征分析方法.主属性值即为一个类标区别于其他类标出现的主要属性值，它反映了同一类标内数据的同质性和类标间数据的差异性，同时考虑了所建模型的鲁棒性.本文方法的大致过程包括：给出主属性值的定义，并建立面向主属性值的类标特征模型；设计面向主属性值的类标特征抽取算法；将建立的类标特征模型应用于分类，给出一种基于主属性值的数据分类方法.主属性值直观地表述了各类标数据的特征，便于领域专家理解，是一种简单有效的类标特征分析方法.另外，将面向主属性值的类标特征应用于分类中，发现针对类标较少的数据集，可以提升分类准确率，可为以后分类研究提供新的思路.
1 面向主属性值的类标特征建模本文以增强类标数据集的可解释性为目标，建立了一种面向主属性值的类标特征模型.下面给出相关定义.
设D是一个类标数据集，具有类标号属性C={c1, c2, …, ck}，即有k个类标号.给定D的某一特征属性A={a1, a2, …, al}，属性值v是一个值对，即为属性A及在该属性上的取值ap(1≤p≤l)的组合，记作
定义1 覆盖度(coverage, 简记为cov)：给定一类标数据集D，则属性值v在数据集D上针对类标cq(1≤q≤k)的覆盖度为
|
(1) |
其中：P(v∪cq)和P(cq)分别为v∪cq和cq在D上出现的概率；|v∪cq|和|cq|分别为v∪cq和cq在D上出现的次数.由定义可知，cov (v, cq)∈[0, 1]，描述了属性值v在类标为cq样本中的覆盖程度.给定最小覆盖度阈值min_cov，如果cov (v, cq)≥min_cov，则称v为D中针对类标cq的频繁属性值.
定义2 特异度(specificity, 简称spec)：给定一类标数据集D，则属性值
|
(2) |
其中：
定义3 主属性值(primary value, 简记为pv)：给定类标数据集D，类标cq及属性值v，如果v在D中针对类标cq既是频繁属性值，又是特异属性值，则称属性值v为D中类标cq的一个主属性值.
从直观上理解，一个类标的主属性值就是在该类标中频繁出现、而在其他类标中出现较少的属性值.根据类标数据集中的数据分布情况和阈值设定的大小，一个类标cq在给定特征属性A上可能有零到多个主属性值，由这些所有的主属性值组成的集合SApv称之为类标cq在特征属性A上的主属性值全集.
定义4 类标特征(class label characteristic, 简记为lc)：给定类标数据集D，其由m个特征属性{A1, A2, …, Am}和一个类标号属性C={c1, c2, …, ck }描述，cq(1≤q≤k)是D中的某个类标.则定义cq的类标特征：
以上所建立的面向主属性值的类标特征模型将各个特征属性独立考虑，主要有两个出发点：一是在实际应用中，特别是针对大数据环境，类标数据集所包含的各特征属性可能有不同的数据来源和存储方式，将各特征属性分开处理可以提升类标特征分析的效率和可行性；二是该模型较为直观，便于领域专家理解和对相关知识模型的应用.
2 面向主属性值的类标特征抽取本文所设计的类标特征抽取算法的大致思路如下.
1) 扫描类标数据集D一次，统计各特征属性Ai(1≤i≤m)的所有属性值在各类标cq(1≤q≤k)中出现的频率，得数据集D的属性值类标分布矩阵M.
2) 基于矩阵M，针对各类标cq，计算各属性值v在cq中的覆盖度，筛选大于最小覆盖度阈值min_cov的各项，得各类标的频繁属性值集.
3) 基于矩阵M，针对各类标cq所对应的频繁属性值集中的各项，计算其特异度，筛选其中大于最小特异度阈值min_spec的各项，即可得到各类标的主属性值集Spv.
本文面向主属性值的类标特征抽取算法(primary value objected class label characteristic extraction algorithm, PVOCLCE)具体描述如下.
算法1 PVOCLCE
输入 类标数据集D，最小覆盖度阈值min_cov，最小特异度阈值min_spec
输出 各类标的主属性值集Spv
Count[k+1]=Initiate (); //将D的元组总数及各类标个数写入数组Count中
M[k][n]=Initiate (); //初始化存放各属性值在各类标出现频数的矩阵M
FOR (tj∈D) //对于D中的任一元组tj
FOR (v∈tj) //对于tj所包含的任一属性值v
Count[q][v]++; //tj所对应的类标为cq
FOR (cq∈C) //对于任一类标cq
FOR (v∈D) //对于任一属性值v
IF (cov (v, cq)≥min_cov) // cov (v, cq)为属性值v在类标cq中的覆盖度
Sq=Insert (v); //Sq为类标cq所对应的全局频繁属性值集
FOR (cq∈C)
FOR (v∈Sq)
IF (spec (v, cq) < min_spec)//spec (v, cq)为值v在类标cq中的特异度
Sq=Sq-v;
RETURNSpv=∪qSq;
以上描述了在类标数据集D中抽取类标特征的算法PVOCLCE.设D中属性值个数为m，元组个数为n，则算法PVOCLCE的时间复杂度为O(m×n).因为m一般数值较小，且该算法仅需扫描一遍数据库即可求解，因而有着较高的运行效率和可伸缩性.
3 面向主属性值的类标特征分类基于上节所抽取的面向主属性值的类标特征，可以构建一类面向主属性值的类标特征分类方法.此类方法的大致思路比较简单，即分析新采集的未知类标的数据中包含的主要是哪个类标的主属性值，就应该属于该类标.本文所设计的面向主属性值的类标特征分类算法(primary value objected class label characteristic classification algorithm, PVOCLCC)的具体思路如下.
1) 扫描抽取出的类标数据集中各类标的类标特征，提取待分类元组t所包含的各类标cq的主属性值集Sq={pv1, pv2, …, pvx}.
2) 依次基于以下规则来判断新元组t所属的类标.
2.1) 如果存在类标cq∈C(1≤q≤k)，使得元组t所包含cq的主属性值个数大于其他类标，则t的类标为cq.
2.2) 如果存在类标cq∈C(1≤q≤k)，使得元组t对cq的归属度最大，则t的类标为cq.其中，归属度定义为
|
(3) |
式中，n为类标数据集中的样本总数.当Sq=
2.3) 如果存在类标cq∈C(1≤q≤k)，使得元组t到达类标cq的欧几里得距离最小，则t的类标为cq.
以上大致描述了本文面向主属性值的类标特征分类算法PVOCLCC的思路.因为算法过程较简单，这里不再详细展开.
4 实验实验将着重从以下2个方面分析文中方法的有效性.一是分析所建立的类标特征模型中两个重要阈值--最小覆盖度和最小特异度对类标主属性值个数的影响；二是分析所提出的面向主属性值的类标特征分类方法的性能.
4.1 阈值对类标主属性值个数的影响最小覆盖度和最小特异度是本文所建立的类标特征模型中2个重要阈值，也是模型的核心，因而实验首先探索这两个阈值对主属性值个数的影响.为了阐述实验结果，定义numavg为一个类标数据集所属各类标的主属性值个数的平均值.实验时采用4个典型的UCI数据集letter-recognition，glass，iris和wine进行分析.
1) 最小覆盖度阈值对主属性值个数的影响：设定最小特异度阈值min_spec=0，图 1给出了各数据集的numavg值随最小覆盖度阈值min_cov的变化趋势.
|
图 1 最小覆盖度阈值对主属性值个数的影响 Fig.1 Influence of minimum coverage threshold on number of primary values |
由图 1可知，随着min_cov的增大，各数据集的numavg值均逐渐减少.当min_cov依次取值0.2，0.3，0.4，0.5和0.6时，这4个数据集的numavg值分别为18.25，12.25，8.75，6.5和3.5.而当min_cov的值增加到0.9和0.99，平均主属性值个数则降到0.5和0.
因为该实验分析时设定min_spec=0，所以实际上统计出来的是各数据集在各类标上的平均频繁属性值个数.最终产生的主属性值个数要比图 1中的数据小，因为还需要满足最小特异度阈值.在设定min_cov时，不宜将其设置过小而违背主属性值的语义，同时也不宜将其设置过大而导致抽取出的主属性值个数太少.由图 1中4个数据集的结果可以看出，min_cov设定值不宜超过0.6.
2) 最小特异度阈值对主属性值个数的影响：当min_cov分别取值为0.0，0.4，0.5和0.55时，各数据集的numavg值随最小特异度阈值min_spec的变化曲线如图 2所示.
|
图 2 最小特异度阈值对主属性值个数的影响 Fig.2 Influence of minimum specificity threshold on number of primary values (a)-min_cov=0；(b)-min_cov=0.4; (c)-min_cov=0.5；(d)-min_cov=0.55. |
由图 2可知，对于大多数类标数据集，最小覆盖度阈值设定在0.2至0.5之间较为合理.而最小特异度阈值设定时应满足min_spec+min_cov>1的条件，一般在0.7至0.95的区间较为合理.在设定阈值时，为了使抽取出的主属性值个数合理，当min_cov较小时，min_spec需适度增大；而当min_cov较大时，min_spec可适度减小.
4.2 算法PVOCLCC的分类性能主要测试算法PVOCLCC的分类准确率，并与经典分类算法进行对比分析.表 1分别列出了本文分类算法PVOCLCC和C4.5，CBA[7]，CMAR[8]这三个经典分类算法在各UCI数据集上的分类准确率.
|
表 1 分类准确率比较 Table 1 Comparison of classification accuracy |
由表 1可知，本文面向主属性值的类标特征分类算法PVOCLCC虽然模型简单，但与经典决策树分类算法C4.5及经典关联分类算法CBA和CMAR相比，在以上10个数据集中，7个分类准确率最优，2个最差.由该实验可知，本文所给出的面向主属性值的分类算法PVOCLCC在针对类标较少的数据集时有较高的分类准确率.
5 结论1) 针对类标数据集，提出了有着广泛应用背景的类标特征分析问题，可为以后此类研究提供原型参考.
2) 建立了面向主属性值的类标特征模型，能够直观、有效地描述类标数据集中的各个类标的特征，增强类标数据集的可解释性.
3) 设计了一种面向主属性值的类标特征抽取算法PVOCLCE，有着较高的执行性能和可伸缩性，能够针对大多数类标数据集有效地抽取各类标的特征.
4) 提出了一种基于类标特征分析的面向主属性值的分类算法PVOCLCC，其有着较高的分类准确率，是一类值得深入研究的分类方法.
| [1] | Khamisi K, Kazuto S, Hideyuki T, et al. Four decades of data mining in network and systems management[J]. IEEE Transactions on Knowledge and Data Engineering , 2015, 27 (10) : 2700–2716. DOI:10.1109/TKDE.2015.2426713 |
| [2] | Prabhu Y, Varma M.FastXML:a fast, accurate and stable tree-classifier for eXtreme multi-label learning[C]//ACM SIGKDD Conference on Knowledge Discovery and Data Mining.New York:ACM, 2014:263-272. |
| [3] | Bi W, Kwok J T. Bayes-optimal hierarchical multilabel classification[J]. IEEE Transactions on Knowledge and Data Engineering , 2015, 27 (11) : 2907–2918. DOI:10.1109/TKDE.2015.2441707 |
| [4] | Wang J Y, Karypis G. On mining instance-centric classification rules[J]. IEEE Transactions on Knowledge and Data Engineering , 2006, 18 (8) : 1497–1511. |
| [5] | Tian J, Li M, Chen F. Learning subspace-based RBFNN using coevolutionary algorithm for complex classification tasks[J]. IEEE Transactions on Neural Networks and Learning Systems , 2016, 27 (1) : 47–61. DOI:10.1109/TNNLS.2015.2411615 |
| [6] | Samanthula B K, Elmehdwi Y, Jiang W. K-nearest neighbor classification over semantically secure encrypted relational data[J]. IEEE Transactions on Knowledge and Data Engineering , 2015, 27 (6) : 1261–1273. |
| [7] | Liu B, Hsu W, Ma Y.Integrating classification and association rule mining[C]//ACM SIGKDD Conference on Knowledge Discovery and Data Mining.New York:ACM, 1998:80-86. |
| [8] | Li W M, Han J W, Pei J.CMAR:accurate and efficient classification based on multiple class-association rules[C]//IEEE International Conference on Data Mining.Piscataway:IEEE, 2001:369-376. http://www.sciencedirect.com/science/article/pii/S0925231215009844 |
| [9] |
张明卫, 刘莹, 张斌, 等.
一种基于概念的数据聚类模型[J]. 软件学报 , 2009, 20 (9) : 2387–2396.
( Zhang Ming-wei, Liu Ying, Zhang Bin, et al. Concept based data clustering model[J]. Journal of Software , 2009, 20 (9) : 2387–2396. DOI:10.3724/SP.J.1001.2009.03412 ) |
| [10] | Hou Y, Whang J J, Gleich D F, et al.Non-exhaustive, overlapping clustering via low-rank semidefinite programming[C]//ACM SIGKDD Conference on Knowledge Discovery and Data Mining.New York:ACM, 2015:427-436. http://dl.acm.org/citation.cfm?id=2783398 |
| [11] | Mashayekhi H, Habibi J, Khalafbeigi T, et al. GDCluster:a general decentralized clustering algorithm[J]. IEEE Transactions on Knowledge and Data Engineering , 2015, 27 (7) : 1892–1905. DOI:10.1109/TKDE.2015.2391123 |
| [12] | Liu H, Liu T, Wu J, et al.Spectral ensemble clustering[C]//ACM SIGKDD Conference on Knowledge Discovery and Data Mining.New York:ACM, 2015:715-724. http://dl.acm.org/citation.cfm?id=2783287 |