# Discovery of Characteristic Patterns from Transactions with Their Classes

Authors: Shigeaki Sakurai
Journal: Applied Computational Intelligence and Soft Computing
 (2012)

---

## Abstract

This paper deals with transactions with their classes. The classes represent the difference of conditions in the data collection. This paper redefines two kinds of supports: characteristic support and possible support. The former one is based on specific classes assigned to specific patterns. The latter one is based on the
minimum class in the classes. This paper proposes a new method that efficiently discovers patterns whose characteristic supports
are larger than or equal to the predefined minimum support by using their possible supports. Also, this paper verifies the effect of the method through numerical experiments based on the data registered in the UCI machine learning repository and the RFID (radio frequency identification) data collected from two apparel shops.


---

## Body

## 1. Introduction

Owing to the progress of computer environment and network environment, we can easily collect large amount of data and cheaply store it. We believe that the data includes useful knowledge which can help our decision making. Many researchers tackle on the discovery of the knowledge from the data since the mid-1990s. Various discovery tasks are studied in order to deal with various kinds of data.The discovery task of frequent patterns composed of items from transactions is one of the tasks. Each transaction is composed of an item set. In the retail field, a receipt and a sales item correspond to a transaction and an item, respectively. In the initial researches, [1] proposes a method that efficiently generates candidate patterns and discovers frequent patterns by using the Apriori property. Here, the property shows that the frequencies of patterns monotonically decrease as items composing the patterns increase. Reference [2] proposes a bitmap index, [3] proposes a vertical ID list, and [4] proposes a frequent pattern tree (FP-tree) in order to speedily access the transactions and efficiently calculate the frequencies of the patterns. It is possible for these improvements to speedily discover the frequent patterns.However, the discovered frequent patterns are not always the ones that are attractive for analysts. The discovery of patterns with different features is tried. For example, [5] tries to discover patterns whose orders based on the frequency are higher than the predefined order. Reference [6] does closed patterns representing many frequent patterns. Reference [7] does long patterns including many items. Reference [8] does patterns reflecting weights of items. Reference [9] does patterns reflecting hierarchical relationships among items. It is anticipated that more attractive patterns are discovered by these researches.On the other hand, the discovery of patterns from different kinds of data is tried. For example, [10] tries to deal with tabular structured data. Here, each item is composed of an attribute and an attribute value. It proposes a method that efficiently discovers frequent patterns from the data by using relationships between attributes and attribute values. In the case of the data, missing values are often included. In order to deal with the values, [10–12] propose new evaluation criteria of the patterns.The discovery task of patterns from transactions is expanding its research field more and more. This paper focuses on the difference of conditions in the data collection as one of expanding fields. This is because we would like to discover patterns which tend to be overlooked due to the difference. For example, we try to discover patterns of sales items from a chain of retail stores. If we collect the data from many stores, we cannot anticipate that each store sells the same items. Limited stores can sell specific items such as new items and regional items. It is difficult to discover patterns related to the items sold in the limited stores. This is because their sales volume tends to be much smaller than the one of items sold in all stores. Also, we cannot anticipate that each store sells the same items every day. It can sell seasoned items. Patterns related to the seasoned items tend to be overlooked. In addition, we cannot anticipate that each store sells items based on the same sales method. Customers may be able to buy items through the trial of items in a store. Patterns related to the trial tend to be buried in patterns unrelated to the one. We can easily find difference of conditions in the data collection. It is anticipated that more attractive patterns are discovered, if we reflect the difference in the discovery of patterns.Thus, this paper regards the difference of conditions in the data collection as classes. It proposes a method that efficiently discovers patterns reflecting the classes. Also, this paper applies the method to the data registered in the UCI machine learning repository [13] and the RFID (radio frequency identification) data collected from apparel shops [14]. It compares patterns discovered by the proposed method with patterns discovered by an existing discovery method, verifies the validity of the patterns discovered by the proposed method, and shows the effect of the proposed method.


## 2. Discovery of Characteristic Patterns

### 2.1. Transactions with Their Classes

This paper regards an item set with a class as a transaction. That is, the transactiont is defined by Formula (1). In this formula, I is a set of all items, C is a set of all classes, and n is the number of items included in the transaction. Citi is a subset of C and is composed of classes where the item iti can be included. This definition shows that the transaction does not have multiple same items. The constraint is introduced by the original discovery task [1] which does not deal with classes. It notes whether an item is sold or not. Also, this definition shows that each item is included in the class cl(1)t=(cl⁡∣it1,it2,…,itn),iti∈I,cl⁡∈⋂∀iCiti⊆C,ifk≠l,thenitk≠itl.Here, we note that the examples are composed of four classes: “spring”, “summer”, “autumn”, and “winter”, and three items: “apple”, “watermelon”, and “banana”. Table1 shows classes in which each item is sold. The set of classes corresponding to an item is called an item class hereafter. Tables 2 and 3 show legal examples and illegal ones, respectively.Table 1
Item class.
ItemClassapple{autumn, winter}watermelon{spring, summer}banana{spring, summer, autumn, winter}Table 2
Legal examples.
t1 = (winter | apple, banana)t2 = (summer | watermelon, banana)Table 3
Illegal examples.
t3 = (autumn | apple, apple, banana)t4 = (spring | apple, watermelon)In Table2, t1 is a transaction with its class, because “winter” is included in the item classes of “apple” and “banana”. Also, t2 is a transaction with its class, because “summer” is included in the item classes of “watermelon” and “banana”. In Table 3, t3 is not a transaction with its class, because two “apple” are included in t3. Also, t4 is not a transaction with its class, because the item class of “apple” does not include “spring”. Some readers may think that this restriction is too strict. However, it is not always strict. This is because we can add “spring” to the item class of “apple” if we need to regard t4 as a transaction with its class. On the other hand, if a valid item class is assigned to each item, we can think of two possibilities. One is that the class in the transaction is wrong, and the other is that wrong items are included in the item set. We can think that some errors occur in the data collection.


### 2.2. Criteria

