KR20080026943A - Method for association rule mining - Google Patents

Abstract

An association rule mining method is provided to reduce an execution time by mining association rules on the basis of an ARCS(Association Rule mining in Compressed Space) algorithm. An association rule mining method comprises the following several steps. Items of all the transactions in an original transaction database are counted and a header table(310) is generated. The items of all the transactions in an original transaction database are recounted, are compared with items of the header table, and are registered at a filtered transaction if the recounted items of the transactions are the same as those of the header table. Filtered transactions are counted and a compressed transaction(320) is generated. The items registered at the filtered transaction are connected to the header table.

Description

Method for Association Rule Mining}

1 is an embodiment of a prior art FP-data structure,

2 is an embodiment of a prior art H-data structure,

3 is an embodiment of a CT-data structure according to the present invention;

4 is an embodiment of conditional header table generation using an ARCS algorithm according to the present invention;

5 is another embodiment of conditional header table generation using an ARCS algorithm according to the present invention;

6 is a diagram illustrating a search path for finding all frequent item sets in an ARCS algorithm according to the present invention.

Figure 7 is a graph showing an embodiment comparing the conventional rules exploration method according to the present invention.

Figure 8 is a graph showing another embodiment comparing the related art rule search method according to the present invention.

Figure 9 is a graph showing another embodiment comparing the conventional rules exploration method according to the present invention.

<Description of the symbols for the main parts of the drawings>

310: header table 320: compressed transactions

The present invention relates to a method for exploring association rules, and more particularly, to process a large amount of data by using a small amount of storage space using a CT-data structure, and to reduce execution time by exploring association rules using an ARCS algorithm. It is about exploration of association rules.

Association rules are useful patterns that are expressed as condition-results between items of data. Exploration of the rules of association is most widely used in corporate activities, especially in marketing. For example, a customer who buys diapers on Thursday in a supermarket in the United States has found a link to buying beer at the same time. At this time, the condition is 'Thursday, diaper' and the result can be referred to as 'beer'. The exploration of these rules allows the development of computer technology. When customers check out at the supermarket checkout, the items in the shopping cart are entered into the database in the form of a computer via a bar code, from which they can analyze their purchasing behavior. At this time, the information of a customer is called a transaction, and a lot of transactions are analyzed to find out the rules that appear frequently and use them for marketing. For example, the above diaper-beer rules can be used to increase sales by displaying diapers and beer in close proximity. These association rules are generated using probabilities such as Evidence Probability, Confidence Probability, and Lift. It is also actively used in scientific research fields.

Association rule exploration is a method of finding associations between items included in a transaction and is the core of a knowledge discovery system based on self-learning. The association rule exploration problem is divided into finding the frequent itemsets, which are sets of items having transaction support above the minimum support level, and generating association rules from them. As the number of items and transactions to be observed increases, the number of calculations required for analysis increases exponentially, and the size of the storage structure required increases drastically. Therefore, in order to perform association rule search on a large amount of data at high speed, an algorithm considering both storage space and execution time is required.

Prior art FP-growth algorithms use FP-trees that use the same node for prefix entries that are common to the header table for a sorted set of transactions in a transaction database. Use an FP-struct consisting of FP-growth uses a pattern-growth method from FP-data structures to detect frequent item sets without generating and testing candidate frequent item sets.

Table 1 shows a set of filtered transactions sorted in descending order of frequency when the original transaction database and minimum support are 3.

Table 1. Filtration transaction set aligned with transaction database

TID Transactional database Filtered transaction set sorted in descending order by frequency 100 f, a, c, d, g, i, m, p <f, c, a, m, p> 200 a, b, c, f, l, m, o <f, c, a, b, m> 300 b, f, h, j, o <f, b> 400 b, c, k, s, p <c, b, p> 500 a, f, c, e, l, p, m, n <f, c, a, m, p>

1 is an embodiment of a prior art FP-data structure, which is generated using the transaction data of Table 1 above. After exploring the frequent itemsets, the conditional FP-tree and the header table 110 for each item of the header table 110 are split and generated until the FP-tree 120 is configured as a single path. All combinations of items and each tree node find a frequent set of items. For example, to find all frequent itemsets that include item m, the conditional pattern sets of item m are {(f: 2, c: 2, a: 2), (f: 1, c: 1, a : 1, b: 1)} yields a conditional FP-tree {(f: 3, c: 3, a: 3)} | m of m. The combination of m's conditional FP-tree and m finds all frequent itemsets including m.

