JP2010191914A - Characteristic pattern extraction device, characteristic pattern extraction method, classification support device, and classification support method - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To efficiently generate information available for decision making support. <P>SOLUTION: A characteristic pattern extraction device includes: a reception part 111 for receiving input of an item set associated with a class for classifying the set, the set including at least one item showing information to be analyzed; a candidate generation part 113 for generating a candidate pattern including at least one item included in the item set, which is a candidate of a characteristic pattern characteristic to a pattern of the item included in the item set; a characteristic extraction part 114 for calculating an appearance frequency of a candidate pattern in the item set associated with the class in each class, and extracting the characteristic pattern which is a candidate pattern satisfying a condition with the calculated appearance frequency set thereto in advance; and a display part 130 for outputting the extracted characteristic pattern. <P>COPYRIGHT: (C)2010,JPO&INPIT

Description

  The present invention relates to a feature pattern extraction device, a feature pattern extraction method, a classification support device, and a classification support method.

  In Non-Patent Document 1, by collecting a large number of receipts indicating a list of purchased items, an efficient association rule that reveals other items or item sets to be purchased in relation to a specific item or item set is efficiently used. The technology to discover is proposed.

  The discovery method disclosed in Non-Patent Document 1 is a technique developed on the assumption of receipts used in the retail industry and the like, but is used in various fields having the same kind of data. Moreover, the correlation rule discovered by such a method is utilized for decision support.

  Patent Document 1 proposes a technique for discovering a correlation rule for each data group, and performing statistical processing using the data group as an explanatory variable, an item corresponding to a condition part of the correlation rule, and an item corresponding to a conclusion part as an explanatory variable. Yes. Further, Patent Document 1 proposes a technique for visualizing the difference in the tendency of data groups by assigning a condition part score and a conclusion part score to each item so that the correlation rules are developed on coordinates.

JP 2002-259127 A

“Mining Sequential Patterns”, R. Agrawal and R. Srikant, Proc. 11th Int. Conf. On Data Engineering, pp. 3-14 (1995)

  However, the method of Non-Patent Document 1 is a method for finding a characteristic pattern inherent in an item set, and cannot find an underlying relationship between the patterns. If the method of patent document 1 is utilized, the correlation rule obtained from a different data group can be compared visually. However, in the method of Patent Document 1, it is necessary for a user to determine which part of an item or item set is caused by a difference in different data groups. In other words, it was not possible to automatically extract the factors that explain the difference between the data groups and model the difference.

  The present invention has been made in view of the above, and provides a feature pattern extraction device, a feature pattern extraction method, a classification support device, and a classification support method that can efficiently generate information that can be used for decision support. The purpose is to provide.

  In order to solve the above-described problems and achieve the object, the present invention is a set including at least one item representing information to be analyzed, the item set being associated with a class into which the set is classified. An accepting unit that accepts an input, and a candidate for generating a candidate pattern that is a candidate for a feature pattern that represents a characteristic pattern among item patterns included in the item set, and that includes at least one item included in the item set For each class, the generation unit calculates the appearance frequency of the candidate pattern in the item set associated with the class, and the calculated appearance frequency is the candidate pattern that satisfies a predetermined condition A feature extraction unit that extracts a feature pattern; and an output unit that outputs the extracted feature pattern; That.

  In addition, the present invention is a set including at least one item representing information to be analyzed, and includes an accepting unit that receives an input of an item set that associates a class to which the set is classified, and the item set includes A candidate generation unit that generates a candidate pattern including at least one item included in the item set, and a candidate generation unit that generates a candidate pattern including a characteristic pattern among the item patterns to be generated, A feature extraction unit that calculates an appearance frequency of the candidate pattern in the associated item set, and extracts the feature pattern that is the candidate pattern in which the calculated appearance frequency satisfies a predetermined condition; and the item For each set, indicates whether the extracted feature pattern is included in the item set For classifying a set including the item into one of the classes based on an attribute generation unit that generates a sex vector, the generated attribute vector, and the class associated with the item set A model generation unit that generates a classification model, and an output unit that outputs the generated classification model.

  The present invention is also a method that can be performed by the above apparatus.

  According to the present invention, it is possible to efficiently generate information that can be used for decision support.

FIG. 1 is a block diagram illustrating an example of the configuration of the feature pattern extraction apparatus according to the first embodiment. FIG. 2 is a diagram illustrating an example of a data structure of data stored in the input data storage unit. FIG. 3 is a diagram illustrating an example of a data structure of data stored in the candidate storage unit. FIG. 4 is a diagram illustrating an example of a data structure of data stored in the feature storage unit. FIG. 5 is a flowchart showing the overall flow of the feature pattern display process in the first embodiment. FIG. 6 is a flowchart showing the overall flow of the feature pattern extraction process in the first embodiment. FIG. 7 is a flowchart showing an overall flow of the feature pattern extraction process in the first embodiment. FIG. 8 is a diagram illustrating an example of the appearance frequency calculated for a set of candidate patterns and classes. FIG. 9 is a diagram illustrating an example of a calculation result of the calculated appearance frequency. FIG. 10 is a diagram illustrating an example of a calculation result of the calculated appearance frequency. FIG. 11 is a diagram illustrating an example of a calculation result of the calculated appearance frequency. FIG. 12 is a block diagram illustrating an example of the configuration of the classification support apparatus according to the second embodiment. FIG. 13 is a flowchart illustrating an overall flow of the classification support processing in the second embodiment. FIG. 14 is a diagram illustrating an example of the generated attribute vector. FIG. 15 is a diagram illustrating an example of the generated classification model. FIG. 16 is an explanatory diagram illustrating a hardware configuration of the device according to the first or second embodiment.

  Exemplary embodiments of a feature pattern extraction device, a feature pattern extraction method, a classification support device, and a classification support method according to the present invention will be explained below in detail with reference to the accompanying drawings.

