关键字 |
| 实用挖掘，高实用项目集，稀有项目集，频繁项目集挖掘 |
效用挖掘简介 |
介绍 |
| 数据挖掘是一个处理从数据库中“知识发现”的领域。它处理从不同角度分析数据，并将其总结为有用的信息，可用于增加收入，削减成本，或两者兼而有之。它还处理从可用数据中提取隐藏模式，并将这些数据转换为知识。数据挖掘可以应用于任何大小的数据集，通常用于广泛的应用，如营销、欺诈检测和科学发现。在市场营销等领域，数据挖掘技术被用于研究客户购买模式，以制定营销策略。这可以基于两个标准，即定义产品销售频率的频率和告知与每种产品相关的利润的效用。最初用于挖掘交易数据库的算法集中于寻找频繁的项目集，但产品的重要性主要是衡量它在每笔交易中的效用。这让位于效用挖掘的方法论。 |
| 从数据库中挖掘高效用项集是指寻找具有高效用(如利润)的项集。效用的基本含义是物品对使用者的重要性/收益性。事务数据库中项目的效用由两个方面组成:(1)不同项目的重要性，称为外部效用;(2)事务中项目的重要性，称为内部效用。项集的效用定义为外部效用乘以内部效用。如果效用不小于用户指定的阈值，则称为高效用项集;否则，该项目集称为低效用项目集。 |
| 从数据库中挖掘高效用项集并不是一项简单的任务，因为在频繁项集挖掘中使用的向下闭包属性在这里不能应用。换句话说，修剪高效用项集挖掘的搜索空间是困难的，因为低效用项集的超集可能是高效用项集。解决这一问题的一种有效方法是根据穷竭原则从数据库中枚举所有项集。这种方法会遇到搜索空间大的问题，特别是当数据库中包含大量的长事务时。因此，如何有效地修剪搜索空间，有效地捕捉所有高效用项集，不出错是效用挖掘的一大挑战。 |
| 传统的效用挖掘方法主要是生成所有可能的项目集组合，然后计算项目集的效用。这也称为候选生成，其中候选是一组项集。当项目数量增加时，复杂性就会变高。 |
| 有许多方法可以从事务数据库中挖掘高效用项集。虽然最原始的方法使用了候选生成，但一些方法被进化来寻找避免候选生成的高效用项集。这里提出了一种这样的方法。这个项目的动机就是来自这样一种方法。该项目旨在减少识别高效用项集所需的候选生成，从而减少数据库扫描的次数 |
文献调查 |
介绍 |
| 效用挖掘的概念处理从事务数据库中隔离高效用项集。高效用项集挖掘是基于效用的描述性数据挖掘的一个研究领域，旨在寻找对总效用贡献最大的项集。 |
| 挖掘频繁项集的算法，如Apriori算法[1]，FPgrowth算法[3]。Apriori算法是一种从大型数据库中高效挖掘关联规则的主动算法。FP-Growth是一种基于树的方法，它在不生成任何候选集的情况下发现频繁项集，性能优于基于Apriori的算法。在频繁项集挖掘中，不考虑项对用户的重要性。不考虑商品的单位利润和购买量。提出了从数据库中挖掘高效用项集的方法，如UMining[6]、Two-Phase[4]、IIDS[5]和IHUP[8]。 |
高效用模式挖掘 |
| 高效用模式挖掘的理论模型和定义在姚海涛的[9]中给出。这种方法称为具有预期效用的挖掘(MEU)。此方法用于根据事务数据库中的信息和关于实用程序的外部信息识别高实用程序项集。MEU不能保持Apriori的向下闭包属性，[9]的作者使用启发式来确定是否应该将一个项集视为候选项集。此外，MEU通常会高估，特别是在开始阶段，此时候选项的数量接近所有项目组合的数量。当不同项目的数量很大而效用阈值很低时，这种特性是不切实际的。 |
UMINING算法 |
| Yao等人[6]提出了一个统一的基于效用的挖掘项目集度量框架。在该算法中，提出了一个统一的框架，通过定义一个统一的效用函数，将多个基于效用的度量纳入数据挖掘过程。在该算法中总结了基于效用的度量的数学性质，这将允许减少项目集挖掘算法的时间和空间成本。尽管它显示出了良好的性能，但它不能捕获高效用项集的完整集，因为在此过程中可能会删除一些高效用模式。 |
两阶段算法 |
| Liu等提出的两阶段算法[4]。有效地减少候选项的数量，并能精确地获得高效用项集的完整集合。它由两个阶段组成。在第一阶段，两阶段算法采用广度优先搜索策略来枚举htui。它从长度为(k-1)的htui生成长度为k的候选项集，并通过TWDC属性删除候选项集。每一次通过扫描数据库计算htui及其估计效用值，即twu。第二阶段通过扫描原始数据库一次，从htui中识别出高效用项集及其效用。虽然两阶段算法通过TWDC属性有效地减少了搜索空间，并捕获了高效用项集的完整集，但它仍然会生成过多的htui候选项，并且需要多次数据库扫描。 |
iid算法 |
| 为了克服两阶段算法中的问题，Li等人提出了一种孤立项丢弃策略(IIDS)[5]来发现高效用项集，减少候选项集的数量，提高性能。IIDS表明，项目集份额挖掘问题可以直接转化为效用挖掘问题，将交易中每个项目的频率值替换为其总利润，即频率值乘以其单位利润。通过在逐级搜索过程中对孤立项进行修剪，可以有效减少第一阶段htui的候选项集数量。然而，这种方法仍然多次扫描数据库，并使用候选生成和测试方案来查找高效用项集 |
系统设计 |
问题定义 |
| 考虑下面给出的表格。事务数据库(表1)提供了关于每个项目集的消费的信息。效用表(表2)提供了关于用户定义的每个项目的效用值的信息。设I={i1, i2，.....i∈D是i的子集。每个项目ip(1≤p≤m)有一个单位利润p(ip)。项集X是k个不同项的集合{i1, i2，…，ik}，其中ij 1≤j≤k, k是X的长度。长度为k的项集称为k-项集。事务数据库D = {T1, T2，。，Tn} contains a set of transactions, and each transaction Tq (1 ≤ d ≤ n) has an unique identifier d, called TID.Each item ip in the transaction Tq is associated with a quantity q(ip, Tq), that is, the purchased number of ip in Tq. |
| 定义1:效用u(ip,Tq)是对交易Tq中项目ip效用的量化度量，定义为u(ip,Tq)= q(ip,Tq) × p(ip)。例如u({D}，T2)= 2 × 1= 2。 |
定义2:项目集X在事务Tq, u(X, Tq)中的效用定义为 |
| 其中X = {i1;i2;. . . . . .:本土知识}是一个k-itemset X⊆Tq,和1≤≤k m。例如,u ({CD}, T1) = (C {}, T1) + u ({D}, T1) = 1 + 2 = 3。 |
D中项集X的效用定义为 |
| 例如,u ({AC}) = ({AC}, T1) + u ({AC}, T2) + ({AC}, T3) = 6 + 16 + 6 = 28。 |
定义3:交易Tq的交易效用(tu)记为tu(Tq)，描述了该交易的总利润。简单地说，一笔交易的交易效用是该交易中存在的各个项目的效用之和，由 例如,你(T1) = u ({}, T1) + u (C {}, T1) + ({D}, T1) = 5 + 1 + 2 = 8。 |
| 定义4:如果u(X)≥minutil，则项目集X是高效用项集。找到高效用项集意味着确定所有项集X具有u(X)≥minutil的标准 |
定义5:项目集X的事务加权利用率(TWU)，用TWU (X)表示，是包含该项目集的所有事务的事务效用之和。 例如，twu({AC}) = tu(T1) + tu(T2) + tu(T3) = 8 + 27 + 30 = 65。 |
| 定义6:如果twu(X)≥minutil, X是一个高事务加权利用率项集(即候选项集)。例如，minutil= 40, twu({AC})=65，则twu({AC})≥40。 |
| 定义7:项目ip的事务频率(tf)为tf(ip)，表示该项目出现的事务数量。ip的原始频率是f(ip)，它表示ip在这些事务中的实际出现次数。例如，tf(C) = 5。 |
| 定义8:事务加权向下闭包(缩写为TWDC)的表述如下。对于任意项集X，如果X不是HTWUI，则X的任何超集都是低效用项集。根据这个定义，向下闭包属性可以通过使用事务加权利用率来维护。例如，在表1中，{AD}的任何超集都是低效用项集，因为TWU({AD}) < min_util。 |
建议的数据结构 |
| 我们使用紧凑的树结构来维护事务信息和高效用项集。树形结构要素: |
| 每个节点N包含1。N.name-节点的项目名称。2.N.count -节点的支持计数。3.N.nuestimate节点的效用值。4.N.parent—节点的父节点，5。N.hlink-节点链接，指向项名与N.name相同的节点。头表的实现是为了遍历树。 Each entry in the header table is composed of an item name, an estimate utility value, and a link. The link points to the last occurrence of the node which has the same item as the entry in the Tree. By following the link in the header table and the nodes in Tree, the nodes whose item names are the same can be Traversed efficiently. |
在构建全局树期间移除全局无希望的项目 |
| Tree的构造可以通过对原始数据库的两次扫描来执行。在数据库的第一次扫描中，计算每个事务的事务效用。同时，每个单项的TWU也在累积。扫描数据库一次后，得到项目及其twu。根据TWDC属性，如果项目的TWU小于最小效用阈值，则其超集不可能成为高效用项集。TWU(ip)≥min_util的项目ip称为有希望的项目。第一次扫描数据库后，有希望的项按照TWU值降序排列在报头表中。在第二次扫描数据库时，事务被插入UP-Tree。最初，树是用根R创建的。 |
| 树可以使用下面给出的步骤来构造。 |
造树程序 |
| 步骤1:创建一个根节点并将其赋值为null |
| 步骤2:对于事务数据库中的每个事务Ti，提取事务中的第一个元素。 |
| 步骤3:检查在root的子元素中是否存在该元素的节点。 |
| 步骤3.1如果是，则向元素的事务实用程序添加当前事务中元素的事务频率。 |
| 3.1.1步检查该节点的子元素和事务中的下一个元素 |
| 3.1.2步如果它们匹配，则重复向元素的事务实用程序(特定事务中的实用程序)添加的过程。 |
| 步骤3.2如果没有，那么创建一个新节点并将其分配为根节点的子节点，并将事务中的其他元素添加为新创建的节点的子节点。 |
| 当将此过程应用于事务数据库中的事务集时，将创建树。当检索事务时，将从事务中删除无希望的项，并从事务的TU中删除它们的效用，因为只有有希望的项的超集才可能是高效用项集。事务中剩余的有希望项按照TWU降序排序。经过上述重组的事务称为重组事务，其TU称为RTU(重组事务实用程序)，如表3所示。一个重组事务Td的RTU记为RTU(Td)。 |
| 示例1:考虑表1中的交易数据库和表2中的利润表。假设最小效用阈值min_util是40。在数据库的第一次扫描中，计算事务的单位单位和项目的单位单位。它们分别显示在表1和表4的最后一列中。从表4中，{F}和{G}是没有希望的项，因为它们的twu小于min_util。希望项在头表中按照TWU降序进行重组。表3显示了表1中数据库的重组事务及其rtu。如表3所示，分别从事务T2、T3和T5中删除无希望的项目{F}和{G}。此外，{F}和{G}的效用分别从T2、T3和T5的tu中消去。交易中剩余的有希望项{A}、{B}、{C}、{D}、{E}按TWU降序排序。 Then, we insert reorganized transactions into the Tree by the same procedure as mentioned above. |
| 例2:插入操作。考虑表4中的重组事务。第一个重组事务T1 ' = {C, A, D}导致在Tree中创建一个分支。节点{C}是在根节点下使用{C}创建的。count = 1和{C}。Nu = 8。第二个节点{A}创建在带有{A}的节点{A}之下。count = 1和{A}。Nu = 8。第三个节点{C}作为节点{a}和{C}的子节点被创建。count =1和{C}。Nu = 8。当检索到下一个重组事务T2 ' = {C, E, A}时，节点{C}的节点效用增加22和{C}。Count增加1。然后，在{C}下使用{E}创建一个新节点{E}。count=1和{E}。Nu = 22。类似地，在带有{a}的节点{E}下创建一个新节点{a}。count=1和{A}。Nu = 22。以相同的方式插入重组的事务T3 '、T4 '和T5 '。 The tree is constructed with inserting all reorganized transactions. |
通过应用FP-Growth从树中生成hui |
| 在图1中，树中的每个节点都有两个数字:一个是支持计数，另一个是节点效用。具有相同项目名称的节点通过节点链接按顺序连接起来。在树中，每个节点{ai}到根形成一条路径({ai}-> {ai+1}->…- >{})。每个路径表示由多个重组事务共享的前缀。{爱}。Count是共享路径和{ai}的重组事务的数量。Nu是路径的估计效用值。与[8]类似，可以通过应用FP-Growth[3]从树中生成hui。 |
| 例3。考虑图2中的树。假设min_util为40。该算法从报头表的底部开始，首先考虑项{D}。通过应用FP-Growth，由于HUI {D}:58的估计效用值大于min_util，因此生成HUI {D}:58。通过遵循{D}。Hlink，找到具有相同项目名称的节点。通过追踪节点到root，可以找到三条路径(D->A-> C: 1,8)、(D->B->A->E->C: 1,25)和(D->B->E->C: 1,20)。对于每个路径，路径旁边的第一个数字是支持计数，第二个数字是路径效用，它等于{D}.nu。这些路径被收集到{D}的条件模式库[3]中，记为{D}-CPB，如表5所示。 In this table, the collected paths are shown in the first column; the support counts and the path utilities of the paths are shown in the third and the forth columns, respectively. For convenience, the path ({ai}- >{ai+1}->...->{an}) in the conditional pattern base is denoted as {ai, ai+1,..., an} and the item ai is discarded from the path in {ai}’s conditional pattern base since every path in {ai}-CPB must contain ai |
定义9。(条件模式库中路径的路径实用程序) |
| 在{ai}- cpb中路径pj = ({ai}->{ai+1}->…->{an})的路径效用等于{ai}。nu，记为pu(pj， {ai}- CPB)。例如，在表5中，路径{AC}在{D}-CPB中的路径效用为8。 |
定义10。(条件模式库中路径中项的路径实用程序) |
| 对于{ai}-CPB路径pj中的每一项ip， {ai}-CPB路径pj中的每一项ip的路径效用等于pu(pj， {ai}-CPB)，记为pu(ip, pj)。例如，路径{AC}中{A}的路径效用为8。 |
定义11。(条件模式库中项的路径实用程序) |
{ai}-CPB中项ip的路径效用定义为: 记为pu(ip， {ai}-CPB)。例如，{D}-CPB中{A}项的路径效用等于(pu({A}， {AC}) + pu({A}， {BAEC})) =(8 + 25) = 33。 |
定义12。(条件模式库中的局部有希望项) |
| 如果pu(ip， {ai}-CPB) ?? ?min_util;否则，IP被称为本地无前途的项目。 |
| 例4。通过扫描{D}-CPB一次，可以获得项目及其路径实用程序，如表6所示。在表6中，item {A}是一个本地无前途的item，因为它的路径效用小于min_util，即33<40。然后将局部有希望项{B}、{C}和{E}排列到局部报头表中。再次扫描{D}-CPB，构造{D}的条件UPTree[5]，记为{D}-Tree。当检索条件模式库中的路径时，将从路径中删除没有希望的项，并根据其本地路径实用程序按降序重新排列其余项。重组后的路径如表5的第二列所示。插入所有重组路径后，完整构造{D}- Tree，如图4(a)所示。应用FP-Growth从{D}-Tree生成phui，得到一组与{D}项相关的phui，即{{D}:58， {DE}:45， {DEB}:45， {DEC}:45， {DEBC}:45， {DB}:45， {DBC}:45， {DC}:53}。考虑全局表头表中的下一项，即{B}，它以同样的方式派生了一组phui，其中包括项{B}，即{{B}:61 {BE}:54， {BEC}:54， {BC}:54}。考虑头表中的其余项，我们可以得到其余的phui，即{{A}:65， {AC}:55， {ACE}:47， {AE}:47， {E}:88， {EC}:76， {C}:96}。 After finding all PHUIs high utility itemsets and their utilities are identified from the set of PHUIs by scanning original database once. |
删除构造Tree中的节点实用程序 |
| 如例5所示，高效用项集的搜索空间可以分为5个较小的搜索空间:(1){D}-CPB， (2) {B}-CPB，不包含项目{D}; (3) {A}-CPB，不包含项目{B}和{D}; (4) {E}- CPB，不包含项目{A}、{B}和{D}; (5) {C}-CPB，不包含项目{E}、{A}、{B}和{D}。当应用DGU策略时，在{B}-CPB中有两条路径{AEC}: 25和{EC}: 29，路径旁边的数字是它们的路径效用。虽然{D}没有出现在{B}的条件模式库中，但{D}的效用涉及到{B}-CPB中路径的路径效用。路径{AEC}的路径效用为25，等于重组事务T3 '的RTU。这个估计效用值实际上是u({B}， T3 ')， u({D}， T3 ')， u({A}， T3 ')， u({E}， T3 ')和u({C}， T3 ')的和。 |
| 但是，{B}-CPB中的所有路径都与{D}无关，因为在UP-Tree中，{D}在{B}下面，如图2所示。此外，只有节点{B}的祖先项才会出现在{B}-CPB中。任何节点{B}的子代项都不会出现在{B}-CPB中。因此，{B}的后代的实用程序可以从{B}-CPB中每个路径的路径实用程序中删除。这个过程可以在构建全局UP-Tree的过程中完成，因为条件模式库中的路径是直接从全局UP-Tree派生出来的。当一个重组事务tj ' = {i1, i2，…，in} (ik?Insert_Reorganized_Transaction(n, ix)函数取树中的节点n和项ix (ix?Tj '， 1≤x≤n)在重组事务Tj '中作为输入。 |
| 例6。考虑表4中的重组事务。当T1 ' = {(C,1) (A,1) (D,1)}插入到全局UP-Tree时，将创建第一个节点{C}。{C}。nu的增加是T1 '的RTU减去T1 '中项目{C}后面的其他项目，即{C}的效用。ν= RTU (T1) - (u({一},T1) + u ({D}, T1)) = 8 -(5 + 2) = 1。为方便起见，也可以认为是T1 '中在{D}之前的项目的效用之和，即{C}。nu = p({C}) × q({C}， T1 ') = 1×1 = 1，其中p({C})为商品{C}的单位利润，q({C}， T1 ')为T1 '中{C}的购买量。第二个节点{A}用{A}填充。count = 1和{A}。ν= (p ({C})×({C}, T1) + p({一})×({},T1)) =(1×1 + 5×1)= 6。第三个节点{D}使用{D}创建。count = 1和{D}。nu = (p({C}) × q({C}, T1’) + p({A}) ×q({A}, T1’) + p({D}) × q({D}, T1’)) = (1×1 + 5×1 + 1×2) = 8. When T2’ = {(C, 6) (E, 2) (A, 2)} is inserted into the tree, {C}.nu is increased by p({C}) × q({C}, T2’) = 6 and {C}.count is increased by 1. Then, a new node {E} is created under the node {C} with {E}.count = 1 and {E}.nu = 12. Similarly, a new node {A} is created under the node {E} with {A}.count = 1 and {A}.nu = 22. After inserting all reorganized transactions, the global UP-Tree is constructed completely. Figure 3 shows the global UP-Tree. By Figure 3, we can know that the node utility of each node is significantly reduced. Generating PHUIs from the UP-Tree by applying FP-Growth, and we obtain a set of PHUIs, that is, {{D}:58, {DE}:45, {DEB}:45, {DEBC}:45, {DEC}:45, {DB}:45, {DBC}:45, {DC}:53, {B}:61, {A}:65, {E}:88, {C}:96} |
结论 |
| 从事务数据库中挖掘高效用项集。针对高效用项集信息的维护，提出了树结构。因此，只需对数据库进行两次扫描，就可以从这个Tree中高效地生成高效用项集。这提高了效用挖掘的挖掘性能。在实验中，我们用合成数据集和真实数据集来评估我们算法的性能。该策略有效地减小了搜索空间和候选数，极大地提高了挖掘性能。当数据库包含大量长事务时，挖掘性能会提高。 |
表格一览 |
|
|
|
|
数字一览 |
 |
 |