This section considers a method dealing with transactions with their classes. Also, it considers a method that discovers important patterns composed of items from the transactions. Here, we note that the numbers of the transactions with specific classes are not always equal to each other. That is, the number of transactions corresponding to a class can be large, and the one corresponding to another class can be small. Therefore, the numbers of items corresponding to the former class tend to be frequent, and patterns composed of the items tend to be frequent.For example, transactions and item classes as shown in Table4 are given. Also, they have three patterns composed of two items: (it1, it2), (it1, it3), and (it2, it3). Their frequencies are 4, 2, and 1, respectively. (it1, it2) is the most frequent pattern in the three patterns. Here, we note the ratio of the frequencies to the number of transactions where the patterns can be included. (it1, it2) can be included in all transactions (t1~t8). This is because both the item class of it1 and the one of it2 are {cl1,cl2}, and the class set corresponding to (it1, it2) is {cl1,cl2}. The ratio of (it1, it2) is 0.50(=4/8). On the other hand, (it1, it3) can be included in three transactions (t6~t8). This is because the item class of it3 is {cl2}. The ratio of (it1, it3) is 0.67(=2/3). Similarly, (it2, it3) can be included in three transactions (t6~t8). The ratio of (it2, it3) is 0.33(=1/3). Therefore, (it1, it3) is the pattern with the biggest ratio, and it is the most important pattern in the three patterns.Table 4
An example of transactions and item classes (1).
(a)
Transaction
t1=(cl1∣it1)t2=(cl1∣it1,it2)t3=(cl1∣it1,it2)t4=(cl1∣it1,it2)t5=(cl1∣it1,it2)t6=(cl2∣it1,it3)t7=(cl2∣it1,it3)t8=(cl2∣it2,it3)(b)
Item class
ItemClassit1{cl1,cl2}it2{cl1,cl2}it3{cl2}We anticipate that the important pattern based on the ratio is more valid than the frequent pattern because the latter one is often a well-known pattern and does not give a big impact to analysts. It is necessary to define a new criterion corresponding to the ratio. Formula (2) shows the definition. It is based on an idea similar to the support for missing values in tabular structured data [10, 11]. The criterion is called a characteristic support hereafter(2)supp⁡char(p)=NpNCp,Cp=⋂iti∈pCiti.In Formula (2), p is a pattern composed of items. Np is the number of transactions including p. Cp is such a class set that all items composing p can be included. NCp is the number of transactions whose classes are included in Cp. Cp and NCp are called a pattern class and a total transaction number for Cp hereafter. We note that Cp can be ϕ. However, if Cp=ϕ, Np is 0. It is not necessary to calculate the characteristic support of p. Therefore, it is not necessary to care about the possibility Cp=ϕ. Also, we note that the characteristic support is in [0,1]. This is because Np is smaller than or equal to NCp.We can anticipate that if the discovery method extracts patterns whose characteristic supports are larger than or equal to a predefined threshold, the patterns can reflect the class distribution in transactions. However, the patterns may be accidentally extracted from a very small transaction subset. We cannot always believe that the patterns are characteristic. Thus, this paper introduces the other criterion assuring the minimum frequency of the pattern. The criterion is equal to the representativity introduced by [12].This paper tries to discover patterns satisfying two conditions: the minimum support and the minimum frequency. That is, if the characteristic supports of the patterns are larger than or equal to the minimum support and their frequencies are larger than or equal to the minimum frequency, the patterns are extracted as characteristic patterns. In the case of transactions without their classes, these conditions are equal to each other. This is because if the support of a patternp1 is always larger than the one of the other pattern p2 in the latter case, the frequency of p1 is larger than the one of p2. It is sufficient for the transactions without their classes to evaluate one of the conditions.Next, we note the property of characteristic supports and frequencies. If two patternsp1 and p2 satisfy the relationship p1⊆p2, the frequency of p1 is clearly larger than or equal to the one of p2. The frequencies monotonically decrease as patterns grow. However, the monotonic property is not always satisfied in the case of the characteristic supports. For example, we note transactions and item classes as shown in Table 5.Table 5
An example of transactions and item classes (2).
(a)
Transaction
t1=(cl1∣it1)t2=(cl3∣it3)t3=(cl2∣it2)t4=(cl2∣it1,it2)t5=(cl2∣it1,it2)(b)
Item class
ItemClassit1{cl1,cl2,cl3}it2{cl2}it3{cl3}Table5 shows that the frequency of it1 is 3 and the total transaction number for it1 is 5. This is because it1 is included in three item classes cl1, cl2, and cl3. The characteristic support of it1 is 0.60(=3/5). Also, Table 5 shows that the frequency of (it1, it2) is 2 and the total transaction number for (it1, it2) is 3. This is because a pattern class of (it1, it2) is {cl2}. The characteristic support of (it1, it2) is 0.67(=2/3). This example shows that the monotonic property is not satisfied.The monotonic property is very important for the discovery method of patterns in order to efficiently discover them. The method can avoid their redundant evaluation by using the property. Therefore, it is difficult for the characteristic support to efficiently discover patterns. Certainly, we can try to discover patterns based on the monotonic property of the frequency. However, the frequency is a limited criterion. The minimum frequency tends to be set as a small value. We cannot anticipate that sufficient efficiency is gained by the frequency.Thus, this paper introduces another criterion. The criterion is based on an idea similar to the possible support proposed by [10]. The support reflects missing values in tabular structured data. This paper redefines the possible support in order to deal with transactions with their classes. Formula (3) shows the definition. In Formula (3), Ncli is the number of transactions assigned class cli. mincli∈Cp{Ncli} is called the minimum transaction number for p hereafter(3)supp⁡pos(p)=Npmin⁡cli∈Cp{Ncl⁡i}.
The redefined possible support is larger than or equal to 0 and can be larger than or equal to 1. This is because Np can be larger than mincli∈Cp{Ncli}. Also, the redefined possible support satisfies the monotonic property. The reason is shown in the following. Firstly, we note the numerator of the formula. The numerator is the frequency of a pattern and monotonically decreases. On the other hand, if two patterns p1 and p2 have the relationship p2⊇p1, the relationship Cp2⊆Cp1 is clearly satisfied. Thus, mincli∈Cp2{Ncli}≥mincli∈Cp1{Ncli}. That is, the denominator monotonically increases as the patterns grow. Therefore, the possible supports monotonically decrease as the patterns grow.Next, we note the relationships between the characteristic support and the possible support. The formulae of these supports show that the numerators are equal to each other. Also, they show that the relationshipNCp≥mincli∈Cp{Ncli} is satisfied in any patterns. Therefore, the relationship described in Formula (4) is always satisfied(4)supp⁡pos(p)≥supp⁡char.Formula (4) shows that the possible support of a pattern p1 gives the upper bound to characteristic supports of any super patterns (⊇p1). Therefore, if the possible support of p1 is smaller than the minimum support, the characteristic supports of the supper patterns are smaller than the minimum support. The supper patterns cannot be characteristic patterns. Thus, the discovery method keeps patterns whose possible supports are larger than or equal to the minimum support and whose frequencies are larger than or equal to the minimum frequency in order to grow them. The patterns are called possible patterns hereafter. Also, the discovery method extracts patterns whose characteristic supports are larger than or equal to the minimum support from the possible patterns. The discovery method based on the two-stepwise evaluation method can efficiently discover all characteristic patterns.


### 2.3. Discovery Method

