设为首页
加入收藏
期刊导航
网站地图
首页
期刊
数学与物理
地球与环境
信息通讯
经济与管理
生命科学
工程技术
医药卫生
人文社科
化学与材料
会议
合作
新闻
我们
招聘
千人智库
我要投搞
办刊
期刊菜单
●领域
●编委
●投稿须知
●最新文章
●检索
●投稿
文章导航
●Abstract
●Full-Text PDF
●Full-Text HTML
●Full-Text ePUB
●Linked References
●How to Cite this Article
Hans Journal of Data Mining
数据挖掘
, 2012, 2, 33-37
http://dx.doi.org/10.12677/hjdm.2012.24007
Published Online October 2012 (http://www.hanspub.org/journal/hjdm.html)
Research on Associative Classification Method Based on
Threshold Adaptive Technology
*
Wei Ta ng, Jingxue Liu
PLA Academy of National Defence Information, Wuhan
Email: ljx_62@sohu.com
Received: Jul. 26
th
, 2012; revised: Aug. 10
th
, 2012; accepted: Aug. 24
th
, 2012
Abstract:
Based on the mechanism of evaluation feedback and control, this paper researches for adaptive adjustment of
setting threshold of associative classifica
tion method. Firstly, the mathematical model of evaluating the set that consist
of classification rules is established. Then, based on this m odel, a method that uses the interval iterative approximation
for getting the approximate optimal solution of associative classification minimum support in order to achieve the
adaptive threshold settings is put forward. Finally, the simulation experiment shows that the method has better
adaptability and effectiveness comparing with some general ones.
Keywords:
Self
-
Adaptive; Associative Classification; Rule Extraction; Class Being Distinguished
阈值自适应关联分类方法研究
*
汤
伟
,刘敬学
国防信息学院,武汉
Email: ljx_62@sohu.com
收稿日期:
2012
年
7
月
26
日;修回日期:
2012
年
8
月
10
日;录用日期:
2012
年
8
月
24
日
摘
要:
本文采用评估反馈控制机制,对关联分类方法的阈值设定自适应调节进行了研究。首先建立了对分类
规则集进行判优评估的数学模型;然后基于此模型提出了运用区间迭代逼近求解关联分类最小支持度,并以此
进行阈值自适应调节的方法;最后的仿真实验表明,该方法比一般的关联分类方法具有更好的自适应性和有效
性。
关键词:
自适应;关联分类;规则提取;类型判别
1.
引言
基于关联规则挖掘
(Frequent Pattern Mining)
的分
类方法称为关联分类
(Associative Classification)
[1]
,用
于基于带类标记的训练数据集进行分析,而不是传统
的事务数据集,规则应用的重点也由原来的提取知识
变为对新数据的分类和趋势预测。而用于关联分类的
训练数据集具有两类不同属性
[2]
,一类是组成分类规
则前件
(
条件
)
的条件属性,记为
A
1
,
A
2
,...,
A
n
,另一类是
组成后件
(
结论
)
的决策属性,记为
C
1
,
C
2
,...,
C
m
。决策
属性的值预先标记多属性目标的类别,类别的标记可
由多个决策属性联合标记来完成。
关联分类主要应用于类型判别系统
DS
= (
A
∪
C
,
R
,
M
)
,其中
R
为分类规则集,
M
为分类器的构建方
法。实际应用中,系统利用分类器对测试数据进行类
型判别,判别的准确率依赖于
R
的可靠度和
M
的优
劣。传统的关联分类采用经验知识或人工尝试的办法
来寻找合适的支持度和置信度阈值,明显存在效率不
高、智能性不强的问题。为了提高分类规则的可靠性,
*
资助信息:
本研究课题受到国家自然科学基金(70903026)资助。
Copyright © 2012 Hanspub
33
阈值自适应关联分类方法研究
本文基于分类规则集的综合评估指标值智能调节自
身阈值设定的反馈自适应控制机制,探讨对关联分类
方法的阈值设定进行自适应调节的改进和具体实现
方法,以提高分类决策的智能性与精准度,降低其对
噪声数据和孤立点的敏感性。
在本文第
2
部分,对建立分类规则集判优评估的
数学模型进行了阐述;在第
3
部分,先分析了阈值自
适应关联分类方法实现的基本思路,然后基于判优评
估模型提出了区间迭代逼近求解关联分类最小支持
度阈值的方法,从而实现了阈值的自适应调节;在第
4
部分,通过仿真实验,验证了阈值自适应关联分类
方法的智能性和有效性。
2.
分类规则集判优评估模型的建立
关联分类挖掘的数据集属性值如果是连续的,须
先对其进行离散化处理,设
v
表示某个属性值处理后
的单个取值或离散区间的标号,先对数据集条件属性
值标签化处理,转换为关联挖掘的一个项
p
,
p =
(
A
i
,
v
)
,再将决策属性
C
1
,
C
2
,...,
C
m
联合成分类属性
A
class
,记
C
为其标识的一个类,则分类规则
r
表示
为如下形式的蕴含式
[1]
:
1 2class
..., 1
l
ppp ACln
(1)
关联分类的主要任务是运用关联挖掘算法挖掘
形如式
(1)
的分类规则,其实质是一类特殊的频繁项集
(Frequent Item Set)
,可采用剪枝的方法和预设阈值产
生强规则,最后对规则进行粗处理得出分类规则集。
将训练数据集分割为基本训练集和测试训练集
两个部分,基本训练集用来挖掘分类规则,测试训练
集用来测试评估分类规则的优劣,以进行阈值的反馈
控制调节。
可以对训练数据集采用一次划分或
k-
折划分的方
法。在一次划分法中,训练数据集按比例划分成两部
分,测试训练集的综合测试评估指标值
Z
作为目标函
数;在
k-
折划分法中,训练数据集被划分成大小大致
相等的
k
个互不相交的子集
S
1
,
S
2
,...,
S
k
,(
k
≥
2)
,训练进
行
k
次,在第
i
次训练中,
S
i
用作测试训练集,其余
子集的集合用作基本训练集,设最小支持度阈值为
ms
,最小置信度阈值为
mc
,第
i
次测试训练的评估指
标值为
Z
i
,则综合判优评估指标
Z
(
ms
,
mc
)
用算术平均
法求得,即:
1
,,
k
i
i
ZmsmcZ kk
1
(2)
其中,
k
表示划分的折数,一般建议使用
10-
折划分,
因为它具有相对低的偏置和方差,特别地,当
k
= 1
时,表示使用的是一次划分法。
考虑到数据的多样化和对象并不都是唯一可分
类的,采用对规则评判而不是对数据测试的评判更具
有合理性。把基于设定的最小阈值训练产生的一组强
关联分类规则记为
12
,,...,
m
Rrr r
,
r
i
的支持度和置
信度分别记为
s
i
和
c
i
。
对规则
r
i
进行测试,记该规则的判别前件为
A
(
r
i
)
,
判别类型为
C
(
r
i
)
,
满足规则前件和结论的数据记录个数
分别为
N
(
A
(
r
i
))
和
N
(
C
(
r
i
))
,
测试数据集总的记录数为
N
。
测试准确率表示为
n
i
=
L
i
/
P
i
,其中
n
i
为准确率,
L
i
为判别
正确的记录数,
P
i
为满足规则前件的数据记录数;测试
误检率表示为
f
i
=
M
i
/
N
i
,其中
f
i
为误检率,
M
i
为判断错
误的记录数,
N
i
为非
C
(
r
i
)
类型的数据记录数。以这四项
指标作为规则集的评判属性,得决策矩阵:
1111
2222
mmmm
s
cn f
s
cn f
s
cn f
D
(3)
对规则的测试而言,
s
i
、
c
i
、
n
i
要求越高越好,而
f
i
要求越低越好,运用乘除法综合式
(3)
中的效益型和
成本型属性,得评估规则测试指标
T
i
:
11
ii
iiiii
ii
iii i
ii
LM
Tcnf c
PN
cL NCrM
NArNCr
(4)
其中
ii
NCrN NCr
。
置信度高的规则具有更高的可靠性,在规则集综
合评估中的权重也应该越大,故可以运用简单加权平
均方法进行评估,它是一种非等权平均方法。按置信
度大小对规则进行排序得到新的决策矩阵
D
,使得
s
1
≤
s
2
≤
≤
s
m
,令新规则序列中
r
j
的权系数
w
j
为:
1
2
1
j
m
j
jj
w
mm
j
(5)
Cop
yright © 2012 Hanspub
34
阈值自适应关联分类方法研究
记规则集的所有判别条件的集合为
rR
A
r
,其
覆盖度定义为
rR
NAr
N
;当规则集为空时,其
覆盖度为零。综合加权测试指标与覆盖度指标,可得
第
i
次测试训练的评估指标
Z
i
:
1
m
ijj
rR
j
Z
wTNArN
(6)
将式
(2)
与式
(6)
合并,得到规则集的综合判优评估
模型为:
11
max,
km
jj
rR
ij
wTN Ar
Zmsmc
kN
(7)
ms
用于筛选出关联度强的规则。
ms
过高会导致得
出的分类规则集不能完整描述各类别的推理特征;
ms
过低会导致得到一些可靠性较低的规则,误导判别结
果,也会使得出的规则过于繁杂。而
mc
用于筛选出
可信度高的规则,越高则基于准确率和误检率的综合
判优评估指标值会越高,但片面地要求较高的指标值
会导致得出的规则集数目过少,有用
的规则被剪枝。
因此,在实际应用中,可先确定
mc
的初值,以
求出最优的支持度阈值解,在此基础上给出
mc
的推
荐取值,最后由决策者根据实际要求确定
mc
的取值。
此外,分类规则集应能涵盖至少一种类别的特
征,
ms
需小于最大数目类别所占总数的比例,设为
p
%(0 <
p
< 100)
,训练样本总数设为
N
,将式
(4)
,式
(5)
代入模型
(7)
,修正并化简为:
11
2
max
1
00.01
.. (8)
1
km
jjjj
rR
ij
jj
jc LNCrMNAr
Z
mmkNArNCrN
ms p
st
kN
这样,原问题转换为求解一个最优的最小支持度阈值
解
ms
*
,使得
Z
(
ms
)
达到最大。
3.
阈值自适应关联分类方法的实现
3.1.
基本思路
阈值自适应关联分类方法的实现主要是根据所
得分类规则集的评估指标值智能调节阈值,包括对训
练数据属性值进行预处理、基于评估反馈控制机制求
出的最小支持度阈值产生分类规则、基于已产生的分
类规则构建分类器、利用分类器判别目标类型等步骤
[6]
。具体实现流程如图
1
所示。
3.2.
评估反馈控制的区间迭代逼近算法
为了能求解出式
(8)
的近似最优解,本文采用一种
基于评估反馈控制的区间迭代逼近求解方法。该算法
设置区间迭代指数为一个大于
1
的正整数
e
,
ms
的取
值区间为
(
a
,
b
]
;具体步骤如下:
Step1
输入训练数据集
S
,最小置信度阈值
mc
,
区间迭代指数
e
;将训练数据集按某种划分方法进行
划分。
Step2
将
ms
的取值区间划分为连续等长的
e
个子
区间
(
a
i
-1
,
a
i
]
,
(
i
=1,2,...,
e
)
,取各子区间的中点
(
a
i
-1
+
a
i
)/2
,
设为
b
i
。
Step3
分别取
ms
=
b
i
对数据集进行基本训练和测
试训练,得综合判优评估指标值序列
(
Z
(
b
1
),
Z
(
b
2
),
,
Z
(
b
e
))
。
Step4
找出最大的评估指标值
max
Z
,对应的
ms
值为
b
j
。
Step5
若
j
= 1
或
j
=
e
,将
ms
的取值区间分别缩
小为
[
a
,
b
2
]
和
[
b
e
-1
,
b
]
;否则将取值区间缩小为
[
b
j
-1
,
b
j
+1
]
。
Step6
转
Step2
,直到准则函数
2
11
-
ee
ij
ij
EZbZbe
收敛,得近似最优解
ms
*
=(
a
+
b
)/2
。
Figure 1. flow chart of associative classification based on
self-adaptive threshold
图
1.
阈值自适应关联分类方法实现流程图
Cop
yright © 2012 Hanspub
35
阈值自适应关联分类方法研究
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
1. 1
0.01
0.03
0.05
0.07
0.09
0.11
0.13
0.15
0.17
0.19
0.21
0.23
0.25
0.27
0.29
0.31
0.33
0.35
0.37
ms
Z(ms)
Acute Inflammations
ms=85%
Hayes-Rot h m s =8 0%
Iris ms= 85%
Step7
输出近似最优解
ms
*
和分类规则集。
从第
2
部分建立的模型来看,支持度阈值越偏离
某一理想小区间,评估值越低,且呈现先单调递增后
递减的特点;因此,上述算法是一个能收敛到最优解
的逼近算法,其收敛速度与
e
等迭代指数密切相关。
在求解出
ms
*
的基础上,决策者再根据具体要求
调整
mc
,以使得出的分类规则集达到最可靠状态。但
最终判别目标类别还依赖于采用具体的方法构建分
类器。
4.
仿真实验
对阈值自适应关联分类方法的仿真实验,基
于
.NET
平台架构,采用算法
Apriori
[4]
作为关联规则的
挖掘算法,分别选用文献
[5]
中的 三个数据集进行 实
验。数据集的描述如表
1
所示。
对这三个数据集,采用一次划分法进行分割,区
间迭代指数取值
e
= 16
。按照阈值自适应区间迭代逼
近求解方法,求解过程分别迭代了
{7,7,6}
次,求得最
小支持度近似最优解
ms
*
≈
{11.25%,7.58%,0.67%}
。
在初始取值区间
{(0,0.3375)
,
(0,0.3864)
,
(0,0.3333) }
之间选取
{33, 38 ,3 3 }
个阈值采样点,这些采
样点与综合判优评估指标
Z
值的关系如图
2
所示。
对关联分析产生的分类规则采用启发式方法构
建分类器,并测试其对目标类型判别的正确率,测试
结果与文献
[6]
中提出的基于排序的关联分类算法作
了比较,具体如表
2
所示。
通过以上两种方法分别对三类数据集的测试、分
析和比较实验表明,由本文提出的逼近算法求得的近
似最优解构建的分类器有较高的测试正确率,能分析
出最为有效的分类规则,且计算程序的运行过程和输
出结果进一步验证了区间迭代逼近求解方法的可行
性,进而验证了阈值自适应关联分类方法的智能性和
可靠性,仿真结果与理论分析相一致。
Table 1. Description of the data set
表
1.
数据集描述
数据集
记录数
条件属性
个数
决策属
性个数
类别数目
属性值中是否
有缺省值
Acute
Inflammations
120 6 2 4
否
Hayes-Roth 160 3
1 3
否
Iris 150 4 1 3
否
Figure 2. Relation chart of the threshold’s sample points
corresponding to the values of synthetically evaluating
图
2.
阈值采样点与综合判优评估指标值对应关系图
Table 2. Test result’s contrasts of the two kinds of associative
classification method
表2. 两种关联分类方法测试结果对比
分类方法 测试数据集
支持度
阈值
分类规则
数目
测试
数据数目
测试
正确率
Acute
Inflammations
20% 28 120 84.17%
Hayes-Roth 5% 15 80 91.25%
基于排序
的关联分
类方法
Iris 3% 75 150 94.67%
Acute
Inflammations
11.25% 136 120 100%
Hayes-Roth 7.58% 9 80 91.25%
阈值自适
应关联分
类方法
Iris 0.67% 140 150 96%
5.
结束语
本文针对一般关联分类方法存在的依赖先验知
识和智能性不强、准确度不够高等缺陷,提出并实现
了基于评估反馈控制机制的阈值自适应关联分类方
法,并选用三个数据集进行了仿真实验,仿真结果与
理论分析相一致,验证了该方法比一般关联分类方法
有更好的自适应性和有效性。该方法在目标类型识别
中具有较高的应用价值,可辅助提高决策的准确率和
对先验知识的利用率。下一步值得深入研究的问题
有:一是随着属性数和数据量的增大,如何提高算法
的效率;二是在判优评估模型中,综合考虑速度、鲁
棒性、可规模性和可解释性等指标的度量,进一步提
升其应用价值。
6.
致谢
本文得到了国家自然科学基金
(7 090 3026)
的资助
和国防信息学院的支持。
参考文献
(References)
[1]
J. W. Han, M. Kamber. Data mining concepts and techniques.
Cop
yright © 2012 Hanspub
36
阈值自适应关联分类方法研究
Copyright © 2012 Hanspub
37
2nd Edition,
北京
:
机械工业出版社
, 2006: 344-345.
[2]
丛蓉
.
作战指挥决策支持系统目标融合识别研究
[D].
大连理
工大学
, 2010: 93-98.
[3]
晁玉宁
,
许孝元
.
基于关联规则的分类模型系统
[J].
计算机
工程与应用
, 2009, 7: 80-83.
[4]
H. Wu, Z. G. Lu, L. Pan, et al. An improved apriori-based algo-
rithm for association rules mining. Sixth International Confer-
ence on Fuzzy Systems and Knowledge Discovery, 2009: 51-55.
[5]
D. Aha, Fellow Graduate Students. UCI machine learning
repository. Irvine: University of California.
http://archive.ics.uci.edu/ml/datasets.html
[6]
朱晓燕
,
宋擒豹
.
基于排序的关联分类算法
[J].
计算机科学
,
2009, 36(7): 204-207.