英语原文共 4 页，剩余内容已隐藏，支付完成后下载完整资料

微Apriori算法——一种寻找具有连续性属性数据关联度的算法

Eui-Hong (Sam) Han George Karypis, Vipin Kumar

Department of Computer Science and Engineering/Army HPC Research Center University of Minnesota 4-192 EECS Bldg., 200 Union St. SE Minneapolis, MN 55455, USA fhan,karypis,kumarg@cs.umn.edu

数据挖掘中的一个重要问题就是从具有事务类型(transaction)的数据库中发现关联规则，这种数据库的显著特点是每个事务包含一组项目。现在已经有几种查找关联规则的算法，而大多数算法都在专注于事务的数据，其中每个事务都包含一个项目的子集。事务数据可以被认为是二进制的，每个事务都包含一个特定的项。这种数据集的例子很常见，比如说市场购物篮数据。一个典型的商店可能有几千个项目，而一个事务则对应于客户购买的一组商品。

当数据集包含连续属性时，现有的算法可能不起作用。例如，除了客户购买的商品外，数据可能包含客户的年龄和工资。你可能想知道年龄/工资和项目之间的联系。在这种情况下，在应用关联规则算法之前，需要对年龄和工资属性进行离散化。一旦这些属性被离散化，就可以发现像 `年龄 lt; 30岁 HrArr; Rollerblade` 这样的关联规则。在[SA96]中讨论了这类数据中关联规则的离散化和发现的实现方法。

另一种类型的数据具有完全连续的特性。例如，文档数据由一组文档组成，每个文档包含单词。这个原始数据被转换成一个表，其中每一行对应一个单词，每个列对应一个文档。这个表的每个条目(i, j)对应于文档j中的单词的频率。从这个表中，用户可能想要找出不同文档或单词之间的关联规则。请注意，在本例中，离散化并不适用于用户希望在文档或单词之间的关联关系，而且也不是与每个单词或文档关联的频率范围。

在本文中，我们提出了一种新的算法来发现上述段落中所讨论的这种类型数据集的关联规则。

关联规则指的是事务中存在的项的关系[AMS 96]。现在假设T是事务的集合，这个集合中每个事务对项目集i中的每个项目都有值。例如，从表1中所示的文档数据中考虑一组事务集。我为这些事务设置的项是`{ doc1、doc-2、doc-3、doc-4、doc-5 }`，每个事务对应于文档数据中的一个单词。表中每个值T(i, j)对应于文档j中i的频率，例如，word-1在doc1和doc3中出现两次，一次在doc5中，而在doc2和doc4中则没有出现。

微Apriori算法的第一步是沿着表的列进行值的标准化。我们将这些值标准化，使每一列都增加到1.0。标准化后的表如表2所示。

让C为I的子集，然后我们定义C对T的支持度为:

其中T(i, j)对应于规范化事务表中的值。例如，{ doc1, doc3 } 的支持度是0.4 0.4 0.0 0.0 0.0 = 0.8，而 { doc-1, doc-3, doc-5 } 的是 0.2 0.2 0.0 0.0 0.0 = 0.4。

上述支持度的单调性定义满足了对比较频繁(或大的)二进制值项集定义的支持。换句话说,基于新的支持度定义，任何C的子集S的支持度是大于或等于C的支持度的。这是由于最小函数的单调性的特性,如果Asube;B且A和B是一组数字,然后就有min(A)ge;min(B)。因此，我们有：

由于这种支持度的新定义满足了单调性的特性，因此，现有的大多数用于查找关联规则的算法都可以根据这个新的定义来查找关联规则。我们基于[AS94]中提出的Apriori算法实现了微-Apriori算法。

我们已经应用了微apriori算法来查找web文档数据的关联规则，并使用关联规则来查找单词和文档的集群数据[HBG 97, HKKM97]。结果表明，我们可以在文档和单词之间找到有意义且有用的关联规则，而不需要对数据中的值进行离散化。研究结果还表明，当数据中值越高表明关系越强时，就可以应用微apriori算法。我们计划在不同的数据上应用微Apriori来度量算法的适用性和有效性。

References

[AMS 96] R. Agrawal, H. Mannila, R. Srikant, H. Toivonen, and A.I. Verkamo. Fast discovery of association rules. In U.M. Fayyad, G. Piatetsky-Shapiro, P. Smith, and R. Uthurusamy, editors, Advances in Knowledge Discovery and Data Mining, pages 307–328. AAAI/MIT Press, 1996.

[AS94] R. Agrawal and R. Srikant. Fast algorithms for mining association rules. In Proc. of the 20th VLDB Conference, pages 487–499, Santiago, Chile, 1994.

[HBG 97] E.H. Han, D. Boley, M. Gini, R. Gross, K. Hastings, G. Karypis, V. Kumar, B. Mobasher, and J. Moore. Webace: A web agent for document categorization and exploartion. Technical Report TR-97-049, Department of Computer Science, University of Minnesota, M inneapolis, 1997.

[HKKM97] E.H. Han, G. Karypis, V. Kumar, and B. Mobasher. Clustering in a high-dimensional space using hypergraph models. Technical Report TR-97-063, Department of Computer Science, University of Minnesota, Minneapolis, 1997.

[SA96] R. Srikant and R. Agrawal. Mining quantitative association rules in large relational tables. In Proc. of 1996 ACM-SIGMOD Int. Conf. on Management of Data, Montreal, Quebec, 1996.

[SAD 93] M. Stonebraker, R. Agrawal, U. Dayal, E. J. Neuhold, and A. Reuter. DBMS research at a crossroads: The vienna update. In Proc. of the 19th VLDB Conference, pages 688–692, Dublin, Ireland, 1993.

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[23283]，资料为PDF文档或Word文档，PDF文档可免费转换为Word