(First embodiment)
In the conventional correlation rule finding methods such as Non-Patent Document 1 and Patent Document 1, it is assumed that a large number of item sets that are not particularly distinguished are given as inputs. For this reason, even if a given item set is classified according to some criteria, the item set cannot be analyzed in consideration of the classification.

  However, there are many data in which item sets are classified according to some criteria, such as an item set of purchased products and an item set not purchased. For this reason, it has been required to analyze the relationship between specific item subsets in consideration of classes determined by specific classification criteria.

  For example, with the spread of RFID tags and RFID readers, not only the event of product purchase at a cash register (product purchase event), but also the event that a product taken out of a shelf is returned to the shelf again can be recognized It has become. An event associated with such a return can be interpreted as an event indicating that a product has not been purchased (a product not purchased event). In this example, for example, it is required to analyze characteristics between a product purchase event and a product non-purchase event.

  Therefore, the feature pattern extraction apparatus according to the first embodiment extracts and outputs a feature pattern in consideration of the class based on an item set to which a class determined by a predetermined classification criterion is assigned. To do.

  Note that an item represents information to be analyzed, and is characterized by an attribute value representing a value of a predetermined attribute. For example, a product to be purchased corresponds to an item. In this case, each product name corresponds to an attribute value. Although the example which uses goods as an item is demonstrated below, an item is not restricted to goods. For example, individual features that characterize a product, such as the color and size of the product, can be regarded as items.

  A class represents classification information for classifying a set of items (item set). For example, when a product is an item, the item set can be classified according to whether or not each product included in the item set is purchased. In this case, the item set is classified into a class of “purchased” or “not purchased”, for example. The class is not limited to this, and any information can be applied as long as the information can classify the item set according to a predetermined classification standard. In addition to the class classified into two, a class classified into three or more may be used.

  The characteristic pattern represents a characteristic pattern among patterns obtained by combining items included in the item set.

  FIG. 1 is a block diagram illustrating an example of the configuration of the feature pattern extraction apparatus 100 according to the first embodiment. As illustrated in FIG. 1, the feature pattern extraction apparatus 100 includes an input data storage unit 121, a candidate storage unit 122, a feature storage unit 123, a feature generation unit 110, and a display unit 130.

The input data storage unit 121 stores an item set to which classes are assigned. FIG. 2 is a diagram illustrating an example of a data structure of data stored in the input data storage unit 121. As shown in FIG. 2, the input data storage unit 121 stores data in which an item set is associated with a class. In the figure, for convenience of explanation, identification information (t _{0 to} t ₉ ) for identifying an item set is described, but such identification information need not be stored in the input data storage unit 121.

  Returning to FIG. 1, the candidate storage unit 122 is a candidate pattern (hereinafter referred to as an element of a candidate pattern to be generated next) among candidate patterns generated by a candidate generation unit 113 described later as a pattern that is a candidate for a feature pattern. , Called candidate elements). Specifically, the candidate storage unit 122 stores, as candidate elements, candidate patterns (hereinafter referred to as undetermined patterns) for which it was not possible to determine whether or not the feature patterns are feature patterns by the feature extraction unit 114 described later.

  FIG. 3 is a diagram illustrating an example of a data structure of data stored in the candidate storage unit 122. As shown in the figure, the candidate storage unit 122 stores candidate elements that are candidate patterns determined to be undetermined patterns. In the figure, only a candidate element having one item is described, but candidate elements whose number of items is sequentially increased as the process progresses can be stored in the candidate storage unit 122.

  Returning to FIG. 1, the feature storage unit 123 stores a feature pattern extracted by a feature extraction unit 114 described later. FIG. 4 is a diagram illustrating an example of a data structure of data stored in the feature storage unit 123. As illustrated in FIG. 4, the feature storage unit 123 stores data in which extracted feature patterns are associated with frequent classes that represent classes in which the feature patterns frequently occur.

  The input data storage unit 121, the candidate storage unit 122, and the feature storage unit 123 are all commonly used storage media such as an HDD (Hard Disk Drive), an optical disk, a memory card, and a RAM (Random Access Memory). Can be configured.

  Returning to FIG. 1, the feature generation unit 110 extracts a feature pattern from the data stored in the input data storage unit 121 and stores it in the feature storage unit 123. The feature generation unit 110 includes a reception unit 111, a division unit 112, a candidate generation unit 113, and a feature extraction unit 114.

  The accepting unit 111 accepts input data from which a feature pattern is to be extracted. In the present embodiment, an item set to which a class is assigned and stored in the input data storage unit 121 is received as feature pattern extraction target data. The data input method is not limited to this. For example, you may comprise so that the data memorize | stored in the external device (not shown) may be received.

  The dividing unit 112 divides the item set with class read from the input data storage unit 121 by the receiving unit 111 into a subset for each class.

  The candidate generation unit 113 extracts an item from a subset of items for each class, and generates a candidate pattern including the extracted item. In addition, the candidate generation unit 113 acquires a plurality of candidate elements in which some of the items are different from each other from the candidate elements stored in the candidate storage unit 122, and a common item among the plurality of candidate elements, A candidate pattern including items that differ between candidate elements is generated as a new candidate pattern.

  The feature extraction unit 114 calculates, for each class, the appearance frequency of each candidate pattern in the item set associated with the class, and extracts a candidate pattern that satisfies a predetermined condition of the appearance frequency as a feature pattern. . For example, the feature extraction unit 114 can use whether or not it is larger than a predetermined frequency threshold as a predetermined condition. In this case, the feature extraction unit 114 extracts candidate patterns whose appearance frequency in any class is greater than the frequency threshold and whose appearance frequency in other classes is equal to or less than the frequency threshold as a feature pattern. Details of the feature pattern extraction process will be described later.

  The display unit 130 is a display device such as a display device that functions as an output unit that outputs the extracted feature pattern.

  Next, a feature pattern display process performed by the feature pattern extraction apparatus 100 according to the first embodiment configured as described above will be described with reference to FIG. FIG. 5 is a flowchart showing the overall flow of the feature pattern display process in the first embodiment.

  First, the reception unit 111 reads one item set with class from the item set with class stored in the input data storage unit 121 (step S501). Next, the dividing unit 112 divides the class-added item set into subsets for each class by referring to the class of the read class-added item set (step S502).