| 图1 |
图2 |
|
参考文献 |
- 阿格拉瓦尔和斯里康德。，“Fast algorithms for mining association rules” In Proc. of the 20th Int'l Conf. on Very Large Data Bases, pp. 487-499, 1994.
- 朴志生，陈敏生，陈培生。于，“一种有效的基于哈希的关联规则挖掘算法”(Apriori算法)，SIGMODConference, 1995。
- 韩俊，裴俊杰，尹玉林，毛荣荣，“无候选生成的频繁模式挖掘”(FP-Tree Method)，中国计算机科学，2000。
- 刘，廖文，乔杜里。，“A fast high utility itemsets mining algorithm.” In Proc. of the Utility-Based Data Mining Workshop,2005.
- ”研究。李,js。是的，还有张c.c。，“Isolated items discarding strategy for discovering high utility itemsets” In Data & KnowledgeEngineering, Vol. 64, Issue 1, pp. 198-217, Jan., 2008.
- 姚海华，H. J. Hamilton，耿L.，“基于效用度量的挖掘项目集的统一框架”，《基于效用的数据挖掘第2届研讨会论文集》，第28-37页，美国，2006年8月。
- 滕文生，吴成伟。，“UP-Growth : An Efficient Algorithm for High Utility Itemset Mining”, In Proc. of the 16th ACM Int'l Conf.on knowledge discovery and data mining.
- C. F.艾哈迈德，S. K.坦比尔，b.s.。郑某和y.k。李。“基于树结构的增量数据库高效用模式挖掘方法”，《知识与数据工程学报》，第21卷，第12期，pp. 1708-1721,2009
- h。Yao, h。j。Hamilton和c。j。Butz。，“A Foundational Approach to Mining Itemset Utilities from Databases,” in Proc. Fourth SIAM Int’lConf. Data Mining (SDM ’04), pp. 482-486, 2004.
- J.-L。Koh和s.f。Shieh，，“一种基于调整fp -树结构的关联规则维护的有效方法”，第九届国际会议，高级应用数据库系统。
|
菜单
例如,你(T1) = u ({}, T1) + u (C {}, T1) + ({D}, T1) = 5 + 1 + 2 = 8。
例如，twu({AC}) = tu(T1) + tu(T2) + tu(T3) = 8 + 27 + 30 = 65。
记为pu(ip， {ai}-CPB)。例如，{D}-CPB中{A}项的路径效用等于(pu({A}， {AC}) + pu({A}， {BAEC})) =(8 + 25) = 33。
