臺灣博碩士論文加值系統

傳統的關聯規則中，只能知道找出銷售物品之間的相關規則，得知那些商品是顧客經常一起購買的，但沒有辨法了解這些被銷售的物品和賣場貨架之間相關性。而在商品之間有規聯的背後隱藏是，商品之間在空間架位上的距離上夠近，讓顧客能產生聯想，提高消費者的購買欲望。例如我們並沒有辨法找出啤酒和尿布在賣場上架位的距離所造成的影響，也許放靠近一點會增加銷售，也許遠一點會降低銷售。
在本研究中我們將納入”空間架位”這個新的維度進來。為了了解商店的架位位置對產品的銷售有什麼的影響，在後面一章節中我們會發展了一些方法用來找出這些空間上的樣式，與尋找一些較好的和較壞的商品擺放位置，因此我們可找到一些相當有趣的樣式出來。例如，在日常生活用品區的馬桶刷和食物區的牛奶、餅乾如果過於靠近的話，也許會降低消費者的購買欲望。因此商品的架位位置對產品之間的銷售有一定程度的影響，我們想要了解什麼樣的商品陳列方式最能吸引消費者的目光? 什麼樣的商品組合方式最能被大家所接受? 怎麼樣的架位安排能讓產品賣得比較好? 在本研究中會提出AprioriLJ演算法出來用來解決上面所呈述的問題，AprioriLJ只需要掃描資料庫一次並同時記錄每一個物品交易次數與交易的編號，並由商品所擺放的架位歷史資料中取得商品在某個時間區間所擺放的位置，由空間和時間上的交集我們可以得具有架位空間上關係的樣式。

Traditional Association rule can’t find the location relation between sold trade article. Sometimes, the sale of beer and diaper highly in the store ,lowly in another store. We can’t understand the space relationship between each article. In this thesis, the issue of mining location relation is studied. We adopt the location issue. In order to understand the relationship of each article between location and sale. We develop Apriori-LJ to solve these problem, it just needed scan database once and record the transaction id. Find the cross common part between location simultaneously, then we can find the location pattern.

第一章緒論..................................................................................................................1
第二章問題描述與相關定義................................................................................5
第一節問題描述................................................................................................5
第二節定義........................................................................................................5
定義2.1 時間Time ...................................................................................5
定義2.2 物品Item ....................................................................................6
定義2.3 物品擺放位置............................................................................6
定義2.4 架位歷史表................................................................................7
定義2.5 物品之間的關係........................................................................8
定義2.6 Item Set ......................................................................................9
定義2.7 架位樣式資料庫d......................................................................9
定義2.8 架位樣式..................................................................................10
定義2.9 架位樣式之間關係..................................................................12
定義2.10 架位樣式擺時間......................................................................14
定義2.11 Pattern Basis.............................................................................14
定義2.12 Global Support.........................................................................15
定義2.13 P-Global Support .....................................................................15
定義2.14 Actual Support .........................................................................16
定義2.15 Strength ....................................................................................16
第三章架位樣式規則的挖掘....................................................................................17
3.1 找出L1 及建立TID AVL Tree .................................................................20
3.2 C2 的產生.................................................................................................22
3.2.1 時間區間交集合併策略....................................................................23
3.2.2 物品之間關係....................................................................................24
3.2.3 計算樣式交易次數............................................................................25
3.3 找出高頻率樣式.........................................................................................28
3.4 Candidate itemset 的產生.............................................................................30
3.4.1 樣式關係組成....................................................................................32
3.4.2 時間區間交集合併策略....................................................................36
3.4.3 計算樣式交易次數............................................................................37
3.5 範例說明.....................................................................................................38
第四章實驗模擬........................................................................................................43
4.1 實驗設計.....................................................................................................43
4.1.1 環境描述............................................................................................43
4.1.2 交易資料之產生................................................................................43
4.2 參數調整.......................................................................................................46
4.3 實驗結果.......................................................................................................47
4.3.1 DB Scale up ...................................................................................47
4.3.2 交易時間........................................................................................48
4.3.3 物品個數........................................................................................49
4.3.4 平均交易長度(T) ........................................................................50
4.3.5 潛在Large itemset 的平均長度(I)............................................50
4.3.6 P_GlobalSupport............................................................................51
4.3.7 架位上H、M、L 的比例...........................................................52
4.3.8 架位上H、M、L的平均次數.....................................................53
4.3.9 變動和不變的層數........................................................................54
4.3.10 Negative and Positive Strength......................................................55
第五章結論與建議....................................................................................................56
參考文獻......................................................................................................................58