This paper proposes a method that discovers all characteristic patterns from transactions with their classes. The method is based on the FP tree and the FP growth proposed by [4]. Here, the FP tree is the data structure storing transactions with tree format. The FP growth is a method discovering all frequent patterns by using the FP tree. The FP growth generates the FP trees from transaction subsets and generates new transaction subsets from generated FP trees. Two kinds of generation steps are recursively repeated. This paper proposes the refined FP tree and the refined FP growth in order to deal with transactions with classes.The original FP tree is composed of nodes assigned an item name and its frequency, links tying to the nodes with the same item name, a header table storing item, and links tying to items in the table with nodes including the item names. In the FP tree, the root node is a special node and is assigned “null”. The refined FP tree is basically equal to the original one. But, the refined one is assigned a pattern class and an identification flag to each item in the header table. Here, the flag shows whether the pattern corresponding to each item in the header table is included in a characteristic pattern. The refined FP tree is generated by an algorithm as shown in Table6 from transactions with their classes, item classes, and a conditioned item set. In the first generation of the refined FP tree, the conditioned item set is ϕ. In the generation except the first one, it is at least possible patterns. In this algorithm, the minimum support (∈(0,1]) and the minimum frequency (≥1) are predefined. Table 6 describes the difference of the generation method for the original one with bold style.Table 6
A generation method of the refined FP tree.
(1) Search transaction and calculate frequencies of each item.(2)Calculate a product set between a pattern classCIts  of a conditioned item set  Itsand an item classCiti  of each item  iti, and set the  product set as a pattern  classCpi  of a patternpi (=Its∪iti).(3)Calculate the total number and the minimum number forpi.(4)Calculate a characteristic  support and a possible support of  pi.(5) Repeat from step 2 to step 4 for anyi.(6)Extract items whose patterns are possible patterns and generate a listFlistarranged the items in descending order, where the first key is the frequency, the second key is the characteristic support, and the third key is the possible support.(7) Regard Flist as a header tableH in a refined FP tree T. Also, tieCpi to iti  in H. In addition, tie an identification flag  fli of  pi  to  iti  in  H.Here, if the pattern corresponding to  iti  is a characteristic  pattern, the value of  fli is “C”. Otherwise the value is“P”. That is, “C” shows that the pattern is a characteristic pattern and “P” shows that the pattern is not a characteristic pattern and is a possible pattern.(8) Create a root node ofT and assign the label “null” to it.(9) Set the root node as a target nodeN.(10) Pick up a transactiontj. If the transaction cannot be picked up, then this algorithm stops.(11) Pick up only items included inH from tj, sort them in the order of items in H, and create a selected and sorted item set Itstj.(12) Pick up an itemitjk from the top of Itstj. If the item cannot be picked up, then go to step 10.(13) If an item name ofitjk is assigned to a child node of N, then the frequency of the node is counted up. Otherwise, a new node N′ is created. N′ is assigned the item name of itjk and is set 1 to the frequency. Also, create a link between N and N′, and register N′ to itjk in H. In addition, regard a selected child node or N′ as a new target node N.(14) Go to step 12.In the following, we show an example which generates the refined FP tree from transactions and item classes as shown in Table7.Table 7
An example of transactions and item classes (3).
(a)
Transaction
t1=(cl1∣it1,it2,it3,it5)t2=(cl1∣it1,it3,it4)t3=(cl1∣it1,it2,it3,it4,it8)t4=(cl2∣it1,it2,it4,it7)t5=(cl2∣it4,it5,it6)t6=(cl2∣it1,it5,it6)t7=(cl2∣it1,it9)(b)
Item class
ItemClassit1{cl1,cl2}it2{cl1,cl2}it3{cl1}it4{cl1,cl2}it5{cl1,cl2}it6{cl2}it7{cl2}it8{cl1}it9{cl1,cl2}In this case, the item set isϕ. The minimum support is 0.5 and the minimum frequency is 1. The transactions of Table 7 show that frequencies of it1~it9 are 6, 3, 3, 4, 3, 2, 1, 1, and 1, respectively. The item classes of Table 7 show that the total transaction numbers for it1, it2, it4, it5, and it9 are 7, the ones for it3 and it8 are 3, and the ones for it6 and it7 are 4. Also, it shows that the minimum transaction numbers for it1, it2, it3, it4, it5, it8, and it9 are 3 and the ones for it6 and it7 are 4. Possible supports of it1~it9 are 2.00(=6/3), 1.00(=3/3), 1.00(=3/3), 1.33(=4/3), 1.00(=3/3), 0.50(=2/4), 0.25(=1/4), 0.33(=1/3), and 0.33(=1/3), respectively. Therefore, the generation method can select it1, it2, it3, it4, it5, and it6 as possible items. The items are arranged in the descending order of frequencies, characteristic supports, and possible supports. The method generates the list Flist such as (it1,it4,it3,it2,it5,it6). But, indexes of the items are used as the fourth key, if three criteria are equal to each other.Next, the method picks up possible items from the transactions and arranges the items in order of the Flist. It generates a selected and sorted transaction subset as shown in Table8. The subset is used in order to generate the refined FP tree.Table 8
A selected and sorted transaction subset.
t1′=(it1,it3,it2,it5)t2′=(it1,it4,it3)t3′=(it1,it4,it3,it2)t4′=(it1,it4,it2)t5′=(it4,it5,it6)t6′=(it1,it5,it6)t7′=(it1)In the case thatt1′ is selected from the subset, the method generates a part of the refined FP-tree as shown in Figure 1(a). Also, in the case that t2′ is selected from the subset, it generates a part of the refined FP tree as shown in Figure 1(b). That is, the method adds new nodes or updates the frequencies of the existing node in order from the root node. Lastly, the refined FP tree as shown in Figure 2 is generated.Refined FP tree (1).
(a)
Aftert1′(b)
Aftert2′Figure 2
Refined FP tree (2).In the remaining part of this subsection, we explain the refined FP growth. The original FP growth detects a single prefix path. The path is a path linked from the root. Each node included in the path has only a child. If an FP tree has the single prefix path, the original FP growth divides the FP-tree into the single prefix path and the remaining part. The remaining part is added a new root node and a new FP tree is generated. The original FP growth separately discovers frequent patterns from the new FP-tree and from the single prefix path. Also, it combines the patterns based on the tree with the patterns based on the path. The combined patterns are frequent patterns. The original FP growth can discover all frequent patterns based on the combination.On the other hand, in the case of the refined FP growth, we do not know whether characteristic supports increase as patterns grow. Even if characteristic patterns based on a single prefix path are given and characteristic patterns based on a new refined FP tree are given, their combinations are not always characteristic patterns. It is necessary to check whether the combinations are characteristic patterns by calculating their characteristic supports. The detection of the single prefix path does not give sufficient merits. Thus, the refined FP growth tries to discover characteristic patterns without detecting a single prefix path. In the following, we explain the FP growth without the detection.The refined FP growth picks up an item it from the rear of Flist in the refined FP tree in order. It generates transactions conditioned byit. That is, the refined FP growth extracts nodes including it from the refined FP tree and extracts paths from upper nodes of the extracted nodes to the root node. A transaction is generated from each path and is assigned frequency which is equal to the frequency of the node including it. The refined FP growth generates a new refined FP tree from the conditioned transactions. it is added to the conditioned item set Its. Here, Its is assigned to the previous refined FP tree and is ϕ in the first process of the refined FP growth. The refined FP growth recursively repeats the generation of refined FP trees and conditioned transactions.On the other hand, the refined FP growth needs pattern classes in order to calculate characteristic supports and possible supports. The pattern classes can be generated by referring to both items included in the patterns and their item classes. However, if the generation is always started from scratch, it is redundant. We can generate the pattern classes more efficiently by using a relationship among pattern classes. That is, if a patternp′ is generated by the combination of a pattern p and a new item it, a pattern class (Cp′) of p′ is equal to the product set (Cp∩Cit) based on both a pattern class (Cp) of p and an item class (Cit) of it. Therefore, the header table keeps pattern classes.According to the above discussion, the refined FP growth is described as shown in Table9. Table 9 describes the difference between the original FP growth and the refined one with bold style. The refined FP tree T and Its are input to the refined FP growth.Table 9
An algorithm of the refined FP growth algorithm.
(1) Extract an itemit from the rear of Flist in a refined FP tree T. If the item is not extracted, this algorithm stops.(2) Add it to an item set Its andinvestigate an identification flag of it. If the flag shows a characteristic pattern, then outputItsas a characteristic pattern.(3) Extract a nodeN whose item is equal to it from T. If the node is not extracted, then go to step 6.(4) Extract a path from the upper node ofN to the root. Generate an item set composed of item included in the extracted path and extract the frequency assigned to N. Regard the combination of the item set and the frequency as a transaction conditioned by it.(5) Go to step 3.(6) Apply a set Trans of the generated transactions to the algorithm shown in Table6 and generate a new refined FP tree T′. If T′ is not generated, then this algorithm stops. Otherwise, this algorithm recursively calls by giving T′ and Its to it as arguments.(7) Go to step 1.Lastly, a discovery method of characteristic patterns is described as shown in Table10. The method appropriately calls the algorithms as shown in Tables 6 and 9. It can generate all characteristic patterns from transactions with their classes, item classes, the minimum support, and the minimum frequency.Table 10
A discovery method of characteristic patterns.
(1) Search transactions and calculate the number of transactions for each class.(2) Setϕ to an item set Its and set all classes to its pattern class.(3) Generate a refined FP treeT based on the algorithm shown in Table 6.(4) IfT is not generated, then this algorithm stops. Otherwise, it discovers characteristic patterns from T and Its based on the algorithm shown in Table 9.


## 2.1. Transactions with Their Classes

This paper regards an item set with a class as a transaction. That is, the transactiont is defined by Formula (1). In this formula, I is a set of all items, C is a set of all classes, and n is the number of items included in the transaction. Citi is a subset of C and is composed of classes where the item iti can be included. This definition shows that the transaction does not have multiple same items. The constraint is introduced by the original discovery task [1] which does not deal with classes. It notes whether an item is sold or not. Also, this definition shows that each item is included in the class cl(1)t=(cl⁡∣it1,it2,…,itn),iti∈I,cl⁡∈⋂∀iCiti⊆C,ifk≠l,thenitk≠itl.Here, we note that the examples are composed of four classes: “spring”, “summer”, “autumn”, and “winter”, and three items: “apple”, “watermelon”, and “banana”. Table1 shows classes in which each item is sold. The set of classes corresponding to an item is called an item class hereafter. Tables 2 and 3 show legal examples and illegal ones, respectively.Table 1
Item class.
ItemClassapple{autumn, winter}watermelon{spring, summer}banana{spring, summer, autumn, winter}Table 2
Legal examples.
t1 = (winter | apple, banana)t2 = (summer | watermelon, banana)Table 3
Illegal examples.
t3 = (autumn | apple, apple, banana)t4 = (spring | apple, watermelon)In Table2, t1 is a transaction with its class, because “winter” is included in the item classes of “apple” and “banana”. Also, t2 is a transaction with its class, because “summer” is included in the item classes of “watermelon” and “banana”. In Table 3, t3 is not a transaction with its class, because two “apple” are included in t3. Also, t4 is not a transaction with its class, because the item class of “apple” does not include “spring”. Some readers may think that this restriction is too strict. However, it is not always strict. This is because we can add “spring” to the item class of “apple” if we need to regard t4 as a transaction with its class. On the other hand, if a valid item class is assigned to each item, we can think of two possibilities. One is that the class in the transaction is wrong, and the other is that wrong items are included in the item set. We can think that some errors occur in the data collection.


## 2.2. Criteria