For example, when the class-attached item sets t _{0 to} t ₄ are input from the input data storage unit 121 as illustrated in FIG. 2, the dividing unit 112 converts these item sets into subsets corresponding to the class “purchase”. assign. On the other hand, when the class-attached item sets t _{5 to} t ₉ are input, the dividing unit 112 assigns these item sets to the subsets corresponding to the class “unpurchased”.

  Next, the reception unit 111 determines whether or not unprocessed data (item set with class) exists in the input data storage unit 121 (step S503). If there is an unprocessed item set with class (step S503: YES), the next item set is read and the process is repeated (step S501).

  When there is no unprocessed item set (step S503: NO), the feature generation unit 110 executes a feature pattern extraction process for finding a feature pattern that characterizes the class-equipped item set from the class-added item set (step S504). .

For example, it is assumed that the input data storage unit 121 stores the class-attached item sets t _{0 to} t ₉ shown in FIG. Also, assume that each item set is read sequentially from the top. At this time, if the item set with classes t _{0 to} t ₈ has been read, the next unprocessed data is read (step S501). In contrast, if after the class with item set t ₉ is loaded, because the raw data does not exist, the characteristic pattern extracting process is executed (step S504).

In the feature pattern extraction process, candidate elements generated in the extraction process are stored in the candidate storage unit 122, while the found feature patterns are stored in the feature storage unit 123. For example, the feature pattern extraction process finds the feature patterns (p _{0 to} p ₁₁ ) shown in FIG. 4 from the class-attached item set as shown in FIG. Details of the feature pattern extraction process will be described later.

  After the feature pattern extraction process, the display unit 130 displays the extracted feature pattern (step S505) and ends the feature pattern display process.

  For example, as shown in FIG. 4, the display unit 130 displays feature patterns that are associated with frequent classes and are represented in a table format. Thus, the user can determine which class the combination pattern of items is classified into.

  For example, a user who is a salesperson in a retail business can recognize a product (item) purchased at the same time and recommend it to a customer by referring to such a feature pattern. Further, by referring to such a feature pattern, the user can arrange, for example, products that are frequently purchased at a closer location. Thus, according to the present embodiment, it is possible to efficiently generate and display information that can be used for user decision support.

  Note that the feature pattern output method is not limited to the method of displaying on the display unit 130. For example, it may be configured to output to a paper medium by a printer or the like.

  Next, details of the feature pattern extraction processing in step S504 will be described with reference to FIGS. 6 and 7 are flowcharts showing the overall flow of the feature pattern extraction process in the first embodiment.

  First, the candidate generation unit 113 extracts classes constituting the subset divided by the division unit 112, and generates a class set including the extracted classes (step S601). For example, a class set including “purchased” and “not purchased” is generated for an item set with classes as shown in FIG.

  Next, the candidate generation unit 113 extracts one unprocessed item as a candidate pattern from the item set constituting the class-added item set read by the reception unit 111 (step S602).

  For example, in the item set with classes as shown in FIG. 2, each item set includes “jacket”, “jeans”, “polo shirt”, “Y shirt”, “jumper”, “slack”, “belt”, and “belt”. It consists of items such as “tie”. For this reason, when any item of the item is unprocessed, the item is acquired as a candidate pattern.

  Next, the feature extraction unit 114 selects one class for which the appearance frequency for each class is not calculated for the candidate pattern extracted in step S602 from the classes included in the class set generated in step S601. (Step S603). For example, “purchased” and “unpurchased” classes are extracted, and for the item “jacket” that is a candidate pattern, if the appearance frequency has not been calculated for any class, that class is acquired. Is done.

  Next, the feature extraction unit 114 calculates the number of item sets including the candidate pattern extracted in step S602 for the item set to which the class that matches the selected class is assigned, and the candidate pattern and the The appearance frequency in the class is set (step S604).

