基于候选集的相似度度量的计算

王梦迪　程玉胜

摘 要：关联规则的数据挖掘作为数据挖掘的一种重要模式，已成为目前数据挖掘领域的一个非常重要的研究课题。其中如何度量和寻找有效的候选集一直是众多学者研究的课题之一。本文在置信度及其兴趣度度量的基础上，提出了产生候选集的相似度度量计算方法，并对比了该方法和置信度及其兴趣度之间的联系，并利用相关结论进一步讨论了大数据集环境下如何更加有效地计算相似度的度量计算方法。

关键词：数据挖掘；关联规则；事务间关联规则

中图分类号： TP274 文献标识码： A 文章编号： 1673-1069（2016）12-145-3

0 引言

关联规则的数据挖掘分为事务内关联规则（Intra-Transaction）的数据挖掘和事务间（Inter-Transaction）关联规则的数据挖掘。非经典关联规则挖掘始终会面临所谓的“高阶逻辑”问题。对股价描述，特别是对一些基于（标的股票）价格之上的衍生资产，如期货或期权，这样的表述会更准确些，即在N维空间下（随机过程）的套利测量场。对其直接套用泛Apriori算法是不合适的。

当以基于事务的观点应用滑动窗口技术将股票原始事务数据库D转化为扩展事务数据库De时会大量出现这样一个很有趣（是因为它有别于经典购物篮的高支持度）也很值得注意的现象。因为得到的扩展事务数据库De往往会很大数据集很丰富，但就某只股票在某个时间点上的事件出现频率计数。（例如，如果以一只股票当天收盘价比上一天收盘价超过2%作为一次事件发生记为1否则记为0。那么就在前不久，上证指数从16.01.04开盘的3536.59一路跌到16.01.29收于2737.60。期间共有二十个交易日，1只出现过三次，其他都记为0。支持度为3/20=0.15。韶钢松山从16.01.04开盘价14.28元一路跌到16.01.29的收盘价12.21元。期间共有20个交易日，1出现了5次，其他都记为0。支持度为5/20=0.25。显然，它们的支持度都很低。那么能由此推断出走势背后的资金流没有关联吗？肯定不是，资金流之间的进出绝对是有关联的。这其中暗藏的有趣关联肯定还不少。）与整个扩展事务数据库De数据集相比结果很小甚至小到都可不予考虑即支持度显然很低。然而依“规则的可信度是指包含I1和I2的事务数与包含I1的事务数之比”来看置信度却较高。这其中有许多有趣的关联规则它们支持度很低但置信度却较高，如果一味用传统的挖掘算法会很难发现这些（有趣的）关联规则。

事务间关联规则通常的支持度都较低。在对支持度很低但置信度很高的关联规则进行挖掘时，用最小支持度门槛值的算法显然不够有效。对此本文打算用相似度来衡量事务间可能产生关联规则的项，进而得到事务间关联规则，而且还可用来挖掘感兴趣的事务间多个项间排斥规则。

1 相似关联规则挖掘算法

1.1 兴趣度及其相似度量

复旦大学的施伯乐教授在文献中提出了基于差异思想的兴趣度定义，用以指导关联规则的发现。其定义规则X=>Y的兴趣度为：

这个定义是由关联规则的支持度和可信度而产生的，分母只是个标准化因子，使得| Interest（X=>Y）|<1。根据这个定义，一条关联规则的兴趣度越大于0，说明对这条规则越感兴趣；一条关联规则的兴趣度越小于0，说明对这条规则的反面规则越感兴趣。

可事先由用户指定最小兴趣度阀值minInterest，若Interest（X=>Y）的绝对值越大于minInterest，说明Y的支持度与规则X=>Y的信任度的差异越大，我们说规则X=>Y是新奇的，用户对这些规则越感兴趣；若Interest（X=>Y）的绝对值小于minInterest时，说明Y的支持度与规则X=>Y的信任度差异较小，则可以说规则X=>Y不是新奇的，不会引起用户对该规则感兴趣。

1.2 相似度度量方法

事务间的特征或多或少都会存在一定的相似性，相似性是普遍存在的，其间差别只在相似程度多少而已。具有高支持度的关联规则往往是显然的大家比较熟悉的规则，而相比较而言，低支持度关联规则可能更具新颖性和有趣性。