This section considers a method dealing with transactions with their classes. Also, it considers a method that discovers important patterns composed of items from the transactions. Here, we note that the numbers of the transactions with specific classes are not always equal to each other. That is, the number of transactions corresponding to a class can be large, and the one corresponding to another class can be small. Therefore, the numbers of items corresponding to the former class tend to be frequent, and patterns composed of the items tend to be frequent.For example, transactions and item classes as shown in Table4 are given. Also, they have three patterns composed of two items: (it1, it2), (it1, it3), and (it2, it3). Their frequencies are 4, 2, and 1, respectively. (it1, it2) is the most frequent pattern in the three patterns. Here, we note the ratio of the frequencies to the number of transactions where the patterns can be included. (it1, it2) can be included in all transactions (t1~t8). This is because both the item class of it1 and the one of it2 are {cl1,cl2}, and the class set corresponding to (it1, it2) is {cl1,cl2}. The ratio of (it1, it2) is 0.50(=4/8). On the other hand, (it1, it3) can be included in three transactions (t6~t8). This is because the item class of it3 is {cl2}. The ratio of (it1, it3) is 0.67(=2/3). Similarly, (it2, it3) can be included in three transactions (t6~t8). The ratio of (it2, it3) is 0.33(=1/3). Therefore, (it1, it3) is the pattern with the biggest ratio, and it is the most important pattern in the three patterns.Table 4
An example of transactions and item classes (1).
(a)
Transaction
t1=(cl1∣it1)t2=(cl1∣it1,it2)t3=(cl1∣it1,it2)t4=(cl1∣it1,it2)t5=(cl1∣it1,it2)t6=(cl2∣it1,it3)t7=(cl2∣it1,it3)t8=(cl2∣it2,it3)(b)
Item class
ItemClassit1{cl1,cl2}it2{cl1,cl2}it3{cl2}We anticipate that the important pattern based on the ratio is more valid than the frequent pattern because the latter one is often a well-known pattern and does not give a big impact to analysts. It is necessary to define a new criterion corresponding to the ratio. Formula (2) shows the definition. It is based on an idea similar to the support for missing values in tabular structured data [10, 11]. The criterion is called a characteristic support hereafter(2)supp⁡char(p)=NpNCp,Cp=⋂iti∈pCiti.In Formula (2), p is a pattern composed of items. Np is the number of transactions including p. Cp is such a class set that all items composing p can be included. NCp is the number of transactions whose classes are included in Cp. Cp and NCp are called a pattern class and a total transaction number for Cp hereafter. We note that Cp can be ϕ. However, if Cp=ϕ, Np is 0. It is not necessary to calculate the characteristic support of p. Therefore, it is not necessary to care about the possibility Cp=ϕ. Also, we note that the characteristic support is in [0,1]. This is because Np is smaller than or equal to NCp.We can anticipate that if the discovery method extracts patterns whose characteristic supports are larger than or equal to a predefined threshold, the patterns can reflect the class distribution in transactions. However, the patterns may be accidentally extracted from a very small transaction subset. We cannot always believe that the patterns are characteristic. Thus, this paper introduces the other criterion assuring the minimum frequency of the pattern. The criterion is equal to the representativity introduced by [12].This paper tries to discover patterns satisfying two conditions: the minimum support and the minimum frequency. That is, if the characteristic supports of the patterns are larger than or equal to the minimum support and their frequencies are larger than or equal to the minimum frequency, the patterns are extracted as characteristic patterns. In the case of transactions without their classes, these conditions are equal to each other. This is because if the support of a patternp1 is always larger than the one of the other pattern p2 in the latter case, the frequency of p1 is larger than the one of p2. It is sufficient for the transactions without their classes to evaluate one of the conditions.Next, we note the property of characteristic supports and frequencies. If two patternsp1 and p2 satisfy the relationship p1⊆p2, the frequency of p1 is clearly larger than or equal to the one of p2. The frequencies monotonically decrease as patterns grow. However, the monotonic property is not always satisfied in the case of the characteristic supports. For example, we note transactions and item classes as shown in Table 5.Table 5
An example of transactions and item classes (2).
(a)
Transaction
t1=(cl1∣it1)t2=(cl3∣it3)t3=(cl2∣it2)t4=(cl2∣it1,it2)t5=(cl2∣it1,it2)(b)
Item class
ItemClassit1{cl1,cl2,cl3}it2{cl2}it3{cl3}Table5 shows that the frequency of it1 is 3 and the total transaction number for it1 is 5. This is because it1 is included in three item classes cl1, cl2, and cl3. The characteristic support of it1 is 0.60(=3/5). Also, Table 5 shows that the frequency of (it1, it2) is 2 and the total transaction number for (it1, it2) is 3. This is because a pattern class of (it1, it2) is {cl2}. The characteristic support of (it1, it2) is 0.67(=2/3). This example shows that the monotonic property is not satisfied.The monotonic property is very important for the discovery method of patterns in order to efficiently discover them. The method can avoid their redundant evaluation by using the property. Therefore, it is difficult for the characteristic support to efficiently discover patterns. Certainly, we can try to discover patterns based on the monotonic property of the frequency. However, the frequency is a limited criterion. The minimum frequency tends to be set as a small value. We cannot anticipate that sufficient efficiency is gained by the frequency.Thus, this paper introduces another criterion. The criterion is based on an idea similar to the possible support proposed by [10]. The support reflects missing values in tabular structured data. This paper redefines the possible support in order to deal with transactions with their classes. Formula (3) shows the definition. In Formula (3), Ncli is the number of transactions assigned class cli. mincli∈Cp{Ncli} is called the minimum transaction number for p hereafter(3)supp⁡pos(p)=Npmin⁡cli∈Cp{Ncl⁡i}.
The redefined possible support is larger than or equal to 0 and can be larger than or equal to 1. This is because Np can be larger than mincli∈Cp{Ncli}. Also, the redefined possible support satisfies the monotonic property. The reason is shown in the following. Firstly, we note the numerator of the formula. The numerator is the frequency of a pattern and monotonically decreases. On the other hand, if two patterns p1 and p2 have the relationship p2⊇p1, the relationship Cp2⊆Cp1 is clearly satisfied. Thus, mincli∈Cp2{Ncli}≥mincli∈Cp1{Ncli}. That is, the denominator monotonically increases as the patterns grow. Therefore, the possible supports monotonically decrease as the patterns grow.Next, we note the relationships between the characteristic support and the possible support. The formulae of these supports show that the numerators are equal to each other. Also, they show that the relationshipNCp≥mincli∈Cp{Ncli} is satisfied in any patterns. Therefore, the relationship described in Formula (4) is always satisfied(4)supp⁡pos(p)≥supp⁡char.Formula (4) shows that the possible support of a pattern p1 gives the upper bound to characteristic supports of any super patterns (⊇p1). Therefore, if the possible support of p1 is smaller than the minimum support, the characteristic supports of the supper patterns are smaller than the minimum support. The supper patterns cannot be characteristic patterns. Thus, the discovery method keeps patterns whose possible supports are larger than or equal to the minimum support and whose frequencies are larger than or equal to the minimum frequency in order to grow them. The patterns are called possible patterns hereafter. Also, the discovery method extracts patterns whose characteristic supports are larger than or equal to the minimum support from the possible patterns. The discovery method based on the two-stepwise evaluation method can efficiently discover all characteristic patterns.


## 2.3. Discovery Method

