本研究主要探討在給定產品概念階層下，採擷跨階層間的關聯規則。 過去的研究中大多採用Apriori為基準的演算法，稱之為CL_Apriori，來進行跨階層的關聯規則採擷，CL_Apriori演算法主要是依由上而下且逐層的方式進行採擷，然而，面對產品的概念階層不僅必須考量不同階層的品項，更因不同階層有著不同的最小門檻值(minimum support threshold)必須考量，故過去的方法不僅在採擷的效率上不彰，更無法採擷出完整的跨階層關聯規則。 本研究提出以FP-tree演算法為基準的演算法，稱之為CL_FP-tree演算法，利用由下往上同時合併考量的方式來採擷跨階層的關聯規則，更依照不同的資料儲存型態提出不同的頻率值(support)計算方法。利用FP-tree為基準的演算法不僅能節省資料掃掠的時間更能完整的採擷出關聯規則。我們首先透過資料庫的掃掠建立產品的概念階層，並且計算概念階層中每個品項的頻率值；進一步蒐集頻率值大於最小門檻值的品項，稱之為常發生的品項(frequent item)，並利用常發生的品項建立CL_FP-tree；最後藉由CL_FP-tree Growth來進行跨階層關聯規則的採擷。 研究中透過實際資料的驗證，證實CL_FP-tree演算法比CL_Apriori演算法更有效率的採擷並且能採擷出更多的跨階層的關聯規則。 We study a cross-level association rule mining, given a concept hierarchy of all products sold in a retailer. Some association rules of interest may occur between two different levels, which are usually difficult to find in terms of number of database scans or computing effort. Previous techniques for mining cross-level association rules are mostly top-down, progressive depending method extended from Apriori algorithm. This approach results in worse mining efficiency and incompleteness of mined rules. In this research, we propose a bottom-up, simultaneously merging method based on FP-tree, called CL_FP-tree, to improve the mining efficiency and completeness of mining cross-level association rule. According to the concept hierarchy attributes and different ways for storing the transaction data, we propose different ways to count the support of items at each concept hierarchy level. CL_FP-tree aims to reduce the number of database rescans which are seemingly inevitable as we need to have the cross-level information. After constructing the CL_FP-tree, the application of the known FP-growth algorithm for mining cross-level association rule is then straightforward. We implement the FP-tress based algorithm, CL_FP-tree algorithm, with real data and compare it with Apriori based algorithm, CL_Apriori algorithm. We observe that CL_FP-tree algorithm can mine out more interesting and potential cross-level association rules and more efficient than CL_Apriori algorithm. Besides, we analyze various exceptional conditions as we apply real data to mine cross-level association rules and find out some important and interesting factor.
