Intelligent Agents for Data Mining and Information Retrieval [Electronic resources] نسخه متنی

PATTERN MATCH ANALYSIS

While exploiting and researching the Market Basket Data Analysis System Based on Mining Associations Rules, we analyzed the pattern match included in mining association rules. We discovered some characteristics of the transaction data set and the set of candidates:

Recording the item number and index can reduce the comparison time and enhance the efficiency of pattern match. Sort all the items of each transaction in the transaction data set alphabetically. When preprocessing the transaction data set, do the sort, record the item number of each transaction and set it as an index. Then, choose a suitable algorithm to generate the k-itemsets. We get alphabetized k-itemsets which match.

The itemsets in the set of candidates can be alphabetized, not only in row, but also in a column. The set of candidate k-itemsets generated by the join and prune steps, based on the set of candidate (k

− 1)-itemsets and C_1, is alphabetical. Then, through the SQL language as follows, we can get the alphabetic set of candidate k-itemsets in a row and in a column:

INSERT INTO Ck
SELECT TOP 100 PERCENT dbo.p.col1, dbo.p.col2,..., dbo.p.colk
− 1, q. colk
− 1 AS colk
FROM dbo.lk
− 1 p INNER JOIN dbo.lk
− 1 q
ON dbo.p.col1=q.col1 AND dbo.p.col2=q.col2 AND ... AND dbo.p.colk
− 1<q.colk
− 1
ORDER BY P.col1, P.col2,..., P.colk
− 1, Q.colk
− 1

We can deal with the pattern match by the alphabetic characteristic. For two alphabetic linear objects, we can find the most efficient lookup algorithm to realize match easily. Then, we should look for a suitable algorithm to transform the alphabetic pre-match object into an alphabetic linear object. The simplest transformation method is to set the item number as weight and add up k-itemsets with weight as the object of match.

The item number of the longest itemset in a transaction data set is far less than the total item number |I|, and the transactions having longer itemsets take up only a small part of the total transactions. When researching the market data set, which has 15,169 pieces of merchandise divided into 228 kinds of ware, we processed the mining based on 228 items, that is |I|=228. We discovered that the item number of the longest transaction in the transaction data set is 33; 0.098 percent of the transactions have an item number larger than 20; 0.62 percent have an item number larger than 15; and 3.9 percent have an item number larger than 10.

The matching data object is larger, and the matching success ratio is lower. When the k-itemsets number of each transaction in the transaction data set is larger, or when the transaction item number is larger, the itemset number of the set of candidates is larger. Then, the matching success ratio is lower. Owing to match being a process of lookup in nature, we can choose an algorithm which fits the match characteristic. In this chapter, that algorithm is bisearch, which has an average comparison time of log₂n (n is the length of the object) and, therefore, can improve the efficiency.

The match proceeded between two alphabetical objefound that the k-itemsets number of each transaction in the transaction data set, when k went from 1 to some scale, was always less than, or far less than, the itemsets number of the set of candidates. But above the scale, the k-itemsets number of each transaction in the transaction data set was more than the itemsets number of candidates. The results show determine data object should be applied to match the other one between the transaction data set and the set of candidates. But what's the determining principlecy.