This paper proposes a method that discovers all characteristic patterns from transactions with their classes. The method is based on the FP tree and the FP growth proposed by [4]. Here, the FP tree is the data structure storing transactions with tree format. The FP growth is a method discovering all frequent patterns by using the FP tree. The FP growth generates the FP trees from transaction subsets and generates new transaction subsets from generated FP trees. Two kinds of generation steps are recursively repeated. This paper proposes the refined FP tree and the refined FP growth in order to deal with transactions with classes.The original FP tree is composed of nodes assigned an item name and its frequency, links tying to the nodes with the same item name, a header table storing item, and links tying to items in the table with nodes including the item names. In the FP tree, the root node is a special node and is assigned “null”. The refined FP tree is basically equal to the original one. But, the refined one is assigned a pattern class and an identification flag to each item in the header table. Here, the flag shows whether the pattern corresponding to each item in the header table is included in a characteristic pattern. The refined FP tree is generated by an algorithm as shown in Table6 from transactions with their classes, item classes, and a conditioned item set. In the first generation of the refined FP tree, the conditioned item set is ϕ. In the generation except the first one, it is at least possible patterns. In this algorithm, the minimum support (∈(0,1]) and the minimum frequency (≥1) are predefined. Table 6 describes the difference of the generation method for the original one with bold style.Table 6
A generation method of the refined FP tree.
(1) Search transaction and calculate frequencies of each item.(2)Calculate a product set between a pattern classCIts  of a conditioned item set  Itsand an item classCiti  of each item  iti, and set the  product set as a pattern  classCpi  of a patternpi (=Its∪iti).(3)Calculate the total number and the minimum number forpi.(4)Calculate a characteristic  support and a possible support of  pi.(5) Repeat from step 2 to step 4 for anyi.(6)Extract items whose patterns are possible patterns and generate a listFlistarranged the items in descending order, where the first key is the frequency, the second key is the characteristic support, and the third key is the possible support.(7) Regard Flist as a header tableH in a refined FP tree T. Also, tieCpi to iti  in H. In addition, tie an identification flag  fli of  pi  to  iti  in  H.Here, if the pattern corresponding to  iti  is a characteristic  pattern, the value of  fli is “C”. Otherwise the value is“P”. That is, “C” shows that the pattern is a characteristic pattern and “P” shows that the pattern is not a characteristic pattern and is a possible pattern.(8) Create a root node ofT and assign the label “null” to it.(9) Set the root node as a target nodeN.(10) Pick up a transactiontj. If the transaction cannot be picked up, then this algorithm stops.(11) Pick up only items included inH from tj, sort them in the order of items in H, and create a selected and sorted item set Itstj.(12) Pick up an itemitjk from the top of Itstj. If the item cannot be picked up, then go to step 10.(13) If an item name ofitjk is assigned to a child node of N, then the frequency of the node is counted up. Otherwise, a new node N′ is created. N′ is assigned the item name of itjk and is set 1 to the frequency. Also, create a link between N and N′, and register N′ to itjk in H. In addition, regard a selected child node or N′ as a new target node N.(14) Go to step 12.In the following, we show an example which generates the refined FP tree from transactions and item classes as shown in Table7.Table 7
An example of transactions and item classes (3).
(a)
Transaction
t1=(cl1∣it1,it2,it3,it5)t2=(cl1∣it1,it3,it4)t3=(cl1∣it1,it2,it3,it4,it8)t4=(cl2∣it1,it2,it4,it7)t5=(cl2∣it4,it5,it6)t6=(cl2∣it1,it5,it6)t7=(cl2∣it1,it9)(b)
Item class
ItemClassit1{cl1,cl2}it2{cl1,cl2}it3{cl1}it4{cl1,cl2}it5{cl1,cl2}it6{cl2}it7{cl2}it8{cl1}it9{cl1,cl2}In this case, the item set isϕ. The minimum support is 0.5 and the minimum frequency is 1. The transactions of Table 7 show that frequencies of it1~it9 are 6, 3, 3, 4, 3, 2, 1, 1, and 1, respectively. The item classes of Table 7 show that the total transaction numbers for it1, it2, it4, it5, and it9 are 7, the ones for it3 and it8 are 3, and the ones for it6 and it7 are 4. Also, it shows that the minimum transaction numbers for it1, it2, it3, it4, it5, it8, and it9 are 3 and the ones for it6 and it7 are 4. Possible supports of it1~it9 are 2.00(=6/3), 1.00(=3/3), 1.00(=3/3), 1.33(=4/3), 1.00(=3/3), 0.50(=2/4), 0.25(=1/4), 0.33(=1/3), and 0.33(=1/3), respectively. Therefore, the generation method can select it1, it2, it3, it4, it5, and it6 as possible items. The items are arranged in the descending order of frequencies, characteristic supports, and possible supports. The method generates the list Flist such as (it1,it4,it3,it2,it5,it6). But, indexes of the items are used as the fourth key, if three criteria are equal to each other.Next, the method picks up possible items from the transactions and arranges the items in order of the Flist. It generates a selected and sorted transaction subset as shown in Table8. The subset is used in order to generate the refined FP tree.Table 8
A selected and sorted transaction subset.
t1′=(it1,it3,it2,it5)t2′=(it1,it4,it3)t3′=(it1,it4,it3,it2)t4′=(it1,it4,it2)t5′=(it4,it5,it6)t6′=(it1,it5,it6)t7′=(it1)In the case thatt1′ is selected from the subset, the method generates a part of the refined FP-tree as shown in Figure 1(a). Also, in the case that t2′ is selected from the subset, it generates a part of the refined FP tree as shown in Figure 1(b). That is, the method adds new nodes or updates the frequencies of the existing node in order from the root node. Lastly, the refined FP tree as shown in Figure 2 is generated.Refined FP tree (1).
(a)
Aftert1′(b)
Aftert2′Figure 2
Refined FP tree (2).In the remaining part of this subsection, we explain the refined FP growth. The original FP growth detects a single prefix path. The path is a path linked from the root. Each node included in the path has only a child. If an FP tree has the single prefix path, the original FP growth divides the FP-tree into the single prefix path and the remaining part. The remaining part is added a new root node and a new FP tree is generated. The original FP growth separately discovers frequent patterns from the new FP-tree and from the single prefix path. Also, it combines the patterns based on the tree with the patterns based on the path. The combined patterns are frequent patterns. The original FP growth can discover all frequent patterns based on the combination.On the other hand, in the case of the refined FP growth, we do not know whether characteristic supports increase as patterns grow. Even if characteristic patterns based on a single prefix path are given and characteristic patterns based on a new refined FP tree are given, their combinations are not always characteristic patterns. It is necessary to check whether the combinations are characteristic patterns by calculating their characteristic supports. The detection of the single prefix path does not give sufficient merits. Thus, the refined FP growth tries to discover characteristic patterns without detecting a single prefix path. In the following, we explain the FP growth without the detection.The refined FP growth picks up an item it from the rear of Flist in the refined FP tree in order. It generates transactions conditioned byit. That is, the refined FP growth extracts nodes including it from the refined FP tree and extracts paths from upper nodes of the extracted nodes to the root node. A transaction is generated from each path and is assigned frequency which is equal to the frequency of the node including it. The refined FP growth generates a new refined FP tree from the conditioned transactions. it is added to the conditioned item set Its. Here, Its is assigned to the previous refined FP tree and is ϕ in the first process of the refined FP growth. The refined FP growth recursively repeats the generation of refined FP trees and conditioned transactions.On the other hand, the refined FP growth needs pattern classes in order to calculate characteristic supports and possible supports. The pattern classes can be generated by referring to both items included in the patterns and their item classes. However, if the generation is always started from scratch, it is redundant. We can generate the pattern classes more efficiently by using a relationship among pattern classes. That is, if a patternp′ is generated by the combination of a pattern p and a new item it, a pattern class (Cp′) of p′ is equal to the product set (Cp∩Cit) based on both a pattern class (Cp) of p and an item class (Cit) of it. Therefore, the header table keeps pattern classes.According to the above discussion, the refined FP growth is described as shown in Table9. Table 9 describes the difference between the original FP growth and the refined one with bold style. The refined FP tree T and Its are input to the refined FP growth.Table 9
An algorithm of the refined FP growth algorithm.
(1) Extract an itemit from the rear of Flist in a refined FP tree T. If the item is not extracted, this algorithm stops.(2) Add it to an item set Its andinvestigate an identification flag of it. If the flag shows a characteristic pattern, then outputItsas a characteristic pattern.(3) Extract a nodeN whose item is equal to it from T. If the node is not extracted, then go to step 6.(4) Extract a path from the upper node ofN to the root. Generate an item set composed of item included in the extracted path and extract the frequency assigned to N. Regard the combination of the item set and the frequency as a transaction conditioned by it.(5) Go to step 3.(6) Apply a set Trans of the generated transactions to the algorithm shown in Table6 and generate a new refined FP tree T′. If T′ is not generated, then this algorithm stops. Otherwise, this algorithm recursively calls by giving T′ and Its to it as arguments.(7) Go to step 1.Lastly, a discovery method of characteristic patterns is described as shown in Table10. The method appropriately calls the algorithms as shown in Tables 6 and 9. It can generate all characteristic patterns from transactions with their classes, item classes, the minimum support, and the minimum frequency.Table 10
A discovery method of characteristic patterns.
(1) Search transactions and calculate the number of transactions for each class.(2) Setϕ to an item set Its and set all classes to its pattern class.(3) Generate a refined FP treeT based on the algorithm shown in Table 6.(4) IfT is not generated, then this algorithm stops. Otherwise, it discovers characteristic patterns from T and Its based on the algorithm shown in Table 9.


## 3. Numerical Experiments

### 3.1. Data

This paper uses the UCI data sets registered in the UCI machine learning repository for numerical experiments. Also, it uses the RFID data sets collected from two apparel shops. In the case of the UCI data sets, three data sets “car”, “hayes”, and “nursery” are selected. This is because each data set is a data set for the classification task and is composed of discrete values. These data sets are tabular structured data. Each example in the data sets is composed of attribute values and a class and is regarded as a transaction. Then, the combination of an attribute and an attribute value is regarded as an item. A class of an example is regarded as a class of a transaction. The item classes are generated by checking the combinations of attribute values and classes. Table11 shows features of transactions generated from the UCI data sets.Table 11
UCI data sets.
Data setItemTransactionClassCar2117284Hayes151603Nursery27129605The RFID data sets are data sets collected in order to analyze a relationship between sales volume and actions of customers in the shops. RFID readers are set to fitting rooms, shelves, and cash registers, and RFID tags are assigned to sales items. We can grasp the actions of the customers by chasing the items to some extent. In this experiment, we regard the difference between fitting items and no fitting items as classes. This is because the fitting of items is one of the important customer actions but its frequency is not always high. Table12 shows the distribution of classes in transactions. We can confirm that the number of fitting items is much smaller than the one of no fitting items.Table 12
RFID data sets.
ShopNo fittingFittingα shop36951372β shop76121849


### 3.2. Method

We compare the proposed method with the existing method [4], but the process of a single prefix path is not incorporated in it. The existing method is a discovery method of frequent patterns. It does not deal with classes. Also, it ignores classes assigned to transactions and item classes corresponding to each item. The proposed method aims at discovering at most hundreds of patterns. The minimum supports and the minimum frequencies are adjusted.In the case of the UCI data sets, the proposed method discovers characteristic patterns by changing the minimum frequencies. The minimum support is fixed. Also, the proposed method outputs possible patterns in order to evaluate investigated patterns. On the other hand, the existing method discovers frequent patterns by changing the minimum frequencies. The minimum support is directly calculated by referring to the frequencies. The frequencies depend on both the minimum supports and the minimum frequencies of the proposed method. This experiment evaluates relationships between discovered patterns, minimum supports, and minimum frequencies.In the case of the RFID data sets, this experiment focuses on the difference of characteristic patterns and frequent patterns. The proposed method and the existing method discover patterns by changing the minimum supports. The minimum frequency in the proposed method is fixed. This experiment evaluates the validity of the discovered patterns.


