关键字 |
| 关联规则挖掘，数据挖掘，支持度，置信度，频繁项集，算法 |
介绍 |
| 近年来，数据库的规模一直在迅速增加。这就导致了能够自动从数据中提取知识的工具的发展。术语数据挖掘处理数据库中隐藏信息的自动发现。在数据挖掘的主要领域中，频繁项的发现是一项艰巨的任务。它是由Agrawal等人在1993年提出的，被称为市场篮子问题。在这个问题中，给出了包含大量项目的大量事务集合。任务是找到这些篮子中不同物品之间的联系。关联规则的发现依赖于频繁集的发现。频繁项在数据挖掘任务中起着重要作用。关联规则描述物品一起购买的频率。 For example , a rule “bread => Jam” 80% states that eight out of ten customers who bought bread also bought jam. These such rules are useful for decision making in various areas. These areas includes product pricings, inventory management, sales promotion strategies etc. Here, we explain the concept of frequent item sets , association rule mining problems and an algorithm to find the frequent items. |
问题定义 |
| 让A = {A1, a2，…，Am} be a set of itemset. Let D be a set of database transactions where each transaction T is a nonempty itemset such that T ⊆ A. Each transaction is connected with an identifier, called a TID. Let X be a set of items. A transaction T is said to contain in X if X ⊆ T. An association rule is an implication of the form X⇒ Y, where X⊂ I, Y ⊂ I, X ≠∅, Y≠ ∅, and X ∩Y = φ. The rule X ⇒ Y holds in the transaction set D with support s.Here s denotes the percentage of transactions in D that contain X ∪Y (i.e., the union of sets X and Y say, or, both X and Y). This is taken to be the probability, P(X ∪Y). The rule X ⇒ Y has confidence c in the transaction set D.Here c denotes the percentage of transactions in D containing X that also contain Y. This is taken as the conditional probability, P(Y|X). support(X⇒Y) =P(X ∪Y) confidence(X⇒Y) =P(Y|X). |
问题分解 |
| 关联规则的推导问题可以分解为两个部分: |
| 1.找到支持度大于用户提到的最小支持度的所有项目集(项目集)。这样的项目集称为频繁项目集[1]。 |
| 2.使用得到的频繁项集生成可能的规则。 |
| 向下闭包性质:一个集合是频繁集的子集，它也是一个频繁集。 |
| 向上闭包性质:一个集如果是不频繁集的超集，它也是一个不频繁集。 |
| 最大频繁集:如果一个频繁集是一个频繁集，并且它的超集不是一个频繁集，那么它就是一个最大频繁集。 |
| 边界集:如果一个项集不是频繁集，那么它就是边界集，但它的所有适当子集都是频繁集[1]。 |
文献综述 |
| C.K.S. Leung和Q.I. Khan在本文中，随着技术的进步，可以在许多应用中产生大量的数据，如传感器网络和Web点击流。这就需要从数据流中提取有用信息的有效技术。在本文中，我们提出了一种新的树结构，称为DSTree(数据流树)，用于从流中捕获重要数据。通过利用其良好的属性，可以轻松地维护和挖掘DSTree以获取频繁项集以及各种其他模式(如约束项集)。 |
| S.K. Tanbeer和C.F. Ahmed在这篇文章中指出，在连续的交易流中发现频繁的模式对于许多应用来说是至关重要的，例如零售市场数据分析、网络监控、web使用挖掘和股票市场预测。尽管在过去十年中已经开发了大量频繁的模式挖掘算法，但由于数据流中以快速速率生成的连续、无界和有序的数据元素序列，仍然需要处理流数据的新解决方案。因此，从最近的数据中提取频繁的模式可以增强对流数据的分析。在本文中，我们提出了一种有效的技术，从滑动窗口上的高速数据流中发现最近频繁模式的完整集。我们开发了一个紧凑模式流树(CPS-tree)来捕获最近的流数据内容，并有效地删除过时的、旧的流数据内容。我们还在CPS-tree中引入了动态树重构的概念，以在运行时产生高度紧凑的频率下降树结构。使用FP-growth挖掘技术从当前窗口的CPS-tree中获得最近频繁模式的完整集。大量的实验分析表明，在从高速数据流中查找最近频繁模式时，我们的cps树在内存和时间复杂度方面是高效的。 |
| C. Giannella, J. Han, J. Pei尽管频繁模式挖掘已经被广泛研究和使用，但将其扩展到数据流是一个挑战。与从静态事务数据集中挖掘相比，流案例有更多的信息要跟踪，管理也要复杂得多。不常见的项目以后会变得频繁，因此不能忽视。存储结构需要动态调整，以反映项集频率随时间的变化。 |
| 关联规则挖掘是数据挖掘领域的一个重要研究课题。在挖掘关联规则时有两个困难。首先，用户必须指定对挖掘的最小支持。通常，在获得一组有用的关联规则之前，可能需要多次调优最小支持值。然而，对于用户来说，找到一个合适的最小支持是不容易的。其次，挖掘结果中通常会产生大量的频繁项集。这会导致生成大量的关联规则，给应用带来困难。在本文中，我们考虑使用滑动窗口技术从数据流中挖掘top-k频繁封闭项集。开发了一种名为FCI_max的单遍算法，用于生成长度不大于max_l的top-k频繁封闭项集。该方法有效地解决了关联规则挖掘中的上述两个难点，提高了挖掘结果在实际中的可用性。 |
ITEMSET矿业 |
| A.频繁的项目集挖掘 |
| 频繁项集是在事务中重复出现的项。频繁项集挖掘的主要目标是识别事务数据集中所有频繁购买的项集。Apriori算法是频繁模式挖掘问题的初始解。为了克服Aprori生成更多候选集和需要对数据库进行更多扫描的问题，提出了FP-Growth算法。使用FP-Tree数据结构，无需任何候选生成，只使用两次数据库扫描。在频繁项集挖掘框架中，不考虑项的重要性。 |
| B.加权频繁项集挖掘 |
| 在这种情况下，项目的重要性以权重的形式表示。模式p的权重是其所有权重之和与p的长度之比。在频繁的项集挖掘情况下，项的相对重要性不被测量。为了解决这一问题，引入了加权关联规则挖掘。这里给项目赋予权重，以表示项目对用户的重要性。其中权重表示项集的重要性。 |
| C.高效用项集挖掘 |
| 在数据挖掘领域中，效用挖掘是寻找高利润项目的重要手段。效用挖掘关注项集的频率以及与项集相关的效用。在高效用项集挖掘中，目的是识别具有超出给定效用阈值的效用值的项集。项集的效用定义为其外部效用和内部效用的叉乘。 |
研究需求 |
| 如今，各个领域都产生了大量的数据。产生的数据是数据流的形式。这些流数据是连续的，不是有界的。流数据也不是均匀分布的。由于流数据需要多次扫描，因此很难从数据流中找到频繁项。一旦河流流过，我们就失去了他们。因此，我们需要一些技术来处理和捕获流的重要内容，并确保捕获的数据能够适合内存。此外，由于流中的数据分布通常随时间而变化，当前不频繁的项集在未来可能会变得频繁，反之亦然。因此，应避免在早期对不常见的项目进行修剪。否则，无法获得某些项集的频率等完整信息(因为无法回忆起那些修剪后的项集)。已经提出了许多算法来从流中挖掘fi。因此，我们提出了一种利用非固定大小窗口的阻尼窗口模型来寻找频繁项的新算法。它既重视前一批数据，也重视当前数据。 |
算法 |
| 在此，我们提出了一种基于数组的尾节点算法，利用阻尼窗口模型挖掘频繁项集。提出的UDS-FIM算法主要包括三个步骤:(1)阻尼窗口初始化(2)创建全局UDS-Tree;(3)从全局UDS-Tree中挖掘频繁项集; |
| A.阻尼窗口初始化 |
| 阻尼窗口初始化阶段是在事务数据流中迄今为止生成的事务数小于或等于用户预定义的窗口大小w(批处理)时启动的。在此阶段，新传入事务的每一项都转换为其全局UP表。 |
| 一般来说，在w批流数据到达后，所提出的算法将遍历所有O(N)个节点w−1次，并更新O(w2N)个旧的期望支持值(即O(w2N)乘法)。经过w=3批流处理 |
| 数据到达时，阻尼算法遍历N=9个节点两次，更新27个旧的期望支持值(涉及27次乘法:B2到达后9次，B3到达后18次)。为了降低更新成本，我们提出了一种改进算法。我们的改进算法不是更新旧的预期支持值并追加新值，而是将新的预期支持值追加到列表中。然后，在计算X在数据流中的期望支持度(目前为止的w批，即B1:w≡B1 Bw)时，改进算法使用以下公式: |
 |
