Pattern mining based on occupancy

Patent metadata

Field	Value
Publication number	US-9679036-B2
Application number	US-201214398213-A
Country	US
Kind code	B2
Filing date	May 15, 2012
Priority date	May 15, 2012
Publication date	Jun 13, 2017
Grant date	Jun 13, 2017

Abstract

An example method of pattern mining includes identifying, via a logic circuit, a plurality of patterns present in a plurality of transactions, the transactions including sets of items, and selecting, via the logic circuit, one of the identified patterns based on an occupancy of the identified pattern in the transactions.

First claim

What is claimed is:

1. A method of pattern mining, comprising:
identifying, via a logic circuit, a plurality of patterns present in a plurality of transactions, each transaction of the plurality of transactions including a respective set of items, each pattern of the plurality of patterns including at least one item;
determining, via the logic circuit, an occupancy of each pattern of the plurality of patterns by:
identifying supporting transactions associated with the each pattern among the plurality of transactions, wherein each of the supporting transactions comprises all items that are present in the each pattern,
determining a ratio of a first count of items in the each pattern to a second count of items in the identified supporting transactions associated with the each pattern, and
determining the occupancy of the each pattern based on the ratio; and

selecting, via the logic circuit, a particular pattern for a computer system to recommend from the identified plurality of patterns based on the occupancy of the particular pattern.

2. The method as defined in claim 1 , wherein the occupancy of the identified pattern comprises an aggregation of the ratio for the identified supporting transactions.

3. The method as defined in claim 1 , further comprising determining a quality of the each pattern based on the occupancy of the each pattern.

4. The method as defined in claim 3 , wherein determining the quality of the each pattern is further based on support of the each pattern.

5. The method defined in claim 4 , wherein selecting the particular pattern for the computer system to recommend from the identified plurality of patterns based on the occupancy of the particular pattern further comprises:
selecting the particular pattern for the computer system to recommend from the identified plurality of patterns based on the quality of the particular pattern.

6. The method as defined in claim 1 , further comprising generating a subset tree for the plurality of transactions.

7. The method as defined in claim 6 , further comprising pruning the subset tree based on at least one of a comparison of respective occupancies or a comparison of respective qualities of the plurality of transactions to a threshold.

8. The method as defined in claim 6 , further comprising pruning a first subtree of the subset tree based on a comparison of an upper occupancy bound of a first branch to an upper occupancy bound of a second branch of the subset tree, the second branch being independent of the first branch.

9. The method as defined in claim 1 , further comprising:
determining a quality metric of the each pattern based on a calculated support of the each pattern and a calculated occupancy of the each pattern; and
recommending the particular pattern in response to determining that the quality metric of the particular pattern is greater than respective quality metrics of other ones of the plurality of patterns.

10. The method defined in claim 1 , wherein the occupancy is a harmonic or arithmetic occupancy.

11. An apparatus to pattern mine, comprising:
a transaction database to store a plurality of transactions, each transaction of the plurality of transactions including a respective set of items; and
a data miner comprising a hardware processor to:
identify a pattern present in the plurality of transactions, the identified pattern including at least one item;
determine an occupancy of the identified pattern by:
identifying supporting transactions associated with the identified pattern among the plurality of transactions, wherein each of the supporting transactions comprises all items that are present in the identified pattern,
determining a ratio of a first count of items in the identified pattern to a second count of items in the identified supporting transactions associated with the identified pattern, and
determining the occupancy of the identified pattern based on the ratio; and

select the identified pattern for a computer system to recommend based on the occupancy of the identified pattern.

12. The apparatus as defined in claim 11 , wherein the data miner comprises an occupancy calculator to calculate the occupancy of the identified pattern.

13. The apparatus as defined in claim 11 , wherein the data miner comprises a quality calculator to calculate a quality of the identified pattern based on the occupancy and a support for the identified pattern.

14. The apparatus as defined in claim 13 , wherein the support of the identified pattern indicates a frequency of the identified pattern in the plurality of transactions.

15. A computer readable storage medium comprising machine readable instructions which, when executed, cause a machine to at least:
identify a pattern present in a plurality of transactions, each transaction of the plurality of transactions including a respective set of items, the identified pattern including at least one item;
determine an occupancy of the identified pattern by:
identifying supporting transactions associated with the identified pattern among the plurality of transactions, wherein each of the supporting transactions comprises all items that are present in the identified pattern,
determining a ratio of a first count of items in the identified pattern to a second count of items in the identified supporting transactions associated with the identified pattern, and
determining the occupancy of the identified pattern based on the ratio; and

select the identified pattern for a computer system to recommend based on the occupancy of the identified pattern.

16. The computer readable storage medium as defined in claim 15 , wherein the instructions further cause the machine to output the identified pattern having a highest quality among a plurality of patterns.

17. The computer readable storage medium as defined in claim 16 , wherein the quality of the identified pattern is based on the occupancy of the identified pattern, support of the identified pattern, and a weighting factor.

18. The computer readable storage medium as defined in claim 17 , wherein the weighting factor indicates a relative importance of the support and the occupancy to a particular user application.

Assignees

• Luo Ping
• Wang Min
• Tang Linpeng
• Zhang Lei
• Hewlett Packard Entpr Dev Lp

Inventors

• Luo Ping
• Wang Min
• Tang Linpeng
• Zhang Lei

Classifications

• G06F18/21

  Design or setup of recognition systems or techniques; Extraction of features in feature space; Blind source separation · CPC title

• G06N5/025 Primary

  Extracting rules from data · CPC title

• G06F2216/03

  Data mining · CPC title

• G06F16/283

  Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP · CPC title

• G06F16/26 Primary

  Visual data mining; Browsing structured data · CPC title