### 3.3. Experimental Results

Figures3, 4, and 5 show experimental results in the case of the UCI data sets: “cars”, “hayes”, and “nursery”, respectively. Graph (a) and Graph (b) show the difference of characteristic patterns and frequent patterns. Graph (a) shows the total number of patterns. In this graph, we do not care about the number of items included in patterns. The number is called the length hereafter.Experimental result in the case of the data set “car”.
(a)
Characteristic pattern and frequent pattern(b)
Characteristic pattern and frequent pattern (Length = 2)(c)
Possible pattern and frequent pattern (Total)(d)
Calculation timeExperimental result in the case of the data set “hayes”.
(a)
Characteristic pattern and frequent pattern (Total)(b)
Characteristic pattern and frequent pattern (Length = 2)(c)
Possible pattern and frequent pattern (Total)(d)
Calculation timeExperimental result in the case of the data set “nursery”.
(a)
Characteristic pattern and frequent pattern (Total)(b)
Characteristic pattern and frequent pattern (Length = 3)(c)
Characteristic pattern and frequent pattern (Total)(d)
Calculation timeGraph (b) shows the difference of characteristic patterns and frequent patterns in the case of specific length. The lengths in the case of “cars,” “hayes,” and “nursery,” are 2, 2, and 3, respectively. In each graph, “Class only” shows the number of patterns discovered only by the proposed method. “Class common” shows the numbers discovered by both the proposed method and the existing method. “No class only” shows the numbers discovered only by the existing method. But, in the case of the proposed method, the minimum support is fixed to 0.100. Also, the minimum frequencies in the case of “car" are 9, 18, 52, 87, and 173. The ones in the case of “hayes” are 1, 2, 5, 8, and 16. The ones in the case of “nursery” are 65, 130, 389, 649, and 1297. They correspond to the minimum supports of the existing method: 0.005, 0.010, 0.030, 0.050, and 0.100. In the case of the existing method, the minimum frequency for the data sets: “car”, “hayes”, and “nursery” are fixed and they are 173, 16, and 1297, respectively. They correspond to the minimum support 0.100.Graph (c) shows the difference of possible patterns and frequent patterns. The thresholds in the proposed method are equal to the case of Graph (a) and Graph (b). The minimum supports in the existing method are changed according to the frequencies in the proposed method. In each graph, “Class” shows the total number of possible patterns and “No class” shows the total number of frequent patterns.Graph (d) shows the calculation time of both the proposed method and the existing method. But, the calculation time of the existing method is estimated by modifying the program code of the proposed method. That is, the calculation of the characteristic support and the possible support, and the evaluation based on them are gotten rid of the program code. On the other hand, other additional processes are left because their calculation cost is comparatively small. The modified program code is used to the estimation of the calculation time for the existing method. In the experiment, the calculation time is measured by using the DOS command “time” with millisecond unit. The experiment uses the computer environment such as Windows 7 Home Premium Service Pack 1 and TOSHIBA dynabook Satellite PXW/59KW loading Intel Core(TM)2 Duo CPU T9600@2.80 GHz and 4.00 GB RAM memory. The program code is described by C language and is compiled by gcc command in MinGW-5.1.6.exe. In the case of the proposed method, the minimum support is fixed to 0.100 and the minimum frequencies are changed. The frequencies are used in the evaluation of the existing method.In these graphs, horizontal axes are the minimum supports, and vertical axes except Graph (d) are the number of patterns. In Graph (d), vertical axes are the calculation time, and their calculation unit is millisecond.Figure6 shows experimental results in the case of the RFID data sets. In this experiment, the minimum frequency is 2 in the proposed method. The minimum supports are changed from 0.001 to 0.005 per 0.001 in the proposed method and the existing method. Graph (a) and Graph (b) show the total number of patterns in the case of α shop and β shop, respectively. In these graphs, “Class only”, “Class common”, “No class”, and the axes correspond to the ones in the case of the UCI data sets. On the other hand, Tables 13 and 14 show patterns discovered only by the proposed method from each shop. In these tables, the minimum support is 0.001, and the length is larger than or equal to 2.Table 13
Discovered patterns fromα shop.
PatternClassA-type jacket, A-type skirtFittingX-type stole, Y-type gift boxNo fittingB-type one-piece wear, B-type jacketFittingC-type jacket, D-type skirtFittingC-type jacket, C-type skirtFittingE-type jacket, E-type pantsFittingB-type jacket, B-type skirtFittingF-type jacket, F-type skirtFittingF-type jacket, G-type skirtFittingF-type jacket, H-type blouseFittingG-type skirt, H-type blouseFittingF-type jacket, G-type skirt, H-type blouseFittingTable 14
Discovered patterns fromβ shop.
PatternClassI-type one-piece wear, H-type necklaceFittingC-type jacket, C-type pantsFittingK-type jacket, K-type skirtFittingExperimental result in the case of the RFID data sets.
(a)
α shop(b)
β shop


### 3.4. Discussions

This section discusses the effect of the proposed method due to seven viewpoints: “difference of discovered patterns”, “validity of discovered patterns”, “frequency of items”, “calculation time”, “complexity of the refined FP tree”, “pre-processing method”, and “generality”.


#### 3.4.1. Difference of Discovered Patterns

Graph (a) and Graph (b) show that there are many patterns discovered only by the proposed method. Especially, when the minimum frequencies in the proposed method are small, the numbers of the patterns are big. We can anticipate that analysts are interested in the patterns because the ratios included in a specific class set are comparatively high. On the other hand, it is difficult for the existing method to discover the patterns. If the existing method tries to discover them, it is necessary to set smaller minimum frequencies. However, the smaller minimum frequencies tend to discover many frequent patterns. The existing method may overlook important patterns because the patterns are hidden in many frequent patterns. In order to avoid the overlook, we may be able to perform a two-stepwise method. The method combines the existing method with a postprocessing method. That is, the first step discovers frequent patterns by applying the existing method to its smaller minimum frequencies. The second step extracts characteristic patterns from the discovered patterns by evaluating their characteristic supports. However, Graph (c) shows that the number of possible patterns is smaller than the number of frequent patterns. The former numbers are 0.376 times, 0.461 times, and 0.404 times as small as the latter numbers in the case of “car", “hayes”, and “nursery”, respectively. The proposed method can discover all characteristic patterns by investigating possible patterns whose number is less than half as small as the numbers based on the existing method. The proposed method is more efficient method with calculation cost.


#### 3.4.2. Validity of Discovered Patterns

Tables13 and 14 show that the proposed method discovers many patterns composed of a top wear and a bottom wear. If a customer is interested in only the top wear, the top wear is not usually fitted in a fitting room. However, if the customer is interested in the combination of the top wear and the bottom wear, the customer tends to fit the combination. The discovered patterns show the combination. On the other hand, the fitting is one of troublesome actions for the customer. The sales volume without the fitting is much larger than the one with the fitting. It is difficult for the existing method to discover patterns related to the fitting. We can think that the proposed method discovers more valid patterns than the existing method does. In future work, we will try to show the patterns to retailers in the apparel shops and verify the validity of the patterns in detail.


#### 3.4.3. Frequency of Items

In the case of “car” and “nursery”, characteristic patterns whose length is 1 completely correspond to frequent patterns whose length is 1. Characteristic patterns whose length is more than equal to 2 include patterns which the existing method cannot discover. This is because characteristic supports increase as the number of classes included in pattern classes decreases. The proposed method discovers the characteristic patterns related to the combination of specific classes. We think that the feature of the proposed method is experimentally confirmed.


#### 3.4.4. Calculation Time

The results in Figures3–5 show that the shapes of Graph (c) are similar to the ones of Graph (d). That is, the calculation time depends on the number of the patterns. It does not almost depend on the additional calculation cost related to the proposed method. The additional calculation cost of the proposed method is not so big. We can anticipate that the proposed method speedily discovers the patterns because it investigates small combinations of items.


#### 3.4.5. Complexity of the Refined FP-Tree

The refined FP-tree has pattern classes and ID flags in the header table. It requires additional memory. However, the nodes composing the refined FP-tree occupy the greater part of memory. This is because the number of transactions and the one of items are much larger than the number of classes. We think that the additional memory is not a big problem.


#### 3.4.6. Preprocessing Method

Even if the existing method directly cannot deal with classes, a combination method of the existing method and a preprocessing method may be able to deal with them. That is, the preprocessing method can divide transactions into some transaction subsets by referring to the classes. The existing method can discover frequent patterns from divided transaction subsets. The combination method may be able to discover all characteristic patterns. However, if the number of classes is large, the combinations of classes exponentially increase. In addition, we do not usually have the knowledge for useful combinations of classes. It is necessary to discover patterns from various transaction subsets. The combination method requires large amount of calculation cost. On the other hand, the proposed method can discover characteristic patterns without requiring the additional knowledge. Therefore, the proposed method is more efficient than the combination method.