| 其中(X,Bj)为X存储在列表第j位的期望支持度(表示流数据的Bj)， α∈(0,1)为衰落因子。通过这样做，我们可以避免在更新过程中发生O(w2N)乘法。用公式(2)计算期望支持度只涉及O(N)个fi上的O(wN)乘法。 |
| B. uds树参数 |
| 设项集X = {x1, x2, x3…xu}是一个排序项集，项xu称为X的数组尾项。将项集X按顺序加入到树T中，树中表示该数组尾项的节点称为数组尾节点;没有子节点的节点称为叶节点;既不是数组尾节点也不是叶节点的节点称为普通节点。 |
| 在将事务项集添加到UDS-Tree之前，将其相应的概率值追加到表中。 |
| c算法 |
| 输入:一个阻尼尾节点树T，一个全局项集报头表H，一个最小期望支持数minExpSN。 |
| 输出:fi(频繁项目集) |
| (1)首先计算数据流中X的期望支持度(w批)， |
| (2)将每个叶节点上info字段的批处理信息添加到字段addInfo中; |
| (3)对于H中的每一项x(从最后一项开始)做 |
| (4)如果(x.esnT≥minthreshold) //x.esnT来自报头表H |
| 生成项集X = X; |
| (6)将X复制到fi中; |
| 为X创建子报头表Hx; |
| (8)如果(Hx不为空) |
| (9)为X创建前缀UDS-Tree Tx; |
| 调用子挖掘(Tx, Hx, X) |
| (11)修剪非频繁项集 |
| (12)如果 |
| (13)如果 |
| (14)将addInfo字段的信息传递给父节点; |
| (15)结束 |
| (16)返还金融机构。 |
| 子程序子挖掘(Tx, Hx, X) |
| (17)对于Hx中的每一项y(来自最后一项)做 |
| (18)生成项集Y= X∪; |
| (19)将Y复制到金融机构中; |
| (20)为Y创建头表Hy; |
| (21) If (Hy不为空) |
| (22)为Y创建前缀UDS-Tree Ty; |
| 调用SubMining(Ty, Hy, Y) |
| (24)如果 |
| (25)将info list字段的信息传递给父节点; |
| 结束于 |
结论 |
| 在本文中，我们提出了基于尾节点树的挖掘算法，该算法使用阻尼窗口模型来挖掘频繁项集的不确定数据动态流。UDS- fim在维护UDS树频繁项的前提下，查找频繁项集。然后将挖掘的项存储在具有预期支持值的流结构中。当下一批到达时，它更新uds流结构。改进后的算法只附加最近数据的预期支持值，从而降低了成本。UDS FIM对每个项集只保留一个support值。与其他算法相比，UDS FIM查找频繁项集所需时间最短。 |
数字一览 |
 |
