基于关联规则的数据挖掘算法的分析及应用

方 蓉(惠州市广播电视大学，广东惠州,516007)



基于关联规则的数据挖掘算法的分析及应用

方 蓉
(惠州市广播电视大学，广东惠州,516007)

摘要：数据挖掘就是从大量的数据中挖掘出有用的信息。数据挖掘与传统的数据分析的本质区别是数据挖掘是在没有明确假设的前提下去挖掘信息、发现知识。文章分析了数据挖掘算法的关联规则特性，对其在股票市场中的应用进行了重点，以便更好的应用在更多的领域。

关键词：关联规则；数据挖掘算法；股票

1　关联规则

1.1关联规则概述

数据关联是数据库中存在的一类重要的可被发现的知识。如果两个或多个变量的取值之间存在某种规律性，就称为关联。关联分析的目的是找出数据库中隐藏的关联网，关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。近些年来，很多业界人士对关联规则挖掘进行了详细的探讨，关联规则挖掘已经成为数据挖掘中的一个非常重要的课题。

关联规则概念是Agrawal等人在1993年首先提出的，与此同时还给出了一种性能相对较差的挖掘算法AIS。1994年，由于项目集格空间理论的建立，他们在以往定理的基础上提出了著名的Apriori算法，这种算法目前仍作为关联规则挖掘的经典算法引起了人们的广泛研究和讨论。

一开始，关联规则的产生主要是针对购物篮分析问题。对于分店经理来说，如何更详细更清楚的了解顾客的购物习惯，尤其是想了解顾客可能会在一次购物时同时购买哪些商品？为此，我们对商店的顾客购物零售数量进行购物篮分析。而顾客的购物习惯就可通过他们放入“购物篮”中的不同商品之间的关联进行分析，零售商也可以通过这种关联分析了解哪些商品频繁的被顾客同时购买，进而有助于他们设计出更好的营销方案。

与此同时，一些知名的电子商务站点也可以从具有强大功能的关联规则挖掘中获得很大好处。通过使用关联规则对数据进行分析，这些电子购物网站可以设置用户有可能会同时购买捆绑包，也有很多购物网站设置了相应的交叉销售，具体是指顾客在购买一种产品时会看到与该类产品相关的另外一种产品的广告。但是目前我国商业银行在数据大集中之后，普遍面临着“数据海量，信息缺乏”的窘迫情况。目前，在金融业所采用的数据库中，大多数数据库的功能层次都很低，只能够简单的实现数据的录入、统计、查询等，根本发现不了数据中蕴含的大量有实用价值的信息。综上所述，可以说在关联规则挖掘技术方面，我国所进行的应用研究并不是很广泛，而且也不够深入。

1.2Apriori算法

使用关联规则对数据进行挖掘主要分两个阶段：第一阶段必须先从原始资料集合中找出所有的高频项目组，第二阶段再由这些高频项目组中产生关联规则。

关联规则挖掘的第一阶段中高频的意思是指在所有记录中某一项目组出现的频率必须相对达到某一水平。这一项目组出现的频率称为支持度。关联规则挖掘的第二阶段是利用前一步骤的高频k-项目组来产生关联规则，在最小信赖度的条件门槛下，要称之为关联规则一规则所求得的信赖度满足最小信赖度。

Apriori算法是关联规则挖掘频繁项集的一种原创性算法。Apriori算法使用的是迭代方法。Apriori算法的核心算法思想是：该算法中有连接步和剪枝步两个关键步骤。对于连接步来说，为了能够找出Lk，即频繁k项集，而通过Lk-1与自身相连接，产生候选k项集Ck；其中Lk-1的元素是能够连接的。对于剪枝步来说，Ck是Lk的超集，也就是说Ck的元素可以是频繁的也可以不是频繁的，但是所有的频繁项集都包含在Ck中。对数据库进行扫描，将Ck中的每一个候选的计数加以确定，从而确定Lk。如果Ck很大，就会导致涉及的计算量变得很大。为了能够压缩Ck，通常会使用Apriori性质。

Apriori算法，使用逐层迭代找出频繁项集。

输入：事务数据库D；最小支持度阈值min_sup。

输出：D 中的频繁项集L。

1） L1 = find_frequent_1_itemsets（D）；

2） for （k = 2； k++） {

3） Ck = aproiri_gen（Lk-1，min_sup）；

4） for each transaction t D{ // 扫描 D 用于计数

5） Ct = subset（Ck，t）；// 得到 t 的子集，它们是候选

6） for each candidate 错误！未找到引用源。 Ct

7） c.count++；

8） }

9） Lk={ Ck | c.count ≥ min_sup}

10） }