For example, when the item “jacket” is extracted as a candidate pattern and the class “purchase” is selected in the item set with class of FIG. 2, the item set t _{0 to} t ₄ includes “jacket”. The appearance frequency is 5.

In addition, when the item “jacket” is extracted as a candidate pattern and the class “unpurchased” is selected, the item set t ₅ , t ₆ , and t ₉ includes “jacket”, and thus appears. The frequency is 3.

FIG. 8 is a diagram showing an example of the appearance frequency calculated for each candidate pattern and class set by such a procedure. In the figure, the purchase frequency and the non-purchase frequency, which are the appearance frequencies of each class, calculated for each candidate pattern are shown. Note that the determination result represents the determination result of the pattern type determined by the feature extraction unit 114 for each candidate pattern (details will be described later). Also, c _{j, k} in the figure represents the (k + 1) th candidate pattern having j items.

  Next, the candidate generation unit 113 determines whether or not all classes have been processed (step S605). If not all classes have been processed (step S605: NO), the next unprocessed class is acquired from the class set and the process is repeated (step S603).

  If all classes have been processed (step S605: YES), the process proceeds to step S606. For example, regarding the item “jacket” that is a candidate pattern, if the appearance frequency has been calculated for both “purchase” and “not purchased”, the process proceeds to step S606.

  In step S606, the feature extraction unit 114 determines the pattern type of the candidate pattern by referring to the appearance frequency for each class for the item extracted as the candidate pattern (step S606). The pattern type is information indicating whether the candidate pattern is a feature pattern. In the present embodiment, the pattern type includes a feature pattern, an undetermined pattern, and a non-feature pattern. The feature extraction unit 114 determines each candidate pattern as one of these three pattern types.

  For example, if two types of classes are targeted, the feature extraction unit 114 determines candidate patterns that appear frequently in one class and do not appear frequently in the other class as feature patterns. Also, the feature extraction unit 114 determines candidate patterns that appear frequently in both classes as undetermined patterns. Furthermore, the feature extraction unit 114 determines candidate patterns that do not appear frequently in both classes as non-feature patterns. Note that the pattern type determination method is not limited to this.

  The feature extraction unit 114 determines that the appearance frequency is frequent when the appearance frequency is equal to or higher than the frequency threshold. For example, it is assumed that an item set with classes as shown in FIG. 2 is input and 2 is set as the frequency threshold. In this case, since the candidate pattern “jacket” appears frequently in both classes, it is determined as an undetermined pattern. Further, the candidate pattern “belt” does not appear frequently in the class “purchase”, but frequently appears in the class “not purchased”, and thus is determined as a feature pattern.

  Similarly, for each candidate pattern in FIG. 8, “Jeans”, “Polo shirt”, “Y shirt”, “Jumper”, and “Slacks” are undetermined patterns as shown in the determination result column of FIG. And “tie” is determined as the feature pattern.

  Next, the feature extraction unit 114 determines whether or not the determined pattern type is a feature pattern (step S607). When the pattern type is a feature pattern (step S607: YES), the feature extraction unit 114 stores the candidate pattern as a feature pattern in the feature storage unit 123 (step S608).

  If the pattern type is not a feature pattern (step S607: NO), the feature extraction unit 114 further determines whether or not the pattern type is an undetermined pattern (step S609). When the pattern type is an undetermined pattern (step S609: YES), the feature extraction unit 114 stores the candidate pattern as a candidate element in the candidate storage unit 122 (step S610).

  If it is determined that the pattern type is not an undetermined pattern (step S609: NO), and after storing the candidate pattern in step S608 or step S610, the candidate generation unit 113 determines whether all items have been processed. (Step S611).

  If all items have not been processed (step S611: NO), the candidate generation unit 113 acquires the next unprocessed item as a candidate pattern and repeats the process (step S602).

  When all items have been processed (step S611: YES), the candidate generation unit 113 determines whether the candidate length can be extended (step S612). The candidate length refers to the number of items included in the candidate pattern currently being processed. At this time, one item is extracted as a candidate pattern, so the candidate length is 1.

  The candidate generation unit 113 determines whether or not the candidate length can be extended based on whether or not two or more candidate elements are stored in the candidate storage unit 122. When two or more candidate elements are stored, it is determined that the candidate length can be extended (step S612: YES), and the candidate generation unit 113 selects a candidate pattern obtained by extending the candidate length based on the two candidate elements. In order to generate, the following processing is executed (step S613 to step S614). For example, in the example of FIG. 3, since six candidate elements are stored, it is determined that the candidate length can be extended.

  If two or more candidate elements do not exist (step S612: NO), the candidate length cannot be extended, and no more candidate patterns can be generated and feature patterns can be extracted. Therefore, the feature pattern extraction process ends.

  When the candidate length can be extended (step S612: YES), the candidate generation unit 113 matches the current candidate length (hereinafter referred to as candidate length k) among the candidate elements stored in the candidate storage unit 122. A candidate element pair consisting of two candidate elements having a length and matching item subsets other than the last item is extracted (step S613). When the candidate length k is 1, that is, when the candidate element includes only one item, there is no candidate element pair with which the item matches. Therefore, all combinations of two candidate elements are extracted as candidate element pairs.

  However, it is assumed that items included in each candidate element are arranged in an order based on a predetermined criterion. The candidate generation unit 113 includes candidate patterns having a candidate length of k + 1, including k−1 items in common among items included in the extracted candidate element pairs and items different from each other in each candidate element. Generate. Hereinafter, a candidate pattern whose candidate length is k + 1 is referred to as a (k + 1) -th candidate pattern. In the (k + 1) next candidate pattern, it is assumed that the items are arranged in the order based on the above criteria.

  After extracting the candidate element pair (step S613), the candidate generating unit 113 generates a new candidate pattern from the two candidate elements included in the candidate element pair (step S614).

  For example, it is assumed that the current candidate length k is 1, and “jacket” and “jeans” are extracted from the candidate elements stored in the candidate storage unit 122 as candidate element pairs that satisfy the condition. In the following, each item is arranged in the order of “jacket”, “jeans”, “polo shirt”, “Y shirt”, “jumper”, “slacks”, “belt”, and “tie”. Assume that standards are set.

  In this case, the candidate generation unit 113 generates a candidate pattern “(jacket, jeans)” including “jacket” and “jeans”, which are different items between two candidate elements, as a new secondary candidate pattern.

  For example, it is assumed that the current candidate length k is 2, and “(jacket, jeans)” and “(jacket, Y shirt)” are extracted as candidate element pairs that satisfy the condition. At this time, the candidate generation unit 113 can generate a tertiary candidate pattern such as “(jacket, jeans, Y shirt)” from the candidate element pair.

  Further, it is assumed that the current candidate length k is 3, and “(jacket, jeans, Y shirt)” and “(jacket, jeans, jumper)” are extracted as candidate element pairs that satisfy the conditions. At this time, the candidate generation unit 113 can generate a quaternary candidate pattern such as “(jacket, jeans, Y shirt, jumper)” from the candidate element pair.

  Since steps S615 to S622 are the same as steps S603 to S610, detailed description thereof is omitted. That is, from step S603 to step S610, a feature pattern was extracted from a candidate pattern consisting of one item, whereas from step S615 to step S622, a feature pattern was extracted from a candidate pattern whose candidate length was extended to 2 or more. To do.

  For example, in the appearance frequency calculation process in step S616, if the candidate pattern is “(jacket, jeans)” and class “purchase”, the appearance frequency is calculated as 3 (see FIG. 2). In the case of the candidate pattern “(jacket, jeans)” and the class “not purchased”, the appearance frequency is calculated as 2.