[AIS93]Rakesh Agrawal, Tomasz Imielinski, and Arun Swami, “ Mining Association Rules Between Sets of Items in Large Databases” Proceedings of the ACM SIGMOD International conference on Management of Data, Pages 207-216, 1993.
[AR00]Juan M. Ale, Gustavo H. Rossi, “ An Approach to Discovering Temporal Association Rules”, Proceedings of the 2000 ACM symposium on Applied computing 2000 (volume 1), Pages 294-300, 2000.
[AS94]Rakesh Agrawal, Ramakrishnan Srikant, “ Fast Algorithms for Mining Association Rules, ” Proc. of the 20 th VLDB Conference Santiago, Chile, 1994.
[AS95]R. Agrawal and R. Srikant, “ Mining Sequential Patterns, ” Proceedings of the 7th International Conference on Data Engineering, pp. 3-14, 1995.
[BL99]J. Borges and M. Levene, “ Mining Association Rules in Hypertext Databases, ” Knowledge Discovery and Data Mining, 1999.
[FPM91] W. J. Frawley, G. Piatetsky-Shapiro and C. J. Matheus. Knowledge Discovery in Databases:An Overview, AAAI/MIT press, 1991.
[HDY99]J. Han, G. Dong, and Y. Yin, “ Efficient Mining of Partial Periodic Patterns in Time Series Database, ” Proceedings of the 15th International Conference on Data Engineering, pp. 106-115, 1999.
[HF99]J. Han and Y. Fu, “ Mining Multiple-Level Association Rules in Large Databases, ” IEEE Transactions on Knowledge and Data Engineering, vol. 11, no. 5, pp. 798-805, 1999.
[SSTE00] Michael J. Shaw, Chandrasekar Subramaniam, Gek Woo Tan and Michael EWelge. Knowledge management and data mining and data mining for marketing. Decision Support Systems, 31, (1):127-137, May, 2001.
[BMUT97]S, Brin, R. Motwani, J. Ullman, and S. Tsur, “ Dynamic Itemset Counting and Implication Rules for Market Basket Data, ” ACM SIGMOD Conf. Management of Data, May 1997.
[HPY00]J. Han, J. Pei, and Y. Yin. “ Mining Frequent Patterns without Candidate Generation, ” Proc. 2000 ACM-SIGMOD Int. Conf. on Management of Data (SIGMOD'00), Dallas, TX, May 2000.
[JA99]R. J. Bayardo Jr. and R. Agrawal, “ Mining the Most Interesting Rules, ” In Proc. of the 5th ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining, Aug. 1999.
[KFW98]C.M. Kuok, A.W. Fu, M.H. Wong, “ Mining Fuzzy Association Rules in Databases, ” SIGMOD Record, vol. 27, no. 1, pp. 41-46, 1998.
[KH95]K. Koperski and J. Han, “ Discovery of Spatial Association Rules in Geographic Information Databases, ” Proc. 4th Int'l Symp. on Large Spatial Databases (SSD95), Maine, pp. 47-66, Aug. 1995.
[LAS97]B. Lent, R. Agrawal and R. Srikant, “ Discovering Trends in Text Databases, ” Proc. of the 3rd Int'l Conference on Knowledge Discovery in Databases and Data Mining, Newport Beach, California, August 1997.
[LFH00]H. Lu, L. Feng, and J. Han. “ Beyond Intra-Transaction Association Analysis: Mining Multi-Dimensional Inter-Transaction Association Rules, ” ACM Transactions on Information Systems, vol. 18, no. 4, pp. 423-454, 2000.
[LHL99]S. Li, S. Hong, and C. Ling, “ New Algorithms for Efficient Mining of Association Rules, ” Information Sciences, vol. 118, no. 1-4, pp. 251-268, Sep. 1999.
[PBTL99]N. Pasquier, Y. Bastide, R. Taouil, and L. Lakhal, “ Efficient Mining of Association Rules Using Closed Itemset Lattices, ” Information Systems, vol. 24, no. 1, pp. 25-46, Mar. 1999.
[PCY97]J.-S. Park, M.-S. Chen, and P. S. Yu, “ Using a Hash-Based Method with Transaction Trimming for Mining Association Rules, ” IEEE Trans. on Knowledge and Data Engineering, vol. 9, no. 5, pp. 813-825, Oct. 1997.
[PHMZ00]J. Pei, J. Han, B. Mortazavi-Asl, and H. Zhu, “ Mining Access Pattern Efficiently from Web Logs, ” Pacific-Asia Conference on Knowledge Discovery and Data Mining, pp. 396-407, 2000.
[RS98]R. Rastogi and K. Shim, “ Mining Optimized Association Rules with Categorical and Numeric Attributes, ” the 14th International Conference on IEEE Data Engineering, Orlando, Florida, 1998.
[SA96]R. Srikant, R. Agrawal: “ Mining Quantitative Association Rules in Large Relational Tables, ” Proc. of the ACM-SIGMOD 1996 Conference on Management of Data, Montreal, Canada, June 1996.
[T93]Tansel, A. et al: Temporal Databases: Theory, Design, and Implementation. Benjaming/Cummings.1993.
[T96]H. Toivonen, “ Sampling Large Databases for Association Rules, ” the 22-th International Conference on Very Large Databases (VLDB'96), pp. 134-145, Mumbay, India, September 1996.
[Z98]M.J. Zaki, “ Efficient Enumeration of Frequent Sequences, ” 7th International Conference on Information and Knowledge Management, pp 68-75, Washington DC, Nov. 1998.
[ZHLH98]Osmar R. Za□ane, Jiawei Han, Ze-Nian Li, Jean Hou.,“ Mining Multimedia Data, ” Proc. CASCON'98: Meeting of Minds, Toronto, Canada, November 1998
[Z00]M.J. Zaki, “ Scalable Algorithms for Association Mining, ” IEEE Trans. on Knowledge and Data Engineering, vol. 12, no. 3, pp. 372-390, May-June 2000.