| 图1 |
|
参考文献 |
- K.Jothimani和Dr.AntonySelvadossThanamami，“ds - fi:挖掘频繁项集的有效数据结构”，来自ISCA(印度科学大会协会)的信息和通信技术，包括计算机科学(ICT)，加尔各答，2013年1月3日至7日。
- K.Jothimani和Dr.AntonySelvadossThanamami，“确定数据sd流中频繁项集挖掘的因素”，2011年8月12日至13日在VELTECH dr . r & SR技术大学举行，pp-127-130,ISBN 978-93-80624-43-3。
- 林志伟，洪涛，“一种基于CUFP树的不确定数据库挖掘方法”，《专家系统与应用》，Vol.39, no.4,pp。4084 - 4093年,2011年。
- 廖国强，吴林，熊宁，一种基于事务不确定数据流的概率频繁模式挖掘方法，第八届泛在智能与计算国际会议，2011,pp.563- 564。
- C.C. Aggarwal和P.S. Yu，“不确定数据算法和应用的调查”，IEEE知识与数据工程汇刊，卷。21日,没有。5，pp.609-623, 2009.
- 梁志强，M.A.F. Mateo和d.a rajczuk，基于树的不确定数据频繁模式挖掘方法，第12届亚太知识发现与数据挖掘会议(PAKDD 2008)。2008年,pp.653 - 661。
- K.Jothimani和Dr.AntonySelvadossThanamami，“基于CB的频繁项集挖掘方法”，国际现代工程学报(IJMER)， Vol.2, Issue.4, 7 - 8。2012 - 2508 - 2511页。
- 孙X.，林丽君，王世峰，“一种从不确定数据集中挖掘频繁项集的近似算法”，《计算机工程学报》，Vol.4, no. 4。3，页42-49,2012。
- T. Calders, C. Garboni和B. Goethals，不确定数据中项目集频率概率的逼近，IEEE数据挖掘国际会议(ICDM 2010)。2010年,pp.749 - 754。
- 王磊，郑荣华，李世峰，杨晓明，“大型不确定数据库中频繁项集的高效挖掘”，《计算机工程》，2011年第99期(预印本)。
- 梁志强，C.L. Carmichael和B. Hao，从不确定数据中高效挖掘频繁模式，国际数据挖掘研讨会(ICDM研讨会2007)。2007年,pp.489 - 494
- q。张飞，李飞，易凯，概率数据中频繁项的发现，国际数据管理会议(ACM SIGMOD)。2008年,pp.819 - 831。
- 梁志强和江飞，基于阻尼窗模型的不确定数据流频繁项集挖掘，第26届ACM应用计算学术研讨会(SAC 2011)。2011年,pp.950 - 955。
- 梁志强和江飞，从时间衰减的不确定数据流中频繁挖掘模式，第13届数据仓库和知识发现国际会议(DaWaK 2011)。2011年,pp.252 - 264。
- K.Jothimani和Dr.AntonySelvadossThanamami，“一种高效的大窗口频繁项集挖掘方法”，国际计算工程学报，ISSN: 2250-3005，第2卷第3期，2012年5月- 6月，pp.923-92
|
菜单