9 to 11 are diagrams illustrating an example of the calculation result of the appearance frequency calculated by such a procedure. FIG. 9 shows the appearance frequency in each class for the secondary candidate patterns c _{2,0 to} c _2,14 . FIG. 10 shows the appearance frequency in each class for the tertiary candidate patterns c _{3,0 to} c _3,3 . FIG. 11 shows the appearance frequency in each class for the quaternary candidate pattern c _4,0 .

  Further, for example, in the pattern type determination process in step S619 to step S622, when 2 is set as the frequency threshold, the determination shown in the determination result column of each figure for each candidate pattern shown in FIGS. Results are obtained.

  After the pattern type determination process, the candidate generation unit 113 determines whether all candidate elements have been processed (step S623). If all candidate elements have not been processed (step S623: NO), the candidate generation unit 113 acquires another candidate element pair that satisfies the condition and repeats the process (step S613). When all candidate elements have been processed (step S623: YES), the candidate generation unit 113 determines whether the candidate length can be further extended (step S612).

  That is, the candidate generation unit 113 determines whether or not two or more candidate elements having a candidate length that matches the current candidate length are stored in the candidate storage unit 122. For example, if the current candidate length is 2 and a candidate pattern as shown in FIG. 9 is generated, there are 6 undetermined patterns with a candidate length of 2, so it is determined that the candidate length can be extended. Is done. If the current candidate length is 3 and a candidate pattern as shown in FIG. 10 is generated, it is determined that the candidate length can be extended because there are two undetermined patterns with a candidate length of 3. Is done. On the other hand, if the current candidate length is 4 and a candidate pattern as shown in FIG. 11 is generated, there is only one undetermined pattern with a candidate length of 4, so it is determined that the candidate length cannot be extended. The

  By performing the processing described above, patterns having different trends in each class can be extracted as feature patterns. Since the feature pattern has a different tendency in each class, it is considered that the feature pattern is appropriate as a feature amount for identifying a difference between classes.

  Although the case where there are two types of classes has been described as an example, three or more types of classes can be targeted. In this case, for example, a lower limit number Th1 and an upper limit number Th2 that are threshold values for the number of two classes are set. A characteristic pattern that appears frequently in classes within the number of Th1 or more and Th2 or less, but does not occur frequently in the remaining classes, an undetermined pattern that occurs frequently in classes exceeding the number Th2, but does not occur frequently in the remaining classes, A criterion that determines that a non-feature pattern is frequently used when the number of classes that are smaller than Th1 appears frequently but does not occur frequently in the remaining classes can be used.

  As described above, in the feature pattern extraction apparatus according to the first embodiment, in order to clarify the relationship between the item subset characterizing the item set and the class by inputting a large number of item sets with classes. Feature patterns can be extracted. Thereby, it is possible to efficiently generate a feature pattern that is information that can be used for decision support.

