提高数据仓库位图索引的效率

摘要

目前,在频繁项目集挖掘处理上已经发展的比较成熟,并在常规数据库中得到了应用。然而这种仅对频繁集的挖掘并没有多大的指导意义,因为这种挖掘只反映了数据库中包含该项目集交易数量,它不能真实的反映那些能衡量成本效益或者其他的用户偏好的项目集中。同时频繁项目集往往只贡献了总利润的小部分,而非频繁项集则占了大部分的利润比例。
　　 通常数据集里蕴含着不同价值的数据信息,一个零售企业的兴趣更多的集中在一些最有价值的客户(企业主要利润来源的客户)身上。因此频率不能充分的回答那个项目集是高利润的项目集而那个项目集是具有重要影响的项目集这一问题。在大量重要的数据挖掘任务中,如关联规则挖掘和长模式,新兴的模式和依赖规则挖掘等。从负项集中发现高利用价值项无论是在理论还是实践中都起着至关重要的作用。效用挖掘的目标是利用负项集找出实用价值高的项目集,这些项目集占了总效用的很大一部分。本研究的目的是通过效用挖掘以识别出高利用价值的数据集。在先前的一些应用中,数据集的价值都是来自具有正相关效用的数据集,然而数据集可能具有负相关的价值。从负相关的数据集中发现具有高价值的数据项,对于兴趣挖掘模式来说是一个重要的处理过程,像利用关联规则从大规模数据库中的挖掘。同时实现从负相关的数据项中挖掘实用价值高的数据集是一件有利的、意义重大的研究,我们的贡献是能利用很少的计算资源有效的挖掘出高价值的数据集。通过这种方法,利用负相关项能有效的挖掘出高价值数据集,且仅需要很少的内存空间。
　　 本文的目标是提出一个利用负项相关集挖掘出高利用价值数据集的高效算法,我们的算法HUIWNIV-Mine将聚焦在通过使用不带负值交易的项目集,减少候选项目集和CPU的I/O上来加快响应时间,本质上就是在一个大型交易数据库中消除负项值。
　　 为了理解HUIWNIV(High Utility Itemsets With Negative Item Values)的思想,我们通过例子来说明。例如：许多超市可能举行一些购买特殊商品获赠其他商品的促销活动,以吸引顾客,而那些免费赠送的商品对于超市来说就是负项集(也就是没有利润获得反而亏损的商品)。然而,超市可能从其他交叉促销商品项中获得更高的利润。这种做法很常见。例如,如果一个消费者买了4项A,他将同时获得免费赠送的一个B。假设超市买出一个A获得4美元的利润,赠送一个B损失3美元。尽管赠送一个B导致超市损失了3美元,但是能从交叉促销商品A中赚16美元。最终超市从本次促销中获得了13美元的利润。
　　 我们可以定义数据项目集X的效用为u(X),它代表包含X的所有交易的总和。效用挖掘的目标是要找出高实用性的项目集,这些项目集占了总效用的很大一部分。传统的关联规则挖掘模型假设每项的效用总为1并且销售量为0或1,因此这只是效用挖掘中一种特殊情况。而在真正的效用挖掘中的每个项的效用和销售量可以为任意值。如果u(X)比指定的效用门限好,X则为高效用项目集;否则为低效用项目集。
　　 HUIWNIV-Mine算法在数据库中利用一个阈值来处理产生的交易权重效用值。该算法能舍弃一些低价值数据集,但是不会遗漏任何的高价值的数据集,数据集中的每个负相关的数据项将不会是高价值数据集。在产生的数据集中至少有一个数据项是有正价值的,或者需要的数据集不必去扫描数据库,因此,HUIWNIV-Mine算法通过一些数据项能输出真正的具有高交易权重效用的候选数据集。
　　 HUIWNIV-Mine算法的新颖性在于它能有效的通过负相关集挖掘出高利用价值的数据集,同时只需要少量的处理利用率,像在大规模数据库中挖掘出高价值的数据集,且能减少执行时间。HUIWNIV-Mine在含有负相关项的大规模数据库中挖掘出高价值的数据集中有很好的应用前景。

目录

文摘

英文文摘

论文说明:LIST OF FIGURES、LIST OF TABLES

CHAPTER 1:INTRODUCTION

1.1 Statement of Problem

1.1.1 Definition(Utility Mining)

1.1.2.Definition The transaction utility value in a transaction

1.1.3.Definition.The external utility value

1.1.4.Definition (Utility Table)

1.1.5.Definition A utility function f (o,s)

1.1.6.Definition The utility of an item iq in a transaction Tq

1.1.7.Definition A k-itemset

1.1.8.Defmition The local utility

1.1.9.Definition The utility of an itemset X

1.2.Theoretical Model of Utility Mining

1.2.1 Goal of utility mining

1.3.Motivation and Contribution of the Thesis

1.4.Outline of the Thesis

CHAPTER 2: PERFORMANCE ISSUES OF EFFICIENTLY MINING HIGH UTILITY ITEMSETS WITH NEGATIVE ITEM VALUES FROM LARGE DATABASES

2.1 Background

2.2. SOME ALGORITHMS AND APPLICATION

2.2.1 Apriori Algorithm

2.2.2. Algorithm FUP

2.2.3. Algorithm FUP2

2.2.4 Algorithm UWEP(Update With Early Pruning)

2.2.5. Algorithm FTP-DS

2.2.6. Algorithm RAM-DS

2.2.7 Algorithm SWF and CET

2.2.8 Algorithm MEU 20

2.2.9 Algorithm Two-Phase

2.2.10 Algorithm THUI(Temporal High Utility Itemsets)

CHAPTER 3: PROPOSED ALGORITHM(HUINIV)-MINE

3.1.Basic concept of HUIWNIV-Mine

3.2.An example of mining high utility itemsets with negative item values

3.3.HUINIV-Mine Algorithm

CHAPTER 4: EXPERIMENTAL RESULTS

4.Experimental evaluation

4.1.Evaluation of number of generated candidates

4.2.Evaluation of execution time

4.3.Scale-up on incremental mining

4.4.Evaluation with real data

CHAPTER 5: CONCLUSIONS AND FUTURE WORK 52错误！未定义书签。

REFERENCES

ACKNOWLEDGEMENTS

APPENDIX B: PUBLISHED PAPER