FP-growth is a waste of space and time due to the generation of repetitive conditional FP-trees and header tables when frequent itemsets are found. In addition, when data density is low or minimum support for the same data is very low, the compression rate of the FP-tree may be low, resulting in a larger FP-data structure than the original transaction database.

Another prior art H-mine algorithm generates an H-data structure consisting of header tables and frequent projections for a filtered set of transactions, and then uses a pattern-growth method to generate candidate frequent item sets without frequent occurrence and testing. Find a set of items. Each item in the header table consists of a name, frequency, and a link, and an item in a frequent projection view consists of a name and a link. While FP-growth repeatedly generates conditional FP-data structures, H-mine generates only conditional header tables repeatedly, using H-data structures at low data densities, and FP-data structures at high FP-data structures. Create a frequent item set by generating.

Figure 2 is an embodiment of the prior art H-data structure, which is similarly generated using the transaction data of Table 1 above. If a frequent item set is found, if the set of links to that item is incomplete, backtracking is needed to search the queue of previous items to find the missing links. In order to find all the frequent item sets including 'c' in FIG. 2, since there is only one link to 'c', the queue of the previous item 'f' is searched again to find and connect the remaining three links. Conduct an exploration on 'c'

H-mine is not only difficult to provide a clear standard for input data density, but also has a high density, which implies the disadvantage of FP-growth. When H-mine is used, H-mine has a compression effect. Can not get. In addition, when using the H-data structure, there is a problem of waste of storage space due to unused link space and backtracking if there is a lack of link to the corresponding item during the frequent item set discovery process.

Accordingly, an object of the present invention is to solve the problems of the prior art, and to achieve a large amount of data by using a small amount of storage space using a CT data structure.

In addition, there is another purpose to reduce the execution time by exploring the association rules using the ARCS algorithm.

An object of the present invention is the first step of identifying items of all transactions in the original transaction database; Adding the identified first item if it is not present in the header table, and increasing the frequency by one; A third step of deleting if the first item of the header table does not satisfy the minimum support level; A fourth step of reconfirming the items of all transactions in the original transaction database; A fifth step of adding the checked second item to the filtered transaction if the header table exists; Adding the filtered transaction if it is not in the compressed transaction and increasing the frequency by one; And a seventh step of connecting a link to the header table when the second item added to the filtered transaction is the first item.

Another object of the present invention is a first step of identifying all items of the root header table; Generating a frequent item set of the identified first items; Reading all the compressed transactions indicated by the first item and generating a conditional header table of the first item; A fourth step of deleting items that do not satisfy the minimum support among the generated items of the conditional header table and generating a frequent item set of the second items that satisfy the minimum support; And a fifth step of reading all the compressed transactions indicated by the second item satisfying the minimum support, and generating a conditional header table of the second item.

Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings. Prior to this, terms or words used in the specification and claims should not be construed as having a conventional or dictionary meaning, and the inventors should properly explain the concept of terms in order to best explain their own invention. Based on the principle that can be defined, it should be interpreted as meaning and concept corresponding to the technical idea of the present invention.

Therefore, the embodiments described in the specification and the drawings shown in the drawings are only the most preferred embodiment of the present invention and do not represent all of the technical idea of the present invention, various modifications that can be replaced at the time of the present application It should be understood that there may be equivalents and variations.

Compressed Transactions (CT) data structure consists of Compressed Transactions and a header table. Compressed transactions that do not change during exploration consist of as little information as possible, and the rest of the information is designed to be included in header tables that can be created / deleted during exploration. Compressed transactions are represented as a two-dimensional string array consisting of only item names. For filtered transactions composed of common items, they are represented as one compressed transaction along with the frequency of transactions. The header table consists of a set of items, and each item consists of item name, frequency, and transaction link set.

In the case of FP-data structure, if the data density is high or if the support for the same data is high, the number of nodes in the FP-tree is reduced, which uses less space. Otherwise, the nodes constituting the FP-tree have different sizes. It uses a lot of space because it is relatively large compared to the data structure. H-data structure uses less size than FP-tree node, but there is no compression function, and since each node of frequent projection is composed of item name and node link, waste of storage space is caused by unused link space. Occurs.

The CT-data structure resolves the growth of the header table by deleting the item from the header table, although the header table is composed of transaction link sets and is larger than the header table of other data structures.