(Second Embodiment)
The classification support apparatus according to the second embodiment is a classification model for classifying an item set into any class based on presence / absence from a feature pattern extracted by the same method as in the first embodiment. Is generated. That is, in the second embodiment, a plurality of item sets collected under different conditions are defined as class-attached item sets to which classes according to each condition are assigned, and the class sets between the class-added item sets are changed. Learn classification models that are considered to be the cause of differences. This classification model makes it possible to support human decision making in the field where the item is handled.

  FIG. 12 is a block diagram illustrating an example of a configuration of the classification support apparatus 200 according to the second embodiment. As illustrated in FIG. 12, the classification support apparatus 200 includes an input data storage unit 121, a candidate storage unit 122, a feature storage unit 123, a feature generation unit 110, a display unit 230, an attribute generation unit 241, and an example. A generation unit 242, a model generation unit 243, and a model storage unit 224 are provided.

  The second embodiment is different from the first embodiment in that the function of the display unit 230 and the addition of an attribute generation unit 241, a case generation unit 242, a model generation unit 243, and a model storage unit 224 are added. . Other configurations and functions are the same as those in FIG. 1 which is a block diagram showing the configuration of the feature pattern extraction apparatus 100 according to the first embodiment.

  The attribute generation unit 241 refers to the item set with class and the extracted feature pattern, and generates an attribute vector that is a vector indicating whether the item set includes a feature pattern. In this attribute vector, the feature pattern corresponds to an attribute, and information indicating whether or not the feature pattern is included (for example, 1 (included), 0 (not included)) corresponds to the attribute value.

  The case generation unit 242 generates a set of cases (case set) that is information in which the attribute vector generated by the attribute generation unit 241 is associated with the class assigned to the item set corresponding to the attribute vector.

  The model generation unit 243 generates a classification model from the case set generated by the case generation unit 242. Specifically, the model generation unit 243 regards the generated case set as a set of learning cases, and applies a recursive learning method to the case set to identify a classification model that identifies a class by attribute (feature pattern). learn.

  For example, the model generation unit 243 learns a tree structure classification model from a set of learning cases, ID3 (“Induction of Decision Trees”, JR Quinlan, Machine Learning, vol. 1, no. 1, pp. 81-106 ( 1986)) can be used to generate a classification model from a set of cases. The applicable inductive learning method is not limited to ID3, and other inductive learning methods such as SVM (Support Vector Machine) and a neural network may be applied.

  The model storage unit 224 stores the classification model generated by the model generation unit 243. The display unit 230 is different from the display unit 130 of the first embodiment in that the generated classification model is displayed.

  Next, a classification support process performed by the classification support apparatus 200 according to the second embodiment configured as described above will be described with reference to FIG. The classification support process is a process that enables a user to assist in classifying an item set into a class by generating a classification model from the extracted feature patterns and displaying the generated classification model. FIG. 13 is a flowchart illustrating an overall flow of the classification support processing in the second embodiment.

  Steps S1201 to S1204 are the same as steps S501 to S504 in the feature pattern extraction apparatus 100 according to the first embodiment, and thus the description thereof is omitted.

  After extracting the feature pattern by the same procedure as in the first embodiment, the accepting unit 111 rereads one item set with class from the item set with class stored in the input data storage unit 121. (Step S1205).

  Next, the attribute generation unit 241 determines whether the item set includes a feature pattern by referring to the read item set with class and the feature pattern stored in the feature storage unit 123. Then, an attribute vector expressing whether or not a feature pattern is included is generated (step S1206).

For example, it is assumed that t ₀ is read from the class-equipped item set as shown in FIG. 2 and the feature pattern shown in FIG. 4 is extracted. At this time, the attribute generation unit 241 determines that the item set constituting t ₀ includes the feature patterns p ₂ and p ₄ . “Jacket” and “Polo shirt” which are items constituting p ₂ are part of the item set constituting t ₀ , and “Jeans” and “Polo shirt” which are items constituting p ₄ are t ₀ . This is because it is a part of the item set to be configured.

On the other hand, with respect to other characteristic pattern of FIG. 4, among the items that make up each feature pattern, at least one is not included in the item set constituting the t _0. Therefore, attribute generation unit 241 determines that the item set forming a t ₀ does not include the feature pattern. For _example, the determination in the case of _{p 10,} an item composing the _{p 10} "jumpers" are not the items that make up the _{t 0,} attribute generation unit 241, and _{t 0} does not include a feature pattern _{p 10} To do.