#### 3.4.7. Generality

We can regard various conditions as classes. For example, in a retail field, the difference of sales period, shop, and salesperson is regarded as classes. Also, in a sensor network field, the difference of area, data collection interval, and data detection range is regarded as classes. Therefore, we think that the proposed method has high generality. The proposed method can analyze data with various viewpoints by using the classes.According to the discussions, we believe that the proposed method can perform more efficient analysis for transactions.


## 3.1. Data

This paper uses the UCI data sets registered in the UCI machine learning repository for numerical experiments. Also, it uses the RFID data sets collected from two apparel shops. In the case of the UCI data sets, three data sets “car”, “hayes”, and “nursery” are selected. This is because each data set is a data set for the classification task and is composed of discrete values. These data sets are tabular structured data. Each example in the data sets is composed of attribute values and a class and is regarded as a transaction. Then, the combination of an attribute and an attribute value is regarded as an item. A class of an example is regarded as a class of a transaction. The item classes are generated by checking the combinations of attribute values and classes. Table11 shows features of transactions generated from the UCI data sets.Table 11
UCI data sets.
Data setItemTransactionClassCar2117284Hayes151603Nursery27129605The RFID data sets are data sets collected in order to analyze a relationship between sales volume and actions of customers in the shops. RFID readers are set to fitting rooms, shelves, and cash registers, and RFID tags are assigned to sales items. We can grasp the actions of the customers by chasing the items to some extent. In this experiment, we regard the difference between fitting items and no fitting items as classes. This is because the fitting of items is one of the important customer actions but its frequency is not always high. Table12 shows the distribution of classes in transactions. We can confirm that the number of fitting items is much smaller than the one of no fitting items.Table 12
RFID data sets.
ShopNo fittingFittingα shop36951372β shop76121849


## 3.2. Method

We compare the proposed method with the existing method [4], but the process of a single prefix path is not incorporated in it. The existing method is a discovery method of frequent patterns. It does not deal with classes. Also, it ignores classes assigned to transactions and item classes corresponding to each item. The proposed method aims at discovering at most hundreds of patterns. The minimum supports and the minimum frequencies are adjusted.In the case of the UCI data sets, the proposed method discovers characteristic patterns by changing the minimum frequencies. The minimum support is fixed. Also, the proposed method outputs possible patterns in order to evaluate investigated patterns. On the other hand, the existing method discovers frequent patterns by changing the minimum frequencies. The minimum support is directly calculated by referring to the frequencies. The frequencies depend on both the minimum supports and the minimum frequencies of the proposed method. This experiment evaluates relationships between discovered patterns, minimum supports, and minimum frequencies.In the case of the RFID data sets, this experiment focuses on the difference of characteristic patterns and frequent patterns. The proposed method and the existing method discover patterns by changing the minimum supports. The minimum frequency in the proposed method is fixed. This experiment evaluates the validity of the discovered patterns.


## 3.3. Experimental Results

Figures3, 4, and 5 show experimental results in the case of the UCI data sets: “cars”, “hayes”, and “nursery”, respectively. Graph (a) and Graph (b) show the difference of characteristic patterns and frequent patterns. Graph (a) shows the total number of patterns. In this graph, we do not care about the number of items included in patterns. The number is called the length hereafter.Experimental result in the case of the data set “car”.
(a)
Characteristic pattern and frequent pattern(b)
Characteristic pattern and frequent pattern (Length = 2)(c)
Possible pattern and frequent pattern (Total)(d)
Calculation timeExperimental result in the case of the data set “hayes”.
(a)
Characteristic pattern and frequent pattern (Total)(b)
Characteristic pattern and frequent pattern (Length = 2)(c)
Possible pattern and frequent pattern (Total)(d)
Calculation timeExperimental result in the case of the data set “nursery”.
(a)
Characteristic pattern and frequent pattern (Total)(b)
Characteristic pattern and frequent pattern (Length = 3)(c)
Characteristic pattern and frequent pattern (Total)(d)
Calculation timeGraph (b) shows the difference of characteristic patterns and frequent patterns in the case of specific length. The lengths in the case of “cars,” “hayes,” and “nursery,” are 2, 2, and 3, respectively. In each graph, “Class only” shows the number of patterns discovered only by the proposed method. “Class common” shows the numbers discovered by both the proposed method and the existing method. “No class only” shows the numbers discovered only by the existing method. But, in the case of the proposed method, the minimum support is fixed to 0.100. Also, the minimum frequencies in the case of “car" are 9, 18, 52, 87, and 173. The ones in the case of “hayes” are 1, 2, 5, 8, and 16. The ones in the case of “nursery” are 65, 130, 389, 649, and 1297. They correspond to the minimum supports of the existing method: 0.005, 0.010, 0.030, 0.050, and 0.100. In the case of the existing method, the minimum frequency for the data sets: “car”, “hayes”, and “nursery” are fixed and they are 173, 16, and 1297, respectively. They correspond to the minimum support 0.100.Graph (c) shows the difference of possible patterns and frequent patterns. The thresholds in the proposed method are equal to the case of Graph (a) and Graph (b). The minimum supports in the existing method are changed according to the frequencies in the proposed method. In each graph, “Class” shows the total number of possible patterns and “No class” shows the total number of frequent patterns.Graph (d) shows the calculation time of both the proposed method and the existing method. But, the calculation time of the existing method is estimated by modifying the program code of the proposed method. That is, the calculation of the characteristic support and the possible support, and the evaluation based on them are gotten rid of the program code. On the other hand, other additional processes are left because their calculation cost is comparatively small. The modified program code is used to the estimation of the calculation time for the existing method. In the experiment, the calculation time is measured by using the DOS command “time” with millisecond unit. The experiment uses the computer environment such as Windows 7 Home Premium Service Pack 1 and TOSHIBA dynabook Satellite PXW/59KW loading Intel Core(TM)2 Duo CPU T9600@2.80 GHz and 4.00 GB RAM memory. The program code is described by C language and is compiled by gcc command in MinGW-5.1.6.exe. In the case of the proposed method, the minimum support is fixed to 0.100 and the minimum frequencies are changed. The frequencies are used in the evaluation of the existing method.In these graphs, horizontal axes are the minimum supports, and vertical axes except Graph (d) are the number of patterns. In Graph (d), vertical axes are the calculation time, and their calculation unit is millisecond.Figure6 shows experimental results in the case of the RFID data sets. In this experiment, the minimum frequency is 2 in the proposed method. The minimum supports are changed from 0.001 to 0.005 per 0.001 in the proposed method and the existing method. Graph (a) and Graph (b) show the total number of patterns in the case of α shop and β shop, respectively. In these graphs, “Class only”, “Class common”, “No class”, and the axes correspond to the ones in the case of the UCI data sets. On the other hand, Tables 13 and 14 show patterns discovered only by the proposed method from each shop. In these tables, the minimum support is 0.001, and the length is larger than or equal to 2.Table 13
Discovered patterns fromα shop.
PatternClassA-type jacket, A-type skirtFittingX-type stole, Y-type gift boxNo fittingB-type one-piece wear, B-type jacketFittingC-type jacket, D-type skirtFittingC-type jacket, C-type skirtFittingE-type jacket, E-type pantsFittingB-type jacket, B-type skirtFittingF-type jacket, F-type skirtFittingF-type jacket, G-type skirtFittingF-type jacket, H-type blouseFittingG-type skirt, H-type blouseFittingF-type jacket, G-type skirt, H-type blouseFittingTable 14
Discovered patterns fromβ shop.
PatternClassI-type one-piece wear, H-type necklaceFittingC-type jacket, C-type pantsFittingK-type jacket, K-type skirtFittingExperimental result in the case of the RFID data sets.
(a)
α shop(b)
β shop


## 3.4. Discussions

This section discusses the effect of the proposed method due to seven viewpoints: “difference of discovered patterns”, “validity of discovered patterns”, “frequency of items”, “calculation time”, “complexity of the refined FP tree”, “pre-processing method”, and “generality”.


### 3.4.1. Difference of Discovered Patterns

Graph (a) and Graph (b) show that there are many patterns discovered only by the proposed method. Especially, when the minimum frequencies in the proposed method are small, the numbers of the patterns are big. We can anticipate that analysts are interested in the patterns because the ratios included in a specific class set are comparatively high. On the other hand, it is difficult for the existing method to discover the patterns. If the existing method tries to discover them, it is necessary to set smaller minimum frequencies. However, the smaller minimum frequencies tend to discover many frequent patterns. The existing method may overlook important patterns because the patterns are hidden in many frequent patterns. In order to avoid the overlook, we may be able to perform a two-stepwise method. The method combines the existing method with a postprocessing method. That is, the first step discovers frequent patterns by applying the existing method to its smaller minimum frequencies. The second step extracts characteristic patterns from the discovered patterns by evaluating their characteristic supports. However, Graph (c) shows that the number of possible patterns is smaller than the number of frequent patterns. The former numbers are 0.376 times, 0.461 times, and 0.404 times as small as the latter numbers in the case of “car", “hayes”, and “nursery”, respectively. The proposed method can discover all characteristic patterns by investigating possible patterns whose number is less than half as small as the numbers based on the existing method. The proposed method is more efficient method with calculation cost.