Table 2 shows the CT-data structure generation algorithm, which finds frequent itemsets through two transactional database scans without generating candidate items for improved execution time, and uses the same storage space for frequent projections of the same items. This reduces the number of searches and reduces the storage space.

[Table 2] Generation algorithm of CT data structure

); Output : 헤더 테이블, 압축된 트랜잭션들; Method : Call CT-자료구조(트랜잭션 데이터베이스,

) Procedure CT-자료구조(트랜잭션 데이터베이스,

) { for( 트랜잭션 데이터베이스의 모든 트랜잭션 ) for( 트랜잭션의 모든 항목 ) if( 헤더 테이블에 해당 항목이 있을 경우 ) 빈도 수 증가; else 헤더 테이블에 항목 추가; for( 헤더 테이블의 모든 요소 ) if( 요소의 빈도 수 <

) 헤더 테이블로부터 항목 제거; for( 트랜잭션 데이터베이스의 모든 트랜잭션 ) for( 트랜잭션의 모든 항목 ) { if( 헤더 테이블에 해당 항목이 있을 경우 ) 여과된 트랜잭션에 항목 추가; } if( 압축된 트랜잭션들에 여과된 트랜잭션이 있을 경우 ) 여과된 트랜잭션의 빈도 수 증가; else { 압축된 트랜잭션들에 여과된 트랜잭션 추가; if( 항목이 여과된 트랜잭션의 첫 번째 항목일 경우 ) 헤더 테이블에 링크 연결 } return 헤더 테이블, 압축된 트랜잭션들; } Algorithm1 ( Generate CT-data structures ) Creates header tables and compressed transactions. Input : Transaction database, minimum support threshold (

); Output : header table, compressed transactions; Method : Call CT-data structure (transaction database,

Procedure CT-data structures (transaction databases,

) {for (all transactions in a transactional database) for (all items in a transaction) if (if there is an entry in the header table) Increase frequency; adding entries to the else header table; for (all elements in header table) if (frequency of element <

) Remove entries from the header table; for (all transactions in a transactional database) for (all items in a transaction) {if (if there is an entry in the header table) Add an item to a filtered transaction; } if (if there are filtered transactions in compressed transactions) increasing the frequency of filtered transactions; else {add filtered transaction to compressed transactions; if (if item is the first item in a filtered transaction) Link to header table} return header table, compressed transactions; }

3 is an embodiment of a CT data structure according to the present invention, which is generated using the transaction data of Table 1 and the algorithm of Table 2.

After reading the first item 'f' from the transaction database of Table 1, it is checked whether there is 'f' in the header table 310. Since 'f' is not in the header table 310, 'f' is added and the item frequency is increased by one. In this way, the header table 310 is generated by reading the entire transaction data. In this case, the header table is implemented as a hash table with the item name as the key value for quick search. After the first scan of the transaction database, the header table 310 stores frequency information for each item. The header table 310 is scanned to see elements <e: 1>, <n: 1>, <s: 1>, <d: 1>, <g: 1>, and <i: that do not meet the minimum support threshold. 1>, <l: 1>, <o: 1>, <h: 1>, <j: 1>, and <k: 1> are removed from the header table 310. Afterwards, a second scan of the transaction database is performed to generate the compressed transactions 320 and perform a link connection with the header table.

In Table 1, the items of the TID 100 transaction are read in order to configure the filtered transactions <a, c, f, m, and p> with only items that exist in the header table 310, that is, satisfying the minimum support threshold. After sorting in an arbitrary order (alphabetical order), it is checked whether there is a corresponding transaction in the compressed transactions 320. Since the compressed transactions 320 are composed of only item names, the compressed transactions 320 can be implemented as a hash table having a set of item names as a key value, so that the exploration time takes 0 (1). Since <a, c, f, m, and p> are not in the compressed transaction, they are added and the item 'a', which is the first item of the filtered transaction, is linked to the header table 310. In this way, reading the entire transaction database in Table 1 creates a CT-data structure as shown in Figure 3. Since the filtered transactions of TID 100 and 500 transactions are all composed of the same items, they are represented as <a, c, f, m, p: 2>.

The time complexity of the CT-data structure generation algorithm is as follows. Implement the header table as a hash table with the item name as the key value, and add a field to remember the last link position in the header table of the existing H-data structure for quick link addition. The time taken to insert a single transaction into an H-data structure or CT-data structure when generating a CT-data structure is all 0 (| Trans |) (| Trans | = 1-the number of frequent items included in a single transaction). In addition, since the CT-data structure uses a hash table with compressed transactions as a key value, the time taken to find the same compressed transactions is 0 (1). Therefore, the H-data and CT-data creation time are both 0 (N * | Trans |) (N = number of transactions).

In the case of the space complexity of the CT-data structure, the header table has the same number of elements as both the H-data structure and the CT-data structure, and the header table elements of the CT-data structure are more likely to be caused by transactional link sets. Because of the size, the header table size of the CT-data structure is larger than that of the H-data structure. However, since the frequent projection of the H-data structure is 2 * | Trans |, and the compressed transactions of the CT-data structure are (| Trans | + frequency), the frequent projection size of the H-data structure is the compressed size of the CT-data structure. Larger than transactions size. In addition, the size of the header table is much smaller than that of frequent projections or compressed transactions, and the CT-data structure removes the expiration of items from the header table. Is less than the storage size of.

Association Rule mining in Compressed Space (ARCS) algorithms, which explore association rules based on CT-data structures, detect frequent itemsets using pattern-growth methods such as FP-growth and H-mine. That is the item set _{I = i 1, i 2,} ..., i m all frequent itemsets containing i ₁ If there are, all the frequent itemsets containing i stand ₂ does not contain a i _1, i _1. ..i will perform exploration in a way to find all frequent itemsets (3≤k≤m) comprising a stand i _k If you do not include a _{k -1.}

FP-growth has the disadvantage of creating conditional FP-trees and header tables during frequent item set exploration, while H-mine re-queues the previous item's queue if the set of links to that item is incomplete. The disadvantage is that you need to trace back and find the missing links.

To solve this problem, the ARCS algorithm generates only conditional header tables during frequent item set exploration, and adds a link to the header table for the second item of each transaction to avoid traceback. Also, in order to prevent the memory shortage caused by the repetitive generation of the header table during the exploration, the terminated item is removed from the header table. This may be possible because no backtracking is required.

Table 3 shows the ARCS algorithm.

[Table 3] ARCS algorithm

; Output : 모든 빈발항목집합; Method : Call ARCS(헤더 테이블, 압축된 트랜잭션들,

) Procedure ARCS(헤더 테이블, 압축된 트랜잭션들,

) { for( 헤더 테이블의 모든 항목 ) if( 항목의 지지도 <

) { for( 항목의 링크집합이 가르키는 모든 압축된 트랜잭션들) 각 압축된 트랜잭션들의 두 번째 아이템을 헤더 테이블에 연결; } else { 이름(헤더 테이블의 이름∪항목의 이름)과 지지도(항목의 지지도)를 갖는 빈발 항목 집합 생성 및 추가; 조건적 헤더 테이블 = TraverseLinkSet(빈발항목의 이름, 요소, 헤더 테이블, 압축된 트랜잭션들); 헤더 테이블로부터 요소 제거; if( 조건적 헤더 테이블 != null ) ARCS(조건적 헤더 테이블, 압축된 트랜잭션들,

); } } Procedure TraverseLinkSet(빈발항목의 이름, 요소, 헤더 테이블, 압축된 트랜잭션들) { 빈발항목을 이름으로 갖는 조건적 헤더 테이블 생성; for( 요소가 가르키는 모든 압축된 트랜잭션들 ) for( 압축된 트랜잭션들의 첫 번째 항목을 제외한 모든 항목 ) 조건적 헤더 테이블에 해당 항목이 있을 경우 빈도 수를 증가시키고, 없을 경우 추가; if( 항목이 압축된 트랜잭션들의 두 번째 항목일 경우 ){ 조건적 헤더 테이블에 링크 연결; 원본 헤더 테이블에 링크 연결; } return 조건적 헤더 테이블; } Algorithm2 (ARCS) Finds all frequent itemsets from a CT-data structure. Input : header table, compressed transactions, minimum support threshold

; Output : all frequent itemsets; Method : Call ARCS (header table, compressed transactions,

Procedure ARCS (Header Tables, Compressed Transactions,

) {for (all items in header table) if (support for item <

) {for (all compressed transactions pointed to by link set of items) linking the second item of each compressed transaction to the header table; } else {Create and add a frequent set of items with a name (name of the header table ∪ item) and support (item support); Conditional header table = TraverseLinkSet (name of frequent item, element, header table, compressed transactions); Removing elements from the header table; if (conditional header table! = null) ARCS (conditional header table, compressed transactions,

); }} Procedure TraverseLinkSet (name of frequent item, element, header table, compressed transactions) {create conditional header table with frequent item by name; for (all compressed transactions pointed to by the element) for (all items except the first item in the compressed transactions) Increases the frequency if there is an entry in the conditional header table, adds none; if (if item is the second item in compressed transactions) {Link to conditional header table; Linking to the original header table; } return conditional header table; }

The frequent item set exploration starts with 'a', the first item in the header table. Since the name of the root header table is null, create a: 3 frequent itemsets. The TraverseLinkSet function in Table 3 reads all the compressed transactions indicated by item 'a' and creates a conditional header table of 'a'. That is, after reading 'c', which is the second item of <a, c, f, m, p: 2>, it checks whether 'c' is in the conditional header table of 'a'. Add a roll and increase the item frequency by 1. At this time, item 'c', which is the second item of the compressed transaction, is connected to the conditional header table of 'a' and to the root header table to prevent backtracking. After reading <a, b, c, f, m: 1> in the same way, delete the item 'a' from the root header table when the conditional header table of 'a' is created.

4 is an embodiment of conditional header table generation using an ARCS algorithm according to the present invention. The conditional header table 420 of 'a' among the items of the transaction database of Table 1 above and the dotted line represents the added link. Since the first item 'b' in the conditional header table 420 of 'a' does not satisfy the minimum map, the second item 'c' is connected to the conditional header table 420 of 'a' and 'a' 'B' is deleted from the conditional header table 420 of '. Since the second item 'c' satisfies the minimum map and the name of the conditional header table 420 of 'a' is 'a', an ac: 3 frequent item set is generated.

5 is another embodiment of conditional header table generation using the ARCS algorithm according to the present invention. In the TraverseLink function of Table 3, all the compressed transactions indicated by the item 'c' are read to generate the conditional header table 530 of 'ac'. That is, after reading 'f', which is the second item of <c, f, m, p: 2>, it checks whether the conditional header table 530 of 'ac' contains 'f', so 'f' is not in the header table. Add 'f' and increase the item frequency by 1. At this time, the second item of the compressed transaction 540, 'f', is connected to the conditional header table 520 of 'a' and the conditional header table 530 of 'ac', respectively. After reading <c, f, m: 1> in the same manner, when the header table 530 of 'ac' is generated, the item 'a' is deleted from the conditional header table 520 of 'a'.

In this way, it finds all the frequent itemsets a: 3, ac: 3, acf: 3, acfm: 3, af: 3, afm: 3, and am: 3 that contain 'a' and then include 'b'. Exploring a set of all frequent items. Since the set of transaction links of 'b' in the root header table is complete, there is no need to backtrack.

6 is a diagram illustrating a search path for finding all frequent itemsets in the ARCS algorithm according to the present invention. Exploration and partitioning methods for exploration of frequent itemsets including 'b', 'c', 'f', 'm' and 'p' like exploration of all frequent itemssets including 'a' And then proceed to Depth-first Search.

The following is an embodiment comparing the conventional rules exploration method and the related art according to the present invention.

Table 4 shows three experimental data for the storage space between FP-data structure, H-data structure and CT-data structure, and the execution time between FP-growth, H-mine and ARCS algorithms. Data used real data.

[Table 4] Experimental data

data Number of items Average number of items per transaction Number of transactions Number of records Data size Relative features (data size, density) Movie data (D1) 326 39 936 36,875 426Kb Small and large Department store data (D2) 6619 7 26580 197,519 4830 Kb Medium, small Department store data (D3) 12,506 41 11,279 468,621 13,800Kb Large, large

For performance comparison, FP-growth and H-mine were re-implemented in the same JAVA environment as the ARCS algorithm, and the experiment was conducted in an environment consisting of 450MHz Pentium main memory, 192MB memory and 40G hard disk.

The compression ratio of the FP-data structure and the CT-data structure was calculated as shown in Equation 1 below. The number of association rule sets found through each algorithm and the support, reliability, and interest of each association rule are the same. Also, to speed up link linking, we added a field to remember the last link position in the header tables of the FP- and H-data structures, respectively.

[Equation 1]

Compression rate of FP-data structures

Compression rate of CT data structure

FIG. 7 is a graph illustrating an example in which an association rule exploration method according to the present invention is compared with a conventional technology. The FP-data structure, H-data structure, and CT-data structure and FP- for experimental data D1 of Table 4 The results show the execution time and storage size according to the change of minimum support threshold of growth, H-mine and CT-algorithm.

In the case of execution time, in the left graph of FIG. 7, the ARCS algorithm shows superior performance compared to FP-growth and H-mine over the entire interval, and it can be seen that the difference is increased as the support becomes smaller. In the case of FP-growth, it took the most time due to the generation of conditional FP-trees, and in the case of H-mine, the number of searches increased more than the ARCS algorithm due to the backtrace.

In the case of the storage space, the CT-data structure in the graph on the right side of FIG. 7 uses the least amount of storage space over the entire interval compared to the FP-data structure and the H-data structure. In the case of the data structure, the growth rate is very small even if the support is low.

Table 5 shows the number of probes of H-mine and ARCS for experimental data D1.

TABLE 5

H-mine exploration frequency 4996161 2141955 1109669 624747 405641 288031 Exploratory number of ARCS 4387164 1881883 984435 548142 354406 248851 Support threshold 4 6 8 10 12 14

For experimental data D1, the difference was small because of the small size and the small number of transactions.

Table 6 shows the compression ratios of the FP data structure, H data structure, and CT data structure for experimental data D1.

TABLE 6

Compression rate of H-data structure 0% 0% 0% 0% 0% 0% Compression rate of CT data structure 0% 0% 0% 0% 0% 0% Compression rate of FP-tree 4.78% 5.59% 6.57% 7.83% 9.45% 10.97% Support threshold 4 6 8 10 12 14

In Table 6, although the compression ratio of the compressed transaction of the CT-data structure was 0% due to the relatively high average number of items and the small number of transactions, the smallest storage space was used in the left graph of FIG. In the case of FP-data structure, the FP-tree compression ratio is 4.78 ~ 10.97%, which is better than the compression ratio of the compressed transactions, but more storage space is used due to the size of the node itself. H-data structure has no compression effect, so the compression ratio is 0%.

FIG. 8 is a graph illustrating another exemplary embodiment in which a related rule exploration method according to the present invention is compared with a conventional technology, and shows execution time and storage space size of the experimental data D2 of Table 4. FIG.

FIG. 9 is a graph illustrating another embodiment in which an association rule exploration method according to the present invention is compared with a conventional technology, and is a result of execution time and storage space size of experimental data D3 of Table 4. FIG.

The left and right graphs of FIGS. 8 and 9 show results of execution time and storage size for experimental data D2 and D3, respectively. ARCS algorithm and CT-data structure in terms of execution time and storage space are similar to experimental data D1. Shows better performance than FP-growth, H-mine, and FP- and H-data structures.

Although the present invention has been shown and described with reference to the preferred embodiments as described above, it is not limited to the above embodiments and those skilled in the art without departing from the spirit of the present invention. Various changes and modifications will be possible.

Therefore, the association rule exploration method of the present invention can process a large amount of data by using a small amount of storage space using a CT-data structure.

In addition, there is a significant and advantageous effect of reducing execution time by exploring association rules using the ARCS algorithm.

Claims (7)

Generating a header table by counting items of all transactions in the original transaction database; A second step of registering the filtered transaction if it matches an item of the header table of the first step after recounting all transaction items in the original transaction database; Counting the filtered transaction to generate a compressed transaction; And A fourth step of linking the item registered in the filtered transaction in the second step to a header table; Association rule exploration method comprising a The method of claim 1, Association rule exploration method, characterized in that for deleting a transaction item that does not satisfy any support among the items of the transactions belonging to the header table. The method of claim 2, And wherein said any degree of support represents a number of counts specified by a user. The method of claim 1, And the header table is implemented as a hash table having the item name as a key value. Counting all the compressed transactions including the first item of the root header table and generating a conditional header table of the first item; A second step of generating a conditional header table with an item satisfying any of the following items in the generated conditional header table of the first item Association rule exploration method comprising a. The method of claim 5, wherein the first step, Counting the second and subsequent items of every compressed transaction including the first item to generate a conditional header table of the first item; Linking a second item of the compressed transaction to the conditional header table of the first item; And Deleting the second item from the root header table when the conditional header table of the first item is generated Association rule exploration method comprising a. The method of claim 5, wherein after performing the second step, Deleting the next item satisfying any support from the conditional header table of the first item when the conditional header table of the next item is generated. Association rule exploration method further comprising.

Images