Then, for example, the attribute generation unit 241 generates an attribute vector expressing 1 when the feature pattern is included and 0 when the feature pattern is not included. FIG. 14 is a diagram illustrating an example of the generated attribute vector. FIG. 14 shows an example of the attribute vector generated when the class-equipped item set as shown in FIG. 2 is input and the feature pattern shown in FIG. 4 is extracted. For example, the vector (0, ₀ , 1, ₀ , 1, ₀ , ₀ , ₀ , ₀ , ₀ , ₀ , 0) shown in the attribute part of t ₀ in FIG. 14 represents the attribute vector for t ₀ .

  Returning to FIG. 13, the case generation unit 242 generates a case by combining the generated attribute vector and the class assigned to the item set that generated the attribute vector (step S1207).

For example, when t ₀ is a processing target as an item set with class, the case generation unit 242 associates the attribute vector of t ₀ in FIG. 14 with the class “purchase” described in the class column. Is generated.

  Next, the reception unit 111 determines whether or not unprocessed data exists (step S1208). If there is (step S1208: YES), the next unprocessed item set is input to perform processing. Repeat (step S1205). For example, the case set shown in FIG. 14 is finally generated by repeatedly performing the process on the item set with class shown in FIG. 2 and the feature pattern shown in FIG.

  When there is no unprocessed data (step S1208: NO), the model generation unit 243 regards the generated case set as a set of learning cases and adapts it to the inductive learning method, thereby changing the attribute (feature pattern). A classification model for identifying a class is learned (step S1209). The model generation unit 243 stores the learned classification model in the model storage unit 224.

  FIG. 15 is a diagram illustrating an example of the generated classification model. FIG. 15 shows an example of a classification model generated from the case set of FIG. In the figure, one of the attributes (feature patterns) is assigned to the branch node represented by the white ellipse, and one of the classes is assigned to the end node represented by the gray ellipse. Assigned. In addition, a line connecting the nodes represents a branch, and one of attribute values of attributes positioned at the upper level is assigned to the branch.

The figure, if it classes not purchased includes a feature pattern p _1, if including feature pattern p ₄ does not contain the characteristic pattern p ₁ class purchased, does not contain the characteristic pattern p ₁ and p _4, characteristic patterns p ₃ shows an example of a classification model that means that if ₃ is included, the class is purchased, and if none of the feature patterns p ₁ , p ₄ , and p ₃ is included, the class is not purchased.

  Returning to FIG. 13, the display unit 230 displays the generated classification model (step S1210), and ends the classification support process.

  For example, by displaying the classification model as shown in FIG. 15, the user can determine which class the combination pattern of items is classified into. For example, a user who is a salesperson in a retail business can recognize a product (item) purchased at the same time and recommend it to a customer by referring to such a classification model.

  In addition, for example, a customer inputs a product to be purchased in real time and refers to a classification model for other products that are likely to be purchased at the same time as the input product. You may comprise so that it may show. Thereby, the user can grasp | ascertain the goods which should be recommended to a customer according to a customer's action in real time.

  As described above, the classification support apparatus according to the second embodiment inputs a large number of item sets with classes, and learns a classification model that clarifies the relationship between the item subsets that characterize the item sets and the classes. be able to. For this reason, it is possible to perform an analysis in consideration of the class of the item set, which cannot be considered in the conventional association rule finding method.

  Next, the hardware configuration of each device (feature pattern extraction device, classification support device) according to the first or second embodiment will be described with reference to FIG. FIG. 16 is an explanatory diagram illustrating a hardware configuration of the device according to the first or second embodiment.

  The apparatus according to the first or second embodiment communicates with a control device such as a CPU (Central Processing Unit) 51 and a storage device such as a ROM (Read Only Memory) 52 and a RAM 53 by connecting to a network. A bus 61 that connects the communication I / F 54, an external storage device such as an HDD (Hard Disk Drive) and a CD (Compact Disc) drive device, a display device such as a display device, an input device such as a keyboard and a mouse, and the like. And has a hardware configuration using a normal computer.

  A program executed by the apparatus according to the first or second embodiment is an installable or executable file, which is a CD-ROM (Compact Disk Read Only Memory) or FD (Floppy (registered trademark) Disk). ), A CD-R (Compact Disk Recordable), a DVD (Digital Versatile Disk), and the like, recorded on a computer-readable recording medium and provided as a computer program product.

  Further, the program executed by the apparatus according to the first or second embodiment may be stored on a computer connected to a network such as the Internet and provided by being downloaded via the network. Good. The program executed by the device according to the first or second embodiment may be provided or distributed via a network such as the Internet.

  The program executed by the apparatus according to the first or second embodiment may be configured to be provided by being incorporated in advance in a ROM or the like.

  The program executed by the apparatus according to the first or second embodiment has a module configuration including the above-described units (accepting unit, dividing unit, candidate generating unit, feature extracting unit), and actual hardware. As described above, the CPU 51 (processor) reads the program from the storage medium and executes the program, so that the above-described units are loaded onto the main storage device, and the above-described units are generated on the main storage device.

  It should be noted that the present invention is not limited to the above-described embodiment as it is, and can be embodied by modifying the constituent elements without departing from the scope of the invention in the implementation stage. In addition, various inventions can be formed by appropriately combining a plurality of constituent elements disclosed in the above embodiments. For example, some components may be deleted from all the components shown in the embodiment. Furthermore, constituent elements over different embodiments may be appropriately combined.