### 3.4.2. Validity of Discovered Patterns

Tables13 and 14 show that the proposed method discovers many patterns composed of a top wear and a bottom wear. If a customer is interested in only the top wear, the top wear is not usually fitted in a fitting room. However, if the customer is interested in the combination of the top wear and the bottom wear, the customer tends to fit the combination. The discovered patterns show the combination. On the other hand, the fitting is one of troublesome actions for the customer. The sales volume without the fitting is much larger than the one with the fitting. It is difficult for the existing method to discover patterns related to the fitting. We can think that the proposed method discovers more valid patterns than the existing method does. In future work, we will try to show the patterns to retailers in the apparel shops and verify the validity of the patterns in detail.


### 3.4.3. Frequency of Items

In the case of “car” and “nursery”, characteristic patterns whose length is 1 completely correspond to frequent patterns whose length is 1. Characteristic patterns whose length is more than equal to 2 include patterns which the existing method cannot discover. This is because characteristic supports increase as the number of classes included in pattern classes decreases. The proposed method discovers the characteristic patterns related to the combination of specific classes. We think that the feature of the proposed method is experimentally confirmed.


### 3.4.4. Calculation Time

The results in Figures3–5 show that the shapes of Graph (c) are similar to the ones of Graph (d). That is, the calculation time depends on the number of the patterns. It does not almost depend on the additional calculation cost related to the proposed method. The additional calculation cost of the proposed method is not so big. We can anticipate that the proposed method speedily discovers the patterns because it investigates small combinations of items.


### 3.4.5. Complexity of the Refined FP-Tree

The refined FP-tree has pattern classes and ID flags in the header table. It requires additional memory. However, the nodes composing the refined FP-tree occupy the greater part of memory. This is because the number of transactions and the one of items are much larger than the number of classes. We think that the additional memory is not a big problem.


### 3.4.6. Preprocessing Method

Even if the existing method directly cannot deal with classes, a combination method of the existing method and a preprocessing method may be able to deal with them. That is, the preprocessing method can divide transactions into some transaction subsets by referring to the classes. The existing method can discover frequent patterns from divided transaction subsets. The combination method may be able to discover all characteristic patterns. However, if the number of classes is large, the combinations of classes exponentially increase. In addition, we do not usually have the knowledge for useful combinations of classes. It is necessary to discover patterns from various transaction subsets. The combination method requires large amount of calculation cost. On the other hand, the proposed method can discover characteristic patterns without requiring the additional knowledge. Therefore, the proposed method is more efficient than the combination method.


### 3.4.7. Generality

We can regard various conditions as classes. For example, in a retail field, the difference of sales period, shop, and salesperson is regarded as classes. Also, in a sensor network field, the difference of area, data collection interval, and data detection range is regarded as classes. Therefore, we think that the proposed method has high generality. The proposed method can analyze data with various viewpoints by using the classes.According to the discussions, we believe that the proposed method can perform more efficient analysis for transactions.


## 3.4.1. Difference of Discovered Patterns

Graph (a) and Graph (b) show that there are many patterns discovered only by the proposed method. Especially, when the minimum frequencies in the proposed method are small, the numbers of the patterns are big. We can anticipate that analysts are interested in the patterns because the ratios included in a specific class set are comparatively high. On the other hand, it is difficult for the existing method to discover the patterns. If the existing method tries to discover them, it is necessary to set smaller minimum frequencies. However, the smaller minimum frequencies tend to discover many frequent patterns. The existing method may overlook important patterns because the patterns are hidden in many frequent patterns. In order to avoid the overlook, we may be able to perform a two-stepwise method. The method combines the existing method with a postprocessing method. That is, the first step discovers frequent patterns by applying the existing method to its smaller minimum frequencies. The second step extracts characteristic patterns from the discovered patterns by evaluating their characteristic supports. However, Graph (c) shows that the number of possible patterns is smaller than the number of frequent patterns. The former numbers are 0.376 times, 0.461 times, and 0.404 times as small as the latter numbers in the case of “car", “hayes”, and “nursery”, respectively. The proposed method can discover all characteristic patterns by investigating possible patterns whose number is less than half as small as the numbers based on the existing method. The proposed method is more efficient method with calculation cost.


## 3.4.2. Validity of Discovered Patterns

Tables13 and 14 show that the proposed method discovers many patterns composed of a top wear and a bottom wear. If a customer is interested in only the top wear, the top wear is not usually fitted in a fitting room. However, if the customer is interested in the combination of the top wear and the bottom wear, the customer tends to fit the combination. The discovered patterns show the combination. On the other hand, the fitting is one of troublesome actions for the customer. The sales volume without the fitting is much larger than the one with the fitting. It is difficult for the existing method to discover patterns related to the fitting. We can think that the proposed method discovers more valid patterns than the existing method does. In future work, we will try to show the patterns to retailers in the apparel shops and verify the validity of the patterns in detail.


## 3.4.3. Frequency of Items

In the case of “car” and “nursery”, characteristic patterns whose length is 1 completely correspond to frequent patterns whose length is 1. Characteristic patterns whose length is more than equal to 2 include patterns which the existing method cannot discover. This is because characteristic supports increase as the number of classes included in pattern classes decreases. The proposed method discovers the characteristic patterns related to the combination of specific classes. We think that the feature of the proposed method is experimentally confirmed.


## 3.4.4. Calculation Time

The results in Figures3–5 show that the shapes of Graph (c) are similar to the ones of Graph (d). That is, the calculation time depends on the number of the patterns. It does not almost depend on the additional calculation cost related to the proposed method. The additional calculation cost of the proposed method is not so big. We can anticipate that the proposed method speedily discovers the patterns because it investigates small combinations of items.


## 3.4.5. Complexity of the Refined FP-Tree

The refined FP-tree has pattern classes and ID flags in the header table. It requires additional memory. However, the nodes composing the refined FP-tree occupy the greater part of memory. This is because the number of transactions and the one of items are much larger than the number of classes. We think that the additional memory is not a big problem.


## 3.4.6. Preprocessing Method

Even if the existing method directly cannot deal with classes, a combination method of the existing method and a preprocessing method may be able to deal with them. That is, the preprocessing method can divide transactions into some transaction subsets by referring to the classes. The existing method can discover frequent patterns from divided transaction subsets. The combination method may be able to discover all characteristic patterns. However, if the number of classes is large, the combinations of classes exponentially increase. In addition, we do not usually have the knowledge for useful combinations of classes. It is necessary to discover patterns from various transaction subsets. The combination method requires large amount of calculation cost. On the other hand, the proposed method can discover characteristic patterns without requiring the additional knowledge. Therefore, the proposed method is more efficient than the combination method.


## 3.4.7. Generality

We can regard various conditions as classes. For example, in a retail field, the difference of sales period, shop, and salesperson is regarded as classes. Also, in a sensor network field, the difference of area, data collection interval, and data detection range is regarded as classes. Therefore, we think that the proposed method has high generality. The proposed method can analyze data with various viewpoints by using the classes.According to the discussions, we believe that the proposed method can perform more efficient analysis for transactions.


## 4. Summary and Future Work

This paper proposed a method that discovers characteristic patterns from transactions with their classes. The method regards the difference of conditions in the data collection as classes. This paper redefined the possible support and the characteristic support in order to efficiently discover the patterns. Lastly, it verified the effect of the proposed method through numerical experiments based on three data sets registered in the UCI machine learning repository and two data sets collected by RFID readers and RFID tags set in apparel shops.In future work, we try to improve the proposed method with a viewpoint of calculation speed. For example, we consider a method that calculates smaller possible supports in order to decrease the number of possible patterns. Concretely, we try to use relationships between the growth of patterns and their pattern classes. We believe that the relationships can estimate the possible supports as smaller values. Also, we try to reconsider the use of the single prefix path. In this paper, we ignore the path because characteristic patterns cannot be simply discovered from the combination of the single prefix path and the remaining FP tree. However, similar combinations may be useful for the speedy discovery. It is necessary to investigate the feature of the combinations in detail. In addition, we will consider to use the class information in nodes of a refined FP tree. The use may lead to the discovery of more valid patterns. On the other hand, it leads to a more complex FP tree with high calculation cost. It is important to clarify the relationships between the validity of patterns and the complexity of the FP tree. Lastly, we will try to apply the proposed method to many data sets in order to verify its effect in detail.The discovery task from transactions without classes is expanding the research field more and more. The expansion may be useful for the discovery task from transactions with their classes. We try to incorporate the expansion in the proposed method.



---

*Source: 786387-2012-04-22.xml*