相似关联规则挖掘的初衷是用置信度度量来替代支持度度量，为了便于运算引入了相似度度量，因为它极好地近似了置信度的概念。对原始数据库利用相似度进行关联规则挖掘，首先需要把原始数据库转换成0/1矩阵。转换方法是：原始数据库的每一项将生成新0/1矩阵的一列；原始数据库的每一个事务将生成新0/1矩阵的一行。如果第i个项在第j个事务中出现，那么这个矩阵的第j行第i列取值为1，反之没有出现就取值为0。

2 基于相似度及其最小哈希变换的候选集挖掘

2.1 基于相似度候选集挖掘

鉴别相似列对的算法包括三个阶段：计算特征标识、产生候选集和对已产生候选集进行剪枝。第一阶段首先是扫描整个数据库进而为每列生成一个小的哈希特征标识。这一步主要是对存放在外存上的大规模数据进行一次概括性的处理以便能把初步处理结果存入内存，好在内存中对其操作。第二阶段，在内存操作中，根据列特征标识生成候选对。最后阶段，再一次扫描原始数据库来决定每一候选对是否确实具有高的相似度。在扫描数据库时，为每个候选列对（Ci，Cj）计算两个计数：一个是在两列中至少有一列中有1的行的个数，即Ci∪Cj，另一个是当两列中同一行都为1的行的数目，即Ci∩Cj。

2.2 基于最小哈希变换的候选集挖掘

先将原始事务数据库转换成扩展了的大事务数据库，再按照扩展项是否出现再转换成0/1数据库M。如果原始数据库有n个事务，m个项，maxspan=w，则M成为了n行，m×w列的0/1矩阵。然后确定要置换变换的k值。k值可根据事务数据库事务总数及对变换后所得矩阵与原始阵的相似度要求来确定。

最小哈希变换的候选集挖掘伪码：

例3：对例2事务数据库（maxspan=3）转换

可见通过哈希法对矩阵M的转化，不仅降低了矩阵的大小，而且很好地保持了原矩阵M的相似度。

3 结束语

相似性研究认为事务间的特征或多或少都会存在一定的相似性，相似性是普遍存在的，其间差别只在相似程度多少而已。这种继承性和相似性反映在以往的数据上可使我们得到很多设计灵感，特征间不同程度的相似性具有重要的启发和借鉴作用。这一观点对海量数据挖掘知识发现尤显重要。本文使用最小哈希方法可减少矩阵的行数，这使运算对象在纵向上数量大量减少，但如果在项数较大的情况下，运算对象在横向上的数量就会大量增加，所占空间也就会相应增大，如考虑把它放入内存恐有困难，这也需要继续研究。

参 考 文 献

[1] JiaWei Han，Micheline Kamber著.范明，孟小峰译.数据挖掘[M].机械工业出版社，2001，第一版，14-18.

[2] 刘绍清.基于频繁项集分类统计的增量式关联规则应用[J].重庆工商大学学报（自然科学版），2015，32（12）：43-47.

[3] 杨国静.基于数据挖掘的高校教学数据分析研究[D].河北师范大学，2015.

[4] Edith Cohen，Mayur Datar，Shinji Fujiwara，etc..Finding Interesting Associations without Support Pruning.IEEE Trans.on Knowledge and Data Eng.，2001，13（1）：64-77.

[5] Anthony K.H. Tung， Hongjun Lu，Jiawei Han，etc..Efficient Mining of Intertrsaction Association Rules. IEEE Trans. on Knowledge and Data Eng.2003，15（1），43.

[6] 陈永峰.大数据背景下数据挖掘在高校固定资产统计中的应用研究[J].河北软件职业技术学院学报，2015（2）：6-9.

[7] 李勇，陈新华，朱建平，等.第七届国际数据挖掘与应用统计研究会学术综述[J].统计与信息论坛，2015（10）：111-111.

[8] J.Hna，J.Pei.Mining Frequent Patterns Without Candidate Generation. In Proc.2000 ACM-SIGMOD Intl. Contf.on Management of Data（SIGMOD′2000）Dallas TX 2000，1-12.

[9] 陈艳，褚光磊.关联规则挖掘算法在股票预测中的应用研究——基于遗传网络规划的方法[J].管理现代化，2014，34（3）：13-15，39.

[10] 陈健.人工神经网络模型在股票价格预测问题中的实证研究[D].南开大学，2014.

[11] 褚光磊.进化算法在数据挖掘与金融工程中的应用研究[D].上海财经大学，2014.

[12] 张筱梅，朱家明.基于Pearson相关系数模型对股票间相关性研究[J].赤峰学院学报（自然科学版），2015（10）：32-33.