51 CPU
52 ROM
53 RAM
54 Communication I / F
61 Bus 100 Feature Pattern Extraction Device 110 Feature Generation Unit 111 Reception Unit 112 Division Unit 113 Candidate Generation Unit 114 Feature Extraction Unit 121 Input Data Storage Unit 122 Candidate Storage Unit 123 Feature Storage Units 130 and 230 Display Unit 200 Classification Support Device 224 Model Storage Unit 241 attribute generation unit 242 case generation unit 243 model generation unit

Claims (10)

A reception unit that receives an input of an item set that includes at least one item that represents information to be analyzed and is associated with a class into which the set is classified;
A candidate generation unit that generates a candidate pattern that includes at least one item that is a candidate for a feature pattern that represents a characteristic pattern among the patterns of items that are included in the item set;
For each class, the appearance frequency of the candidate pattern in the item set associated with the class is calculated, and the feature pattern that is the candidate pattern that satisfies the predetermined condition is calculated. A feature extraction unit,
An output unit for outputting the extracted feature pattern;
A feature pattern extraction apparatus comprising: In the feature extraction unit, the appearance frequency in a first class that is one of the classes satisfies the condition, and the appearance frequency in a class other than the first class included in the class is the condition. Extracting the candidate pattern not satisfying as the feature pattern;
The feature pattern extraction apparatus according to claim 1. The first class is any one of the classes, and is a class having a number equal to or more than a predetermined lower limit number and equal to or less than a predetermined upper limit number;
The feature pattern extraction apparatus according to claim 2. The feature extraction unit is not determined whether the candidate pattern satisfies the condition in which the appearance frequency in a number of classes greater than a predetermined upper limit number among the classes is the feature pattern. Extracted as a pattern,
The candidate generation unit further generates a new candidate pattern including items extracted from the plurality of undetermined patterns;
The feature pattern extraction apparatus according to claim 1. The candidate generation unit extracts a common item and a different item from the plurality of undetermined patterns in which only some of the items are different from each other, and includes a new candidate pattern including a common item and a different item Generating,
The feature pattern extraction apparatus according to claim 4. The candidate generation unit extracts a different item from each of the plurality of undetermined patterns including one different item, and generates a new candidate pattern including the two extracted items;
The feature pattern extraction apparatus according to claim 4. The feature extraction unit satisfies any one of the classes, and the appearance frequency in the first class, which is a number of classes smaller than a predetermined lower limit number, satisfies the condition and is included in the class Not extracting the candidate pattern whose appearance frequency in a class other than the first class does not satisfy the condition as the feature pattern;
The feature pattern extraction apparatus according to claim 1. A reception unit that receives an input of an item set that includes at least one item that represents information to be analyzed and is associated with a class into which the set is classified;
A candidate generation unit that generates a candidate pattern that includes at least one item that is a candidate for a feature pattern that represents a characteristic pattern among the patterns of items that are included in the item set;
For each class, the appearance frequency of the candidate pattern in the item set associated with the class is calculated, and the feature pattern that is the candidate pattern that satisfies the predetermined condition is calculated. A feature extraction unit,
An attribute generation unit that generates an attribute vector indicating whether or not the extracted feature pattern is included in the item set for each of the item sets;
A model generation unit that generates a classification model for classifying a set including the items into one of the classes based on the generated attribute vector and the class associated with the item set;
An output unit for outputting the generated classification model;
A classification support apparatus comprising: A reception step for receiving an input of an item set that is a set including at least one item representing information to be analyzed, and that associates a class into which the set is classified;
A candidate generation step in which the candidate generation unit generates a candidate pattern including at least one item included in the item set, which is a feature pattern candidate representing a characteristic pattern among the item patterns included in the item set. When,
The feature extraction unit calculates the appearance frequency of the candidate pattern in the item set associated with the class for each class, and the calculated appearance frequency is the candidate pattern that satisfies a predetermined condition. A feature extraction step of extracting the feature pattern;
An output unit that outputs the extracted feature pattern; and
A feature pattern extraction method comprising: A reception step for receiving an input of an item set that is a set including at least one item representing information to be analyzed, and that associates a class into which the set is classified;
A candidate generation step in which the candidate generation unit generates a candidate pattern including at least one item included in the item set, which is a feature pattern candidate representing a characteristic pattern among the item patterns included in the item set. When,
The feature extraction unit calculates the appearance frequency of the candidate pattern in the item set associated with the class for each class, and the calculated appearance frequency is the candidate pattern that satisfies a predetermined condition. A feature extraction step of extracting the feature pattern;
An attribute generating step for generating an attribute vector indicating whether or not the extracted feature pattern is included in the item set for each of the item sets;
A model generation unit generates a classification model for classifying a set including the items into one of the classes based on the generated attribute vector and the class associated with the item set. A model generation step;
An output unit that outputs the generated classification model; and
A classification support method comprising:

Images