11） return L = 错误！未找到引用源。Lk；

Procedure apriori_gen (Lk-1:frequent(k-1)-itemsets)

重复，返回 Ck。

1.3Apriori算法评价和改进

基于频繁项集的Apriori算法采用了逐层搜索的迭代方法，该算法没有复杂的理论推导过程，简单易懂，并且很容易实现。但是仍然存在一些不可避免的不足：扫描数据库的次数过多。在Apriori算法的描述中，每生成一个候选项集，都要进行一次全面的数据库搜索。如果要生成的频繁项集的最大长度为N，那么就要扫描N次数据库。在有限的内存容量下，如果数据库中存放的事务数据过多，就会使得系统过大，导致扫描数据库时间变长，进而造成效率低下的不良现象。Apriori算法过程中会产生很多的中间项集。Apriori_gen函数是用Lk-1产生候选Ck，而Ck是由k个项集组成的，所以k越大，所产生的候选k项集的数量就会以几何级数的形式增加。采用唯一支持度，没有综合考虑到各个属性的重要程度会有所不同。Apriori算法的适应面是非常窄的，在实际的应用过程中，可能出现数量的、多维的、多层的关联规则，而Apriori算法只考虑单维布尔关联规则的挖掘。因此，这种情况下Apriori算法就不能再应用了，需要对其进行进一步的改进。

为了能够提高Apriori算法的性能，目前已经有许多变种对Apriori算法进行扩展和改进。具体的改进方法有以下几个方面：

（1）基于动态的项目集计数

该算法是将数据库分成不同的部分，标记最初的点，对数据库进行重复扫描。该算法能够在第二次扫描后完成所有的操作，它与Apriori算法最明显的区别是能在任何开始点增加新的候选项目集，在每个开始点，该算法对所有项目集的支持度进行估计，如果估计所有子集是频繁的，就会把该项目集增加到候选项目集中。

（2）基于划分的方法

PARTITION算法首先将数据库分成若干个互相不重叠的子数据库，然后分别对子数据库进行频繁项集的挖掘，最后将所有的局部频繁项集合并作为整个交易库的候选项集。该算法生成整个交易数据库的频繁项集只需要对数据库进行两次扫描即可。

（3）基于hash技术

通过hash技术的使用，在生成候选集时，DHP能够过滤掉更多的项集。因此每一次生成的候选集都会更加接近频繁集，对于二项候选集的剪枝来说，这种技术是非常有效的。除此之外，DHP技术还能够十分有效的降低每一次扫描数据库的规模。

2　关联规则在股票数据挖掘分析及预测中的应用

证券市场中的涨跌起伏往往是瞬息万变的，尽管如此，它还是存在着一定的规律：在某一段时间中，如果A股票出现上涨趋势，则B股票必然会随之上涨；如果A股票在tl时刻出现上涨趋势，B股票在t2时（t2>tl）刻出现上涨趋势，则C股票必然会在t3（t3>t2）时刻上涨。前一条规律能够用来对股票之间的相互关系进行分析，后一条规律能够用来对股票的涨跌进行预测，这些规律在投资者的实际决策过程中有着重要的参考价值和指导作用。

2.1选取数据

如果上市公司所经营的业务是相同或相近的，则在一段时间内股票价格的走势就会呈现出相似性；在一定时间内，属于同一个区域的上市公司也会受到区域经济政策的直接影响，也会呈现出大体相同的变化形势；如果上市公司之间具有关联交易，相互持股、控股，则它们之间也会产生某种相互作用。上述规则能够通过关联规则分析来发现，然而更重要的是发现另一种表面上没有很强的相关性、但是实际的股票价格却具有很大关联的规则。

