模糊关联规则挖掘
关联规则挖掘是数据挖掘最基本和最常用的算法之一,Apriori算法基本上是每个学习数据挖掘的同学掌握的第一个算法。但是,一般的关联规则挖掘算法无法处理涉及连续值的记录。 虽然某些算法把连续值通过划分区间的方法离散化,但是这种硬边界划分的方法效果并不是很好,一些在边缘附近的数据只能属于一个划分,而这与事实不符。比如,年龄的一个划分可以是青年,但如果我们把青年的区间定义为[20,30],则19岁的人就被排除在青年的范围之外了,显然这不是很合适。针对这种问题,我们可以基于模糊集把区间划分成多个模糊集,然后求得某个元素属于某个模糊集的概率(根据模糊隶属函数),这样的话每个元素都可以属于多个不同的模糊集,而不是只属于一个集合。划分模糊集的常用算法是FCM,见参考文献。
当我们给定了所有连续值属性的模糊集划分之后,下一步就是进行关联规则的挖掘了,我们定义问题如下:
T={t 1 ,t 2 ,...,t n }是数据集
I={i 1 ,i 2 ,...,i m }是属性集,我们假定所有的属性都是数值型。
F ik ={f ik 1 ,f ik 2 ,...,f ik l }代表第ik个属性的模糊集。
我们要挖掘的模糊关联规则的形式为:
If X is A then Y is B.
其中,X和Y是属性,A和B是X,Y对应的模糊集中的某个划分,比如:
X为年龄,其对应的模糊集为{婴儿,幼儿,少年,青年,壮年,老年},A为青年,Y为薪水,其对应的模糊集为{低薪,中薪,高薪},B为高薪。
模糊关联规则挖掘的过程为:
1. 计算significance factor
对于每个属性X与X属性对应的模糊集的划分的属性-划分对<X,A>,比如<年龄,青年>,计算其significance系数:
其中
m aj 是用FCM算法已经算好的模糊隶属函数的值,只有当其大于阀值w时,我们才会取其值,否则只取0.
2. 计算certainty factor
对于第一步求得的所有的significance系数大于给定值的<Z,C>对,我们计算所有属性-划分对:<X,A>,<Y,B>的certainty系数:
求得的certainty系数大于给定值的<X,A>,<Y,B>就是我们要挖掘的关联规则:
If X is A then Y is B.
参考文献:
[1] Chan Man Kuok, Ada Fu, Man Hon Wong. Mining Fuzzy Association Rules in Databases.
[2] FCM聚类算法简介