设股票行情数据D={X1，X2，…，Xi，…，Xn。}，其中Xi (1

本文选取的研究对象是沪深300指数成分股，样本时间是从2010年9月2日到2011年9月1日一年的数据。分析可知，沪深300指数成分股能很好反映出上海和深圳证券市场的总体特征，具有很强的代表性。

选取样本时间从2010年9月2日到2011年9月1日这段时间的主要原因是：在这段时间中，大盘经历了上涨波段和下跌波段，沪深300指数最低到 1598，最高达3256，而且上涨时间和下跌时间大致相同。本文数据均来源于CASMAR数据库，着重考虑股票价格变化之间存在的关联关系，由于一天中股票价格有很多种，本文主要考虑的是收盘价。因此原始数据包含日期、股票代码、收盘价三个变量，经过处理数据中共有71268条记录。

表1　关联规则模型的变量

2.2数据预处理

数据预处理是指在主要的处理以前对数据进行的一些处理。在我们实际生活的世界中，数据大多数都是不完整并且不一致的，根本没有办法直接使用数据挖掘方法，或者会导致挖掘的结果不能让人满意。为了能够有效的将数据挖掘的质量提高，数据预处理技术便在这种形势下产生了。数据预处理的方法有很多，具体包括：数据清理，数据集成，数据归约，数据变换等。在对数据进行挖掘之前，使用这些数据处理技术，能够在很大程度上提高数据挖掘模式的质量，并且有效的减少挖掘所使用的时间。我们所要研究的是在一段时间内，股票价格变动之间存在的关联关系，因此只需对那些对投资有参考价值的数据进行研究。在投资过程中，关系到投资者收益的重要指标是收益率，在数据挖掘中所选用的是每天的涨跌幅。首先以收盘价为依据，将每日的涨跌幅计算出来，日涨跌幅就是当日收盘价和上一个交易日收盘价之差与上一个交易日收盘价之比。计算公式如下：

在分析过程中我们所感兴趣的是那些每天的涨跌幅大于一定幅度的股票，因为在股票市场中，大多数股票会随着大盘指数的涨跌而不断发生变化，多数股票都会在大盘指数涨跌幅进行上下波动，所以只有涨跌幅超过一定范围的股票才具有研究意义。因此我们在进行分析之前，引入最小日涨跌幅Min-UpRat。最小日涨跌幅的值是以具体的股票行情为依据并由用户确定的，本文选取Min-UpRat为3%，这主要是从以下几个方面考虑：现阶段，中国的证券市场还处于发展阶段，尚不成熟。股票在牛市中会存在随大盘指数普遍上涨的情况，因此只有对那些涨势较为剧烈的股票进行分析研究才会有实际意义。大部分股票在熊市中会出现普遍下跌的情况，出现上涨形势的股票只有极少的一部分，涨势能达到3%涨幅的股票更是少之又少。

在样本中添加一个新的变量，极为win，当日涨跌幅大于最小日涨跌幅min-UpRat时，win就记为1，日涨跌幅小于或等于最小日涨跌幅min-UpRat时，win就记为0。在原始数据中，交易日期均为10个字符的字符型变量，共有244天。众所周知，在进行数据挖掘时，字符长度较大会占用大量的内存，因此应该尽量用简短的数据型变量来对其进行替换。所以为了节省空间进而提高运行的效率，我们重新对交易时间变量进行编码，用1，2，…，244来标记。将股票代码均变为6位字符的字符型数据，共有300只股票，分别用1，2，…，300标识。在进行关联规则挖掘时，直接处理对象是股票和日期的新编码，间接处理对象是股票代码和交易日期，这样便可有效减少内存的占用，有利于提高挖掘效率。

表2　关联规则模型的原始数据

选取的原始数据有字符型证券代码，字符型交易日期，数值型收盘价，如表2所示。接着对原始数据进行变换和预处理，然后计算出每个交易日各只股票的涨跌幅。

2.3数据探索

一般情况下，在进行数据挖掘之前可以先对数据进行初步探索，用描述性统计方法对数据进行初步的分析，从而对沪深300指数的一些基本性质进行简单的了解。通过整理可以看出，虽然股票指数有某种程度的变化和波动，但是总体变化趋势是先下跌而后上涨。这种情况表明，在这一年中由于受到全球经济的影响，股票市场先逐渐下降，随着中国各项经济政策的一系列措施的实施，中国证券市场又出现了回升的趋势。

3　总结

对于挖掘的方法，不同的研究者将根据各自的偏好和理解制定不同的策略，发现规律可能具有不稳定性和时效性；关联规则是数据挖掘算法的一种，将对结果有决定性的影响，过分挖掘和优化不一定会产生预期的效果，在审慎的原则下对股票数据进行挖掘，将会成为可靠的研究手段。

参考文献

[1] 夏火松主编.数据仓库与数据挖掘技术[M]. 科学出版社, 2004

[2] 王玲.数据挖掘在证券分析中的应用[D]. 贵州大学 2008

[3] 谢忠.基于数据挖掘技术的证券投资辅助决策支持系统[D].重庆大学 2005

Analysis and application of data mining algorithm based on association rules

Fang Rong
(Huizhou radio and TV University,Guangdong Huizhou,516007)

Abstract：Data mining is to extract useful information from a large number of data.The essential difference between data mining and traditional data analysis is that data mining is to excavate information and discover knowledge without explicit assumptions. This paper analyzes the characteristics of association rules of data mining algorithms, and focuses on the application of the data mining algorithm in the stock market, so that it can be applied in more areas.

Keywords：association rule; data mining algorithm; stock