CN110399406B - Method, device and computer storage medium for mining global high utility sequence pattern - Google Patents

Abstract

The present disclosure provides a method, apparatus, and computer-readable storage medium for mining global high utility sequence patterns. The method comprises the following steps: determining a first type of item in the sequence database, wherein the first type of item is an item with a global sequence weight utility value higher than a first threshold value; determining utility value linked lists of all sequences in a sequence database; mining at least one candidate global high utility sequence pattern from a sequence database and determining a first set according to the determined first class item, wherein the first set comprises the at least one candidate global high utility sequence pattern, the identification of sequences comprising the respective candidate global high utility sequence patterns, and utility values of the respective candidate global high utility sequence patterns in the respective sequences; and mining a global high utility sequence pattern from the at least one candidate global high utility sequence pattern according to the utility value linked list and the first set of each sequence.

Description

Method, device and computer storage medium for mining global high-utility sequence patterns

Technical Field

The present disclosure relates to the field of data processing, and in particular, to a method, device and computer-readable storage medium for mining global high-utility sequence patterns.

Background technique

Sequential pattern mining is an important technology in the field of data mining. Sequential pattern mining is aimed at sequence databases. Sequential databases can include multiple sequences (also called transactions), where each sequence can include at least one itemset, each itemset includes at least one item, and there is a sorting order between item sets. Taking the shopping data of a supermarket as an example, a user bought goods a and goods b on the first day, goods a and goods c on the second day, and goods b on the third day. The user's shopping data during this period can be abstracted as a sequence: <[a b], [a c], [b]>, where a, b and c are items, the items in [] constitute an itemset, and multiple item sets are arranged in order to form a sequence. The high-utility sequential pattern mining algorithm mines commodity combinations with utility values higher than the preset threshold, that is, sequential patterns. Sequential patterns are ordered arrangements of different item sets.

In the process of mining high-utility patterns, the process of finding high-utility patterns by calculating the total utility value of the entire database requires more calculations, especially the mining of high-utility sequence patterns. Therefore, high-utility sequence pattern mining is more complicated than traditional high-utility pattern mining and frequent sequence pattern mining. Current distributed and parallel pattern mining focuses on high-utility pattern mining and frequent sequence pattern mining. For example, high-utility pattern mining and frequent sequence pattern mining can be performed on the Hadoop platform. Therefore, there is no distributed and parallel high-utility sequence pattern mining method.

Summary of the invention

To this end, the present disclosure provides a method, an apparatus, and a computer-readable storage medium for mining global high-utility sequence patterns.

According to one aspect of the present disclosure, a method for mining global high-utility sequence patterns is provided, comprising: determining a first category of items in a sequence database, wherein the first category of items are items whose global sequence weighted utility values are higher than a first threshold; determining a utility value chain list of each sequence in the sequence database; mining at least one candidate global high-utility sequence pattern from the sequence database and determining a first set based on the determined first category of items, wherein the first set includes the at least one candidate global high-utility sequence pattern, an identifier of a sequence including each candidate global high-utility sequence pattern, and a utility value of each candidate global high-utility sequence pattern in the corresponding sequence; and mining a global high-utility sequence pattern from the at least one candidate global high-utility sequence pattern based on the utility value chain list of each sequence and the first set.

According to an example of the present disclosure, determining the first category of items in the sequence database includes: determining the global sequence weight utility value of each item in the sequence database; and determining the items whose global sequence weight utility value is higher than a first threshold as the first category of items.

According to an example of the present disclosure, determining the global sequence weight utility value of each item in a sequence database includes: determining the local sequence weight utility values of the item in each partition of the sequence database; and determining the global sequence weight utility value of the item based on the determined local sequence weight utility values.

According to an example of the present disclosure, the local sequence weight utility value of the item in each partition of the sequence database is determined according to the utility values of the sequences including the item in the partition.

According to an example of the present disclosure, determining the utility value linked list of each sequence in the sequence database includes: determining the utility value linked list of the sequence according to the utility value of each item in the sequence and the position of each item in the sequence.

According to an example of the present disclosure, mining at least one candidate global high-utility sequence pattern from the sequence database based on the determined first category items includes: mining local high-utility sequence patterns from each partition of the sequence database based on the determined first category items; and determining at least one candidate global high-utility sequence pattern based on the mined local high-utility sequence patterns.

According to an example of the present disclosure, based on the determined first category items, mining local high utility sequence patterns from each partition of the sequence database includes: for an item belonging to the first category in each sequence included in the partition, calculating the utility value and residual utility value of the item in each sequence, wherein the residual utility value of the item in a sequence is the sum of the utility values of all items after the item in the sequence; constructing a utility list of the item in each sequence; determining the utility value chain of the item based on the utility list of the item in each sequence; and mining local high utility sequence patterns from the partition based on the utility value chain of each item in the partition.

According to an example of the present disclosure, mining a global high utility sequence pattern from the at least one candidate global high utility sequence pattern according to the utility value chain list of each sequence and the first set includes: determining the local utility value of each candidate global high utility sequence pattern according to the utility value chain list of each sequence and the first set; determining the global utility value of each candidate global high utility sequence pattern according to the local utility value of each candidate global high utility sequence pattern; and determining a sequence pattern whose global utility value is greater than a first threshold as a global high utility sequence pattern.

According to an example of the present disclosure, the above method further includes: dividing the sequences in the sequence database into multiple partitions according to a load balancing algorithm.

According to another aspect of the present disclosure, there is provided an apparatus for mining global high-utility sequence patterns, comprising: a first determination unit, configured to determine a first category of items in a sequence database, wherein the first category of items are items whose global sequence weight utility values are higher than a first threshold; a second determination unit, configured to determine a utility value chain list of each sequence in the sequence database; a first mining unit, configured to mine at least one candidate global high-utility sequence pattern from the sequence database and determine a first set based on the determined first category of items, wherein the first set includes the at least one candidate global high-utility sequence pattern, an identifier of a sequence including each candidate global high-utility sequence pattern, and a utility value of each candidate global high-utility sequence pattern in the corresponding sequence; and a second mining unit, configured to mine a global high-utility sequence pattern from the at least one candidate global high-utility sequence pattern based on the utility value chain list of each sequence and the first set.

According to an example of the present disclosure, the first determination unit is configured to determine the global sequence weighted utility value of each item in the sequence database; and determine the items whose global sequence weighted utility value is higher than a first threshold as first category items.

According to an example of the present disclosure, the second determination unit is configured to determine the local sequence weighted utility value of each item in each partition of the sequence database; and determine the global sequence weighted utility value of the item according to the determined local sequence weighted utility value.

According to an example of the present disclosure, the local sequence weight utility value of the item in each partition of the sequence database is determined according to the utility values of the sequences including the item in the partition.

According to an example of the present disclosure, the second determining unit is configured to determine a utility value linked list of the sequence according to the utility value of each item in each sequence and the position of each item in the sequence.

According to an example of the present disclosure, the first mining unit is configured to mine local high-utility sequence patterns from various partitions of the sequence database based on the determined first category items; and determine at least one candidate global high-utility sequence pattern based on the mined local high-utility sequence patterns.

According to an example of the present disclosure, the first mining unit is configured to calculate the utility value and residual utility value of an item belonging to the first category in each sequence included in each partition of the sequence database, wherein the residual utility value of the item in a sequence is the sum of the utility values of all items after the item in the sequence; construct a utility list of the item in each sequence; determine the utility value chain of the item based on the utility list of the item in each sequence; and mine a local high-utility sequence pattern from the partition based on the utility value chain of each item in the partition.

According to an example of the present disclosure, the second mining unit is configured to determine the local utility value of each candidate global high-utility sequence pattern based on the utility value chain list of each sequence and the first set; determine the global utility value of each candidate global high-utility sequence pattern based on the local utility value of each candidate global high-utility sequence pattern; and determine the sequence pattern whose global utility value is greater than the first threshold as the global high-utility sequence pattern.

According to an example of the present disclosure, the above-mentioned device also includes a load distribution unit, which is configured to divide the sequences in the sequence database into multiple partitions according to a load balancing algorithm.

According to another aspect of the present disclosure, there is provided an apparatus for mining global high-utility sequence patterns, comprising: a processor; and a memory, wherein a computer executable program is stored in the memory, and when the computer executable program is executed by the processor, the above method is performed.

According to another aspect of the present disclosure, a computer-readable storage medium is provided, on which instructions are stored. When the instructions are executed by a processor, the processor executes the above method.

Through the method, device and computer-readable storage medium for mining global high-utility sequence patterns provided by the present invention, the utility value linked list and the first set of each sequence in the sequence database are determined, and the global high-utility sequence pattern is mined based on these two data structures, which saves a lot of time, speeds up the calculation process of calculating the global utility value in the sequence database, speeds up the mining speed, and reduces the time complexity.

BRIEF DESCRIPTION OF THE DRAWINGS

The above and other purposes, features and advantages of the present disclosure will become more apparent by describing the embodiments of the present disclosure in more detail in conjunction with the accompanying drawings. The accompanying drawings are used to provide a further understanding of the embodiments of the present disclosure and constitute a part of the specification. Together with the embodiments of the present disclosure, they are used to explain the present disclosure and do not constitute a limitation of the present disclosure. In the accompanying drawings, the same reference numerals generally represent the same components or steps.

FIG1 is a schematic diagram of a system architecture for mining global high-utility sequence patterns from a sequence database according to an embodiment of the present disclosure.

FIG. 2 is a flowchart of a method for mining global high-utility sequence patterns according to an embodiment of the present disclosure.

FIG. 3 shows a schematic diagram of the utility list of item a in sequence s1.

FIG. 4 shows a schematic diagram of the utility value chain of item a.

FIG. 5 is a flowchart of a method for mining a global high-utility sequence pattern from at least one candidate global high-utility sequence pattern according to an embodiment of the present disclosure.

FIG6 is a schematic diagram of the structure of an apparatus for mining global high-utility sequence patterns according to an embodiment of the present disclosure.

FIG. 7 shows the architecture of a computer device according to an embodiment of the present disclosure.

Detailed ways

In order to make the purpose, technical solutions and advantages of the present disclosure more obvious, the exemplary embodiments according to the present disclosure will be described in detail with reference to the accompanying drawings. In the accompanying drawings, the same reference numerals represent the same elements from beginning to end. It should be understood that the embodiments described here are merely illustrative and should not be interpreted as limiting the scope of the present disclosure.

In the present disclosure, when the utility value of a sequence pattern is high, for example, when the utility value of a sequence pattern is higher than a preset threshold, the sequence pattern may be referred to as a "high-utility sequence pattern". That is, a "high-utility sequence pattern" may be a sequence pattern whose utility value is higher than a preset threshold. The "preset threshold" here may be fixed or may change as the application scenario of the mining algorithm changes.

The present disclosure proposes a technical solution for distributed and parallel high-utility sequence pattern mining. In the present disclosure, distributed and parallel high-utility sequence pattern mining is achieved through a distributed computing framework based on the Hadoop platform. In the mining process, the utility value linked list and the first set of each sequence in the sequence database are used to save the necessary information in the mining process, thereby speeding up the mining speed and reducing the time complexity. The "distributed computing framework" mentioned here can be a mapping and induction (MapReduce) framework, in which Map is to map a key-value pair into a new key-value pair, and Reduce is to integrate the values with the same key in the key-value pair and map them into new key-value pairs at the same time. In addition, the module that performs the Map operation can be called Mapper, and the module that performs the Reduce operation can be called Reducer.

First, the system architecture of mining a global high-utility sequence pattern (Global-High Utility Sequence Pattern, G-HUSP) from a sequence database according to an embodiment of the present disclosure is described with reference to FIG. 1. FIG. 1 is a schematic diagram of a system architecture of mining a global high-utility sequence pattern from a sequence database according to an embodiment of the present disclosure. As shown in FIG. 1, the system architecture 100 may include three parts, namely, an identification part 110, a local mining part 120, and an integration part 130. The identification part 110 may include a plurality of mappers and a plurality of reducers, for example, n mappers and n reducers, where n is a positive integer. The identification part 110 may be used to determine the first category of items in the sequence database, which are items whose global sequence weight utility values are higher than a first threshold. The first category of items are items that may constitute a high-utility sequence pattern, and therefore may also be referred to as promising items. The local mining part 120 may include a plurality of mappers and a plurality of reducers, for example, n mappers and n reducers, where n is a positive integer. The local mining part 120 can be used to mine a local high-utility sequence pattern (Local-High Utility Sequence Pattern, L-HUSP) from a sequence database according to the first category item. A part of the sequence pattern in the local high-utility sequence pattern may be a global high-utility sequence pattern, and another part of the sequence pattern may not be a global high-utility sequence pattern, then the other part of the sequence module can be used as a candidate global high-utility sequence pattern. In addition, the local mining part 120 can also be used to determine a first set (which can be expressed as a sidset), which can include at least one candidate global high-utility sequence pattern, an identifier of a sequence including each candidate global high-utility sequence pattern, and the utility value of each candidate global high-utility sequence pattern in the corresponding sequence. In addition, the utility value chain list of each sequence in the sequence database can also be determined. The integration part 130 can include multiple Mappers and multiple Reducers, such as n Mappers and n Reducers, where n is a positive integer. The integration part 130 can be used to mine a global high-utility sequence pattern from the at least one candidate global high-utility sequence pattern according to the utility value chain list of each sequence and the first set. Through the system architecture shown in Figure 1, the utility value linked list and the first set of each sequence in the sequence database can be used to save the necessary information in the mining process, thereby speeding up the mining of high-utility sequence patterns and reducing time complexity.

It should be noted that although three stages of MapReduce are shown in FIG1 , this is only for illustration. According to the embodiments of the present disclosure, there may be fewer or more stages of MapReduce. In addition, the number of Mappers and Reducers included in each stage of MapReduce may be the same or different. In addition, the number of Mappers and/or Reducers included in different stages of MapReduce may be the same or different.

In addition, it should be understood that in the present disclosure, "local" refers to a partition of a database, while "global" refers to the database as a whole. For example, the "local high-utility sequence pattern" in the present disclosure may be a high-utility sequence pattern mined from a partition of a database, that is, a sequence pattern that is highly useful for the partition; and the "global high-utility sequence pattern" in the present disclosure may be a high-utility sequence pattern mined from multiple local high-utility sequence patterns, that is, a sequence pattern that is highly useful for the database as a whole. For another example, the "local sequence weight utility value" in the present disclosure may be a utility value determined based on the data in a partition of a database; and the "global high-utility sequence pattern" in the present disclosure may be a utility value determined based on all the data in the database.

The following will specifically describe a flow chart of a method for mining global high-utility sequence patterns according to the system framework shown in FIG1 in conjunction with FIG2. FIG2 is a flow chart of a method 200 for mining global high-utility sequence patterns according to an embodiment of the present disclosure. As shown in FIG2, in step S201, a first category of items in a sequence database is determined, wherein the first category of items is an item whose global sequence weight utility value (Global Sequence Weight Utility, GSWU) is higher than a first threshold.

In the present disclosure, a sequence database may include multiple sequences and identification information corresponding to each sequence. In the present disclosure, a sequence may be a quantitative sequence. The identification information corresponding to each sequence may be referred to as a sequence identifier (sequence id, sid). The sequence identifier of the lth sequence may be represented by s _l , where l is a positive integer. Each sequence may include one or more item sets, and each item set may include one or more items. Each item has an internal utility value and an external utility value. In a transaction-type database, the internal utility value may be the number of transactions of the item. In databases of other scenarios, the form of the internal utility value may be adjusted accordingly. A table recording the external utility values of each item in the database may be referred to as an external utility value table. In a transaction-type database, the external utility value table may be a profit table, that is, the external utility value table may record the unit profit value of each item in the database. In databases of other scenarios, the form of the external utility value table may be adjusted accordingly.

Table 1 below shows an example of a sequence database. As shown in Table 1, the sequence database is a transaction type database, which includes 5 sequences, namely s ₁ to s ₅ . Each sequence consists of the purchase list of the same customer at different times. Each purchase list is an item set, and the purchased goods are items. For example, sequence s1 means that the customer first purchases 2 goods a and 3 goods c, then purchases 3 goods a, 1 goods b and 2 goods c, then purchases 4 goods a, 5 goods b and 4 goods d, and finally purchases 3 goods e.

sid sequence s ₁ <[(a∶2)(c∶3)]，[(a∶3)(b∶1)(c∶2)]，[(a∶4)(b∶5)(d∶4)]，[(e∶3)]> s ₂ <[(a∶1)(e∶3)], [(a∶5)(b∶3)(d∶2)], [(b∶2)(c∶1)(d∶4)(e∶3)]> s ₃ <[(e∶2)]，[(c∶2)(d∶3)]，[(a∶3)(e∶3)]，[(b∶4)(d∶5)]> s ₄ <[(b:2)(c:3)],[(a:5)(e:1)],[(b:4)(d:3)(e:5)]> s ₅ <[(a∶4)(c∶3)], [(a∶2)(b∶5)(c∶2)(d∶4)(e∶3)]>

Table 1 Examples of sequence databases

An example of an external utility value table is shown in Table 2 below. As shown in Table 2, the profit of commodity a is 5, the profit of commodity b is 3, the profit of commodity c is 4, the profit of commodity d is 2, the profit of commodity e is 1, and the profit of commodity f is 6.

item a b c d e f profit 5 3 4 2 1 6

Table 2 Example of external utility value table

In step S201, the global sequence weighted utility value of each item in the sequence database can be determined, and items with global sequence weighted utility values higher than a first threshold are determined as first-category items. Step S201 can be performed by the identification part 110 (ie, the first-stage MapReduce) described above.

The process of determining the global sequence weight utility value of each item in the sequence database will be described below. According to an example of the present disclosure, for each item in the sequence database, the local sequence weight utility value (LSWU) of the item in each partition of the sequence database can be first determined, and then the global sequence weight utility value of the item is determined based on the determined local sequence weight utility value.

For example, the sequence database may be first divided into a plurality of partitions, and the plurality of partitions may be assigned to a plurality of mappers in the first stage MapReduce. For example, the sequence database may be divided into n partitions, and the 1st partition may be assigned to Mapper 1 in the first stage MapReduce, ..., the kth partition may be assigned to Mapper k in the first stage MapReduce, ..., the nth partition may be assigned to Mapper n in the first stage MapReduce, where 1≤k≤n is a positive integer.

Then, for each sequence in the kth partition, Mapper k can determine the utility value of the sequence. For example, Mapper k can determine the utility value of the sequence according to a conventional method for calculating the utility value of a sequence. For example, the utility value of a sequence can be the sum of the utility values of each item set constituting the sequence in the sequence. In the present disclosure, the utility value of a sequence s _l can be expressed as u(s _l ).

Then, for each item in the sequence, Mapper k can generate a key-value pair, and the key-value pair can be composed of the item and the utility value of the sequence. For example, for item i in sequence s _l , Mapper k can generate a key-value pair (i, u(s _l )). It can be seen that the sequence identifier of the sequence and the content of the sequence can be input into Mapper k as a key-value pair, and then Mapper k outputs one or more new key-value pairs.

In addition, since different sequences in each partition may contain the same item, the Mapper can generate multiple key-value pairs for the same item in these different sequences. In this case, each Mapper can be configured with a combination module (for example, it can be called a combiner) to determine the local sequence weight utility value of the same item in each partition. Specifically, the local sequence weight utility value of the item in each partition of the sequence database can be determined based on the utility value of the sequence including the item in the partition. For example, the local sequence weight utility value of the item in each partition of the sequence database can be the sum of the utility values of the sequence including the item in the partition. In this way, the workload of the Reducer to be described below can be reduced, thereby reducing the requirements for communication costs and transportation time. For example, the local sequence weight utility value of item i in the kth partition of the sequence database can be determined by the following formula (1):

Among them, i represents an item, _Dk represents the kth partition of the sequence database, s represents the sequence including the item, and u(s) represents the utility value of the sequence.

The following is a specific example to describe the process of determining the local sequence weighted utility value of an item in a partition of a sequence database. For example, in an example where the kth partition of the sequence database includes sequence s ₁ and sequence s ₂ , Mapper k can determine that the utility values of sequence s ₁ and sequence s ₂ are u(s ₁ ) and u(s ₂ ), respectively. Then, for each item in sequence s ₁ , namely item a, item b, item c, item d, and item e, Mapper k can generate key-value pairs (a, u(s ₁ )), (b, u(s ₁ )), (c, u(s ₁ )), (d, u(s ₁ )), (e, u(s ₁ )). For each item in sequence s ₂ , namely item a, item b, item c, item d and item e, Mapper k can generate key-value pairs (a, u(s ₂ )), (b, u(s ₂ )), (c, u(s ₂ )), (d, u(s ₂ )), (e, u(s ₂ )). Therefore, for item a, there are two key-value pairs, namely (a, u(s ₁ )) and (a, u(s ₂ )). These two key-value pairs of item a can also be expressed as (a, _lu ), where _lu is a set including u(s ₁ ) and u(s ₂ ). Then, the combination module sums the elements in the set _lu , namely u(s ₁ )+u(s ₂ ), to obtain the local sequence weight utility value LSWU _ak =u(s ₁ )+u(s ₂ ) of item a in the kth partition. Similarly, the local sequence weighted utility values of item b, item c, item d, and item e in the kth partition can be obtained.

It can be seen that the key-value pair output by Mapper k can be used as the input of the combination module corresponding to Mapper k, and then the combination module generates a new key-value pair. The new key-value pair can be composed of an item and the local sequence weighted utility value of the item in the kth partition. For example, for item i, the combination module corresponding to Mapper k can generate a key-value pair (i, LSWU _ik ). In the example where item i is item a, the combination module corresponding to Mapper k can output a key-value pair (a, LSWU _ak ).

By the above method, the local sequence weighted utility value of each item in each partition of the sequence database can be determined. After the local sequence weighted utility value of each item in each partition of the sequence database is determined, the global sequence weighted utility value of the item can be determined according to the determined local sequence weighted utility value. For example, the sum of the local sequence weighted utility values of each item in each partition of the sequence database can be used as the global sequence weighted utility value of the item.

Specifically, the key-value pairs with the same key value in the output of multiple combination modules can be input into a Reducer in the first stage MapReduce. That is to say, multiple key-value pairs corresponding to the same item in the output of multiple combination modules, for example, multiple key-value pairs (i, LSWU _ik ) corresponding to item i, are input into a Reducer. The Reducer can sum the local sequence weighted utility values in these multiple key-value pairs as the global sequence weighted utility value GSWU _i of item i. For example, the global sequence weighted utility value of item i can be determined by the following formula (2):

Wherein, GSWU(i, D) represents the global sequence weighted utility value of item i in the sequence database D, D _k represents the kth partition of the sequence database, and LSWU(i, D _k ) represents the local sequence weighted utility value of item i in the kth partition of the sequence database.

So far, the process of determining the global sequence weighted utility value of each item in the sequence database has been described. After determining the global sequence weighted utility value of each item in the sequence database, each Reducer in the first stage MapReduce can determine the items whose global sequence weighted utility value is higher than or equal to the first threshold as first-class items, and discard the items whose global sequence weighted utility value is less than the first threshold. Each Reducer can output one or more new key-value pairs, where each new key-value pair can be composed of a first-class item and the global sequence weighted utility value of the first-class item. For example, when item i is a first-class item, a Reducer can output a key-value pair (i, GSWU _i ).

The "first threshold" described here may be determined based on the total utility value of the database and the threshold factor. For example, the "first threshold" may be the product of the total utility value of the database and the threshold factor. The total utility value of the database may be determined according to a conventional method for calculating the total utility value of a database. For example, the total utility value of a database may be the sum of the utility values of each transaction in the database. The total utility value of the database may be represented as u(D). The threshold factor may be pre-set, which may be represented as δ. Therefore, the first threshold may be represented as δ×u(D).

Through step S201, items that are expected to form high-utility sequence patterns can be identified. Unidentified items can be discarded and no longer need to be considered. Through step S201, the space used to search for high-utility sequence patterns is much smaller than the original search space, thereby improving the search speed and accelerating the mining speed.

Returning to Fig. 2, in step S202, the utility value chain list of each sequence in the sequence database is determined. Step S202 may be performed before or after step S201, or may be performed simultaneously with step S201.

According to an example of the present disclosure, for a sequence in a sequence database, a utility value linked list of the sequence can be determined based on the utility values of each item in the sequence and the position of each item in the sequence. The utility value of an item can be the product of the internal utility value and the external utility value of the item. The position of each item in the sequence can include the initial position and adjacent position of each item, wherein the initial position of the item can be the position where the item first appears in the sequence, and the adjacent position can be the position where the item appears next in the sequence. In addition, the utility value linked list of a sequence can include two rows, wherein the first row can be information about the utility value and adjacent position of each item (can be referred to as Utility Position Information, UPinformation), and the second row can be information about the initial position of non-repeating items in the sequence (can be referred to as Header Table). The second row can include non-repeating items and the initial position of each non-repeating item.

Table 3 below shows the utility value chain table of sequence s ₁ in Table 1. As shown in Table 3, the utility value chain table of sequence s ₁ includes two rows. The first row shows the utility values and adjacent positions of each item a, b, c, d, and e in sequence s ₁ , and the second row shows the initial positions of each item a, b, c, d, and e in sequence s _1. Specifically, "a" in the element (a, 10, 3) in the first row represents the first item in sequence s ₁ , "10" represents the utility value of item a in sequence s ₁ is 10, and "3" represents the next position of item a in sequence s _1. "c" in the element (c, 8, -) in the first row represents the fifth item in sequence s ₁ , "8" represents the utility value of item c in sequence s ₁ is 8, and "-" represents that item c has no next position in sequence s _1. "a" in the element (a, 1) in the second row represents the item in sequence s ₁ , and "1" represents the initial position of item a in sequence s ₁ .

Table 3 Example of utility value list of sequence s ₁

It can be understood that the utility value linked list of the sequence is formed by converting and expanding the sequence in the original database, which records information about the original database and the common information that needs to be calculated. The utility value linked list of the sequence can improve the calculation speed of the sequence pattern. This is because the target sequence pattern may have multiple matching items in a single transaction. Therefore, calculating the utility value of the sequence pattern in the transaction requires finding all matching items and then taking the maximum utility value. The utility value linked list records the next position of the item in the transaction. Therefore, there is no need to scan the transaction multiple times. Instead, the maximum utility value of the sequence pattern in the transaction can be calculated by continuously searching for the next position of the item.

Returning to FIG. 2 , in step S203 , based on the determined first category item, at least one candidate global high-utility sequence pattern is mined from the sequence database and a first set is determined, wherein the first set includes the at least one candidate global high-utility sequence pattern, the identifier of the sequence including each candidate global high-utility sequence pattern, and the utility value of each candidate global high-utility sequence pattern in the corresponding sequence. Step S203 can be performed by the local mining part 120 (i.e., the second stage MapReduce) described above.

According to an example of the present disclosure, before executing step S203, the sequences in the sequence database may be assigned to multiple tasks. The number of tasks may be represented as m, where m is a positive integer. For example, m may be a multiple of the number of mappers in the second stage MapReduce. In the following example, the present disclosure is described by taking m as equal to the number of mappers in the second stage MapReduce as an example.

In this example, the sequences in the sequence database can be divided into multiple partitions according to the load balancing algorithm. For example, the sequences in the sequence database can be assigned to multiple tasks according to the load balancing algorithm. Specifically, for a sequence in the sequence database, the number (Num) of first-class items included in the sequence can be determined. Then, a task p with the smallest workload is selected from multiple tasks, and the sequence is assigned to the task p, and the workload of the task p is updated according to the number of first-class items included in the sequence. For example, the workload of the p-th task can be expressed as WL _p . When a sequence is assigned to the task, the workload of the task is updated from WL _p to (WL _p +Num).

In addition, in this example, the algorithm can initialize the workload of each task to 0. Therefore, in the first iteration of the algorithm, since the workload of each task is 0, for a sequence in the sequence database, a task can be randomly selected from multiple tasks and the sequence can be assigned to the task. For example, the first task can be selected from multiple tasks and the sequence can be assigned to the first task.

In addition, the "task" described here may also be referred to as a task file. Hereinafter, the terms task and task file may be used interchangeably.

Through the above load balancing algorithm, it is possible to avoid the impact of the mining algorithm on the workload imbalance between nodes caused by partitioning the database, so that the workload between each node is balanced, thereby effectively improving the speed of mining calculations.

Step S203 may include three sub-steps S2031 to S2033. In step S2031, local high-utility sequence patterns may be mined from each partition of the sequence database according to the determined first category items. Then, in step S2032, at least one candidate global high-utility sequence pattern may be determined according to the mined local high-utility sequence patterns. Then, in step S2033, the first set may be determined. Step S2033 may also be performed simultaneously with step S2033.

In the present disclosure, local high-utility sequence patterns can be mined from various tasks based on the determined first-category items. Some of these local high-utility sequence patterns may be global high-utility sequence patterns, and another part of the sequence patterns may not be global high-utility sequence patterns. The other part of the sequence patterns can be used as candidate global high-utility sequence patterns.

The following describes the process of mining local high-utility sequence patterns from each partition of the sequence database in step S2031. Specifically, for an item belonging to the first category in each sequence included in each partition, the utility value and the residual utility value of the item in each sequence are calculated, a utility list of the item in each sequence is constructed, and the utility value chain of the item is determined according to the utility list of the item in each sequence; and according to the utility value chain of each item in the partition, a local high-utility sequence pattern is mined from the partition.

In the present disclosure, the residual utility value of an item in a sequence may be the sum of the utility values of all items in the sequence and after the item. In addition, the utility list of an item in a sequence may include the identification information of the sequence (which may be represented as sid), the identification information of each item set in which the item is located (which may be represented as tid), the utility value of the item in the sequence in each item set (which may be represented as acu) and the residual utility value (which may be represented as ru), and the indication information (e.g., pointer) from one item set to the next item set (which may be represented as next). In addition, the utility value chain of an item may include the utility list of the item in each sequence.

An example of a utility list of items in a sequence is given below. Assuming that a partition includes the sequences s ₁ to s ₅ shown in Table 1, and item a belongs to the first category of items, then for sequence s ₁ , the identification information of the sequence can be determined to be 1. In addition, item a appears in the first item set of sequence s ₁ , so the utility value and residual utility value of item a in the first item set in sequence s ₁ are determined to be 10 and 84, respectively. Since item a also appears in the second item set of sequence s ₁ , the utility value and residual utility value of item a in the second item set in sequence s ₁ are determined to be 15 and 57, respectively. Since item a also appears in the third item set of sequence s ₁ , the utility value and residual utility value of item a in the third item set in sequence s ₁ are determined to be 20 and 26, respectively. Therefore, the utility list of item a in sequence s ₁ can be constructed. FIG3 shows a schematic diagram of the utility list of item a in sequence s ₁ . As shown in Figure 3, the first "1" in the first set of data (1, 1, 10, 84) represents sequence s ₁ , the second "1" represents the first item set of sequence s ₁ , "10" represents the utility value of item a in the first item set in sequence s ₁ , and "84" represents the residual utility value of item a in the first item set in sequence s _1. In the second set of data (1, 2, 15, 57), "1" represents sequence s ₁ , "2" represents the second item set of sequence s ₁ , "15" represents the utility value of item a in the second item set in sequence s ₁ , and "57" represents the residual utility value of item a in the second item set in sequence s ₁ . In the third set of data (1, 3, 20, 26), "1" represents sequence s ₁ , "3" represents the third item set in sequence s ₁ , "20" represents the utility value of item a in the third item set in sequence s ₁ , and "26" represents the residual utility value of item a in the third item set in sequence s _1. The black arrows in Figure 3 represent pointers from one item set to the next item set.

An example of a utility value chain of an item is given below. In the above example, similarly, the utility list of item a in sequence s ₂ to s ₅ can be determined. Then, the utility value chain of item a can be determined based on the utility list of item a in sequence s ₁ to s _5. FIG4 shows a schematic diagram of the utility value chain of item a. As shown in FIG4 , the utility value chain of item a includes the utility list of item a in sequence s ₁ , the utility list of item a in sequence s ₂ , the utility list of item a in sequence s ₃ , the utility list of item a in sequence s ₄ , and the utility list of item a in sequence s ₅ .

Similarly, the utility value chains of the items belonging to the first category in the sequences included in each partition can be determined. Then, based on the utility value chains of the items in the partition, local high-utility sequence patterns can be mined from the partition. For example, the items in the partition and the utility value chains of the items can be used as inputs of a traditional high-utility sequence pattern algorithm (e.g., HUS-Span algorithm), and one or more local high-utility sequence patterns corresponding to the partition can be output through the algorithm. In addition, the algorithm can also output the utility value of each local high-utility sequence pattern in the corresponding sequence and the identification information of the sequence. The output of the algorithm can be represented as a key-value pair (pattern, {sid, utility}), where pattern represents a local high-utility sequence pattern, sid represents the identification of the sequence containing the local high-utility sequence pattern, and utility represents the utility value of the local high-utility sequence pattern in the corresponding sequence.

The above operation of step S2031 can be performed by the Mapper in the second stage MapReduce. For example, multiple partitions of the sequence database can be processed by multiple Mappers in the second stage MapReduce respectively, so that each Mapper can mine local high-utility sequence patterns from the partition corresponding to it. In this case, the algorithm output described above can be the output of the Mapper. That is, for a partition of the sequence database, the output of the Mapper corresponding to the partition is one or more key-value pairs (pattern, {sid, utility}), where the one or more patterns are one or more local high-utility sequence patterns mined from the partition.

After step S2031, in step S2032, at least one candidate global high-utility sequence pattern can be determined based on the mined local high-utility sequence pattern. For example, key-value pairs with the same key value in the output of multiple Mappers can be input into a Reducer in the second stage MapReduce. That is, multiple key-value pairs corresponding to the same pattern in the output of multiple Mappers, for example, multiple key-value pairs corresponding to pattern x (pattern x, {sid, utility}), are input into a Reducer. The Reducer can determine the sum of multiple utility values corresponding to pattern x, and determine whether pattern x is a global high-utility sequence pattern based on the sum and the first threshold. If the sum is greater than or equal to the first threshold, it is determined that pattern x is a global high-utility sequence pattern. If the sum is less than the first threshold, it is determined that pattern x is not a global high-utility sequence pattern, but a candidate global high-utility sequence pattern.

In addition, each Reducer may output one or more new key-value pairs, each of which may consist of a candidate global high-utility pattern, an identifier of a sequence corresponding to the candidate high-utility sequence pattern, and the utility value of the candidate high-utility sequence pattern in the sequence. For example, the new key-value pair may be expressed as (sid, (pattern, utility)), which means that the form of the key-value pair output by the Mapper is changed.

The “at least one candidate global high-utility sequence pattern” in step S2032 may be determined according to the outputs of multiple Reducers in the second stage of MapReduce. For example, the “at least one candidate global high-utility sequence pattern” in step S2032 may be determined according to the sequence patterns in the key-value pairs output by multiple Reducers in the second stage of MapReduce. For example, the outputs of multiple Reducers may be (s ₁ , (pattern 1, utility 1)), (s ₂ , (pattern 1, utility 1)), (s ₃ , (pattern 2, utility 2)), (s ₃ , (pattern 1, utility 1)), (s ₄ , (pattern2, utility 2)), then the “at least one candidate global high-utility sequence pattern” in step S2032 may be pattern 1 and pattern 2.

In addition, after step S2032, in step S2033, a first set can be determined. For example, the first set can be determined based on the outputs of multiple Reducers in the second stage MapReduce. The first set may include the at least one candidate global high-utility sequence pattern, the identifier of the sequence including each candidate global high-utility sequence pattern, and the utility value of each candidate global high-utility sequence pattern in the corresponding sequence. For example, the first set may include multiple subsets, each subset including the identifier of the sequence, the candidate global high-utility sequence pattern included in the sequence, and the utility value of the candidate global high-utility sequence pattern included in the sequence in the sequence. For example, the outputs of multiple Reducers in the second stage of MapReduce can be ( _s1 , (pattern 1, utility 1)), ( _s2 , (pattern 1, utility 1)), ( _s3 , (pattern 2, utility 2)), ( _s3 , (pattern 1, utility 1)), ( _s4 , (pattern 2, utility 2)), then the first set can include four subsets, the first subset is ( _s1 , (pattern 1, utility 1)), the second subset is ( _s2 , (pattern 1, utility 1)), the third subset is ( _S3 , (pattern 2, utility 2), (pattern 1, utility 1)), and the fourth subset is ( _s4 , (pattern 2, utility 2).

It can be understood that the calculation of the utility value of the candidate global high-utility sequence pattern can be accelerated by the data structure of the first set. Specifically, if the sequence includes a candidate global high-utility sequence pattern, the utility value of the candidate global high-utility sequence pattern can be directly obtained from the first set without calculating its utility value again, because repeated calculation will take a lot of time.

In the above example, no corresponding combination module is configured for the Mapper in the second stage MapReduce. However, the present disclosure is not limited to this. For example, a corresponding combination module may also be configured for the Mapper in the second stage MapReduce.

Returning to Fig. 2, in step S204, according to the utility value chain list of each sequence and the first set, a global high-utility sequence pattern is mined from the at least one candidate global high-utility sequence pattern. Step S204 can be performed by the integration part 130 (ie, the third stage MapReduce) described above.

Step S204 will be described in detail below in conjunction with FIG5. FIG5 is a flowchart of a method 500 for mining a global high utility sequence pattern from at least one candidate global high utility sequence pattern according to an embodiment of the present disclosure. As shown in FIG5, in step S501, the local utility value of each candidate global high utility sequence pattern can be determined based on the utility value linked list of each sequence and the first set.

Specifically, at least one candidate global high-utility sequence pattern and the first set may be used as inputs of multiple mappers in the third stage MapReduce. For example, at least one candidate global high-utility sequence pattern may be divided into multiple groups, and then the multiple groups are respectively input into multiple mappers. In addition, the first set may be input into each mapper.

Then, each Mapper can determine the utility value of each candidate global high utility sequence pattern among the multiple candidate global high utility sequence patterns corresponding to it. For example, for a candidate global high utility sequence pattern among the multiple candidate global high utility sequence patterns corresponding to a Mapper, the Mapper can determine whether the first set includes the candidate global high utility sequence pattern. When the first set includes the candidate global high utility sequence pattern, the utility value of the candidate global high utility sequence pattern can be determined according to the first set. In addition, when the first set does not include the candidate global high utility sequence pattern, the utility value of the candidate global high utility sequence pattern can be determined according to the utility value chain list of the sequence.

This is because, when the utility value of the candidate global high-utility sequence pattern has been calculated, the utility value of the candidate global high-utility sequence pattern can be directly obtained by querying the sidset of the sequence including the candidate global high-utility sequence pattern. However, when the utility value of the candidate global high-utility sequence pattern is not calculated, it is necessary to check whether it appears in a specific sequence. If this situation occurs, it is necessary to calculate the utility value of the candidate global high-utility sequence pattern according to the specific sequence. It should be noted that the calculation of this operation is time-consuming because the specific sequence needs to be scanned, and the candidate global high-utility sequence pattern may have multiple matches in the specific sequence. Therefore, it is necessary to scan the specific sequence multiple times to find the maximum match as the utility value of the candidate global high-utility sequence pattern in the specific sequence. Therefore, to complete the mining task, the entire sequence database must be scanned multiple times. The utility value linked list of the sequence proposed in the present disclosure is a compact data structure suitable for processing big data problems.

The following will describe an example of determining the utility value of a candidate global high-utility sequence pattern according to a utility value chain table of a sequence in conjunction with a specific example. For example, the utility value of a candidate global high-utility sequence pattern <[a, c], b> can be determined according to the utility value chain table of the sequence _s 1 shown in Table 2 above. Specifically, since item a and item c are in the same item set, all positions where a and c appear can be found according to the position where item c appears, i.e., the first position (1, 2) with a utility value of 22, and the second position (3, 5) with a utility value of 23. For the first position (1, 2) satisfied by items a and c, all positions satisfied by item b can be found, i.e., 4 and 7, and then the utility values of items a, c, and b combined can be calculated as 22+3=25 and 22+15=37. For the second position (3, 5) satisfied by items a and c, all positions satisfied by item b can be found, i.e., 7, and then the utility value of items a, c, and b combined can be calculated as 23+15=38. Therefore, the utility value of the sequence pattern <[a, c], b> is max{25, 37, 38}=38.

In the present disclosure, each Mapper in the third stage MapReduce can output one or more new key-value pairs, wherein each new key-value pair can be composed of a candidate global high-utility sequence pattern and its utility value. For example, the new key-value pair can be expressed as (pattern, utility).

In addition, the same Mapper may output multiple key-value pairs (pattern, utility) corresponding to the same candidate global high-utility sequence pattern. For example, for the candidate global high-utility sequence pattern pattern y, the same Mapper may output two key-value pairs, namely (pattern y, utility 1) and (pattern y, utility 2). These two key-value pairs can also be expressed as (pattern y, G _u ), where G _u is a set including utility 1 and utility 2.

In addition, in this case, each Mapper can be configured with a combination module (for example, it can be called a combiner) to determine the local utility value of the same candidate global high-utility sequence pattern. Specifically, the local utility value of the same candidate global high-utility sequence pattern can be determined based on the utility values in multiple key-value pairs corresponding to the candidate global high-utility sequence pattern. For example, the local utility value of the same candidate global high-utility sequence pattern can be the sum of the utility values in multiple key-value pairs corresponding to the candidate global high-utility sequence pattern. For example, for the candidate global high-utility sequence pattern pattern y, the same Mapper may output two key-value pairs, namely (patterny, utility 1) and (pattern y, utility 2), then the local utility value local~utility for the candidate global high-utility sequence pattern pattern y is (utility 1+utility 2).

In the present disclosure, the combination module may also output one or more new key-value pairs, wherein each new key-value pair may be composed of a candidate global high-utility sequence pattern and its local utility value. For example, the new key-value pair may be expressed as (pattern, local-utility). In the example where the candidate global high-utility sequence pattern is pattern y, the combination pattern may output a key-value pair (pattern y, utility 1+utility 2).

Returning to FIG. 5, in step S502, the global utility value of each candidate global high utility sequence pattern can be determined according to the local utility value of each candidate global high utility sequence pattern. For example, for each candidate global high utility sequence pattern, the global utility value of the candidate global high utility sequence pattern can be determined according to multiple local utility values of the candidate global high utility sequence pattern. For example, the sum of multiple local utility values of the candidate global high utility sequence pattern can be used as the global utility value of the candidate global high utility sequence pattern.

Specifically, the key-value pairs with the same key value in the output of multiple combination modules can be input into a Reducer in the third stage MapReduce. That is, multiple key-value pairs corresponding to the same candidate global high-utility sequence pattern in the output of multiple combination modules, for example, multiple key-value pairs corresponding to the candidate global high-utility sequence pattern pattern y, are input into a Reducer. The Reducer can sum the local utility values in these multiple key-value pairs as the global-utility value of the candidate global high-utility sequence pattern.

Then, in step S503, a sequence pattern whose global utility value is greater than the first threshold value can be determined as a global high-utility sequence pattern. For example, each Reducer in the third stage MapReduce can determine a sequence pattern whose global utility value is higher than or equal to the first threshold value as a global high-utility sequence pattern. Each Reducer can output one or more new key-value pairs, wherein each new key-value pair can be composed of a global high-utility sequence pattern and the global utility value of the global high-utility sequence pattern. For example, when pattern y is a global high-utility sequence pattern, a certain Reducer can output a key-value pair (pattern y, global-utility). Therefore, the sequence patterns in the key-value pairs output by each Reducer in the third stage MapReduce are all global high-utility sequence patterns.

Through the method for mining global high-utility sequence patterns provided by this embodiment, the utility value linked list and the first set of each sequence in the sequence database are determined, and the global high-utility sequence patterns are mined based on these two data structures, which saves a lot of time, speeds up the calculation process of calculating the global utility value in the sequence database, speeds up the mining speed, and reduces the time complexity.

Hereinafter, a device corresponding to the method shown in FIG. 2 according to an embodiment of the present disclosure is described with reference to FIG. 6. FIG. 6 shows a schematic diagram of the structure of a device 600 for mining global high-utility sequence patterns according to an embodiment of the present disclosure. Since the functions of the device 600 are the same as the details of the method described above with reference to FIG. 2, a detailed description of the same contents is omitted here for simplicity. As shown in FIG6 , the device 600 includes: a first determination unit 610, configured to determine a first category of items in a sequence database, wherein the first category of items are items whose global sequence weight utility values are higher than a first threshold; a second determination unit 620, configured to determine a utility value chain list of each sequence in the sequence database; a first mining unit 630, configured to mine at least one candidate global high-utility sequence pattern from the sequence database and determine a first set according to the determined first category of items, wherein the first set includes the at least one candidate global high-utility sequence pattern, the identifier of the sequence including each candidate global high-utility sequence pattern, and the utility value of each candidate global high-utility sequence pattern in the corresponding sequence; and a second mining unit 640, configured to mine a global high-utility sequence pattern from the at least one candidate global high-utility sequence pattern according to the utility value chain list of each sequence and the first set. In addition to these four units, the device 600 may also include other components, however, since these components are irrelevant to the content of the embodiment of the present disclosure, their illustration and description are omitted here.

The first determination unit 610 can determine the global sequence weight utility value of each item in the sequence database, and determine the items with global sequence weight utility values higher than the first threshold as first-category items. The first determination unit 610 can be the identification part 110 described above (ie, the first-stage MapReduce).

The process of determining the global sequence weight utility value of each item in the sequence database by the first determination unit 610 will be described below. According to an example of the present disclosure, for each item in the sequence database, the first determination unit 610 may first determine the local sequence weight utility value (LSWU) of the item in each partition of the sequence database, and then determine the global sequence weight utility value of the item according to the determined local sequence weight utility value.

For example, first, the first determination unit 610 may divide the sequence database into a plurality of partitions, and assign the plurality of partitions to a plurality of mappers in the first stage MapReduce. For example, the sequence database may be divided into n partitions, and the 1st partition is assigned to Mapper 1 in the first stage MapReduce, ..., the kth partition is assigned to Mapper k in the first stage MapReduce, ..., the nth partition is assigned to Mappern in the first stage MapReduce, where 1≤k≤n is a positive integer.

Then, for each sequence in the kth partition, Mapper k can determine the utility value of the sequence. For example, Mapper k can determine the utility value of the sequence according to a conventional method for calculating the utility value of a sequence. For example, the utility value of a sequence can be the sum of the utility values of each item set constituting the sequence in the sequence. In the present disclosure, the utility value of a sequence s _l can be expressed as u(s _l ).

Then, for each item in the sequence, Mapper k can generate a key-value pair, and the key-value pair can be composed of the item and the utility value of the sequence. For example, for item i in sequence s _l , Mapper k can generate a key-value pair (i, u(s _l )). It can be seen that the sequence identifier of the sequence and the content of the sequence can be input into Mapper k as a key-value pair, and then Mapper k outputs one or more new key-value pairs.

In addition, since different sequences in each partition may contain the same item, the Mapper can generate multiple key-value pairs for the same item in these different sequences. In this case, each Mapper can be configured with a combination module (for example, it can be called a combiner) to determine the local sequence weight utility value of the same item in each partition. Specifically, the local sequence weight utility value of the item in each partition of the sequence database can be determined based on the utility value of the sequence including the item in the partition. For example, the local sequence weight utility value of the item in each partition of the sequence database can be the sum of the utility values of the sequence including the item in the partition.

It can be seen that the key-value pair output by Mapper k can be used as the input of the combination module corresponding to Mapper k, and then the combination module generates a new key-value pair. The new key-value pair can be composed of an item and the local sequence weighted utility value of the item in the kth partition. For example, for item i, the combination module corresponding to Mapper k can generate a key-value pair (i, LSWU _ik ). In the example where item i is item a, the combination module corresponding to Mapper k can output a key-value pair (a, LSWU _ak ).

In the above manner, the first determining unit 610 can determine the local sequence weight utility value of each item in each partition of the sequence database. After determining the local sequence weight utility value of each item in each partition of the sequence database, the first determining unit 610 can determine the global sequence weight utility value of the item according to the determined local sequence weight utility value. For example, the sum of the local sequence weight utility values of each item in each partition of the sequence database can be used as the global sequence weight utility value of the item.

Specifically, the key-value pairs with the same key value in the outputs of the multiple combination modules can be input into a Reducer in the first stage MapReduce. That is, multiple key-value pairs corresponding to the same item in the outputs of the multiple combination modules, for example, multiple key-value pairs (i, LSWU _ik ) corresponding to item i, are input into a Reducer. The Reducer can sum the local sequence weighted utility values in the multiple key-value pairs as the global sequence weighted utility value GSWU _i of item i.

So far, the process of determining the global sequence weighted utility value of each item in the sequence database has been described. After determining the global sequence weighted utility value of each item in the sequence database, each Reducer in the first stage MapReduce can determine the items whose global sequence weighted utility value is greater than or equal to the first threshold as first-class items. Each Reducer can output one or more new key-value pairs, where each new key-value pair can be composed of a first-class item and the global sequence weighted utility value of the first-class item. For example, when item i is a first-class item, a Reducer can output a key-value pair (i, GSWU _i ).

According to an example of the present disclosure, for a sequence in a sequence database, the second determination unit 620 may determine the utility value chain table of the sequence according to the utility value of each item in the sequence and the position of each item in the sequence. The utility value of an item may be the product of the internal utility value and the external utility value of the item. The position of each item in the sequence may include the initial position and adjacent position of each item, wherein the initial position of the item may be the position where the item first appears in the sequence, and the adjacent position may be the position where the item appears next in the sequence. In addition, the utility value chain table of a sequence may include two rows, wherein the first row may be information about the utility value and adjacent position of each item (which may be referred to as Utility Position Information, UP information), and the second row may be information about the initial position of non-repeating items in the sequence (which may be referred to as Header Table). The second row may include non-repeating items and the initial positions of each non-repeating item.

It can be understood that the utility value linked list of the sequence is formed by converting and expanding the sequence in the original database, which records information about the original database and the common information that needs to be calculated. The utility value linked list of the sequence can improve the calculation speed of the sequence pattern. This is because the target sequence pattern may have multiple matching items in a single transaction. Therefore, calculating the utility value of the sequence pattern in the transaction requires finding all matching items and then taking the maximum utility value. The utility value linked list records the next position of the item in the transaction. Therefore, there is no need to scan the transaction multiple times. Instead, the maximum utility value of the sequence pattern in the transaction can be calculated by continuously searching for the next position of the item.

In the present disclosure, the first mining unit 630 may be the local mining part 120 (ie, the second stage MapReduce) described above.

According to an example of the present disclosure, the apparatus 600 may further include a load distribution unit (not shown in the figure), which is configured to distribute the sequences in the sequence database to a plurality of tasks. The number of tasks may be represented as m, where m is a positive integer. For example, m may be a multiple of the number of Mappers in the second stage MapReduce. In the following example, the present disclosure is described by taking m equal to the number of Mappers in the second stage MapReduce as an example.

In this example, the load distribution unit can divide the sequences in the sequence database into multiple partitions according to the load balancing algorithm. For example, the sequences in the sequence database can be distributed to multiple tasks according to the load balancing algorithm. Specifically, for a sequence in the sequence database, the number (Num) of first-category items included in the sequence can be determined. Then, a task p with the smallest workload is selected from multiple tasks, and the sequence is distributed to the task p, and the workload of the task p is updated according to the number of first-category items included in the sequence. For example, the workload of the p-th task can be expressed as WL _p , and when a sequence is distributed to the task, the workload of the task is updated from WL _p to (WL _p +Num).

In addition, in this example, the algorithm can initialize the workload of each task to 0. Therefore, in the first iteration of the algorithm, since the workload of each task is 0, for a sequence in the sequence database, a task can be randomly selected from multiple tasks and the sequence can be assigned to the task. For example, the first task can be selected from multiple tasks and the sequence can be assigned to the first task.

In addition, the "task" described here may also be referred to as a task file. Hereinafter, the terms task and task file may be used interchangeably.

In the present disclosure, the first mining unit 630 may mine local high-utility sequence patterns from each partition of the sequence database according to the determined first category items. Then, the first mining unit 630 may determine at least one candidate global high-utility sequence pattern according to the mined local high-utility sequence pattern. Then, the first mining unit 630 may determine the first set.

In the present disclosure, local high-utility sequence patterns can be mined from various tasks based on the determined first-category items. Some of these local high-utility sequence patterns may be global high-utility sequence patterns, and another part of the sequence patterns may not be global high-utility sequence patterns. The other part of the sequence patterns can be used as candidate global high-utility sequence patterns.

The following describes the process of mining local high-utility sequence patterns from each partition of the sequence database by the first mining unit 630. Specifically, for an item belonging to the first category in each sequence included in each partition, the utility value and the residual utility value of the item in each sequence are calculated, a utility list of the item in each sequence is constructed, and the utility value chain of the item is determined according to the utility list of the item in each sequence; and according to the utility value chain of each item in the partition, a local high-utility sequence pattern is mined from the partition.

In the present disclosure, the residual utility value of an item in a sequence may be the sum of the utility values of all items in the sequence and after the item. In addition, the utility list of an item in a sequence may include the identification information of the sequence (which may be represented as sid), the identification information of each item set in which the item is located (which may be represented as tid), the utility value of the item in the sequence in each item set (which may be represented as acu) and the residual utility value (which may be represented as ru), and the indication information (e.g., pointer) from one item set to the next item set (which may be represented as next). In addition, the utility value chain of an item may include the utility list of the item in each sequence.

Similarly, the utility value chains of the items belonging to the first category in the sequences included in each partition can be determined. Then, based on the utility value chains of the items in the partition, local high-utility sequence patterns can be mined from the partition. For example, the items in the partition and the utility value chains of the items can be used as inputs of a traditional high-utility sequence pattern algorithm, and one or more local high-utility sequence patterns corresponding to the partition can be output through the algorithm. In addition, the utility value of each local high-utility sequence pattern in the corresponding sequence and the identification information of the sequence can also be output through the algorithm. The output of the algorithm can be represented as a key-value pair (pattern, {sid, utility}), where pattern represents a local high-utility sequence pattern, sid represents the identification of the sequence containing the local high-utility sequence pattern, and utility represents the utility value of the local high-utility sequence pattern in the corresponding sequence.

The above operations can be performed by the Mapper in the second stage MapReduce. For example, multiple partitions of the sequence database can be processed by multiple Mappers in the second stage MapReduce respectively, so that each Mapper can mine local high-utility sequence patterns from the partitions corresponding to it. In this case, the algorithm output described above can be the output of the Mapper. That is, for a partition of the sequence database, the output of the Mapper corresponding to the partition is one or more key-value pairs (pattern, {sid, utility}), where the one or more patterns are one or more local high-utility sequence patterns mined from the partition.

Then, the first mining unit 630 can determine at least one candidate global high-utility sequence pattern based on the mined local high-utility sequence pattern. For example, the key-value pairs with the same key value in the output of multiple Mappers can be input into a Reducer in the second stage MapReduce. That is, multiple key-value pairs corresponding to the same pattern in the output of multiple Mappers, for example, multiple key-value pairs corresponding to pattern x (pattern x, {sid, utility}), are input into a Reducer. The Reducer can determine the sum of multiple utility values corresponding to pattern x, and determine whether pattern x is a global high-utility sequence pattern based on the sum and the first threshold. If the sum is greater than or equal to the first threshold, it is determined that pattern x is a global high-utility sequence pattern. If the sum is less than the first threshold, it is determined that pattern x is not a global high-utility sequence pattern, but a candidate global high-utility sequence pattern.

In addition, each Reducer may output one or more new key-value pairs, each of which may consist of a candidate global high-utility pattern, an identifier of a sequence corresponding to the candidate high-utility sequence pattern, and the utility value of the candidate high-utility sequence pattern in the sequence. For example, the new key-value pair may be expressed as (sid, (pattern, utility)), which means that the form of the key-value pair output by the Mapper is changed.

The "at least one candidate global high-utility sequence pattern" may be determined based on the outputs of multiple Reducers in the second stage MapReduce. For example, the "at least one candidate global high-utility sequence pattern" in step S2032 may be determined based on the sequence patterns in the key-value pairs output by multiple Reducers in the second stage MapReduce. For example, the outputs of multiple Reducers may be (s ₁ , (pattern 1, utility 1)), (s ₂ , (pattern 1, utility 1)), (s ₃ , (pattern 2, utility 2)), (S ₃ , (pattern 1, utility 1)), (s ₄ , (pattern 2, utility 2)), then the "at least one candidate global high-utility sequence pattern" in step S2032 may be pattern 1 and pattern 2.

In addition, the first mining unit 630 can determine a first set. For example, the first set can be determined based on the outputs of multiple Reducers in the second stage MapReduce. The first set can include at least one candidate global high-utility sequence pattern, an identifier of a sequence including each candidate global high-utility sequence pattern, and a utility value of each candidate global high-utility sequence pattern in the corresponding sequence. For example, the first set may include multiple subsets, each subset including an identifier of a sequence, a candidate global high-utility sequence pattern included in the sequence, and a utility value of the candidate global high-utility sequence pattern included in the sequence in the sequence. For example, the outputs of multiple Reducers in the second stage of MapReduce can be ( _s1 , (pattern 1, utility 1)), ( _s2 , (pattern 1, utility 1)), ( _s3 , (pattern 2, utility 2)), ( _s3 , (pattern 1, utility 1)), ( _s4 , (pattern 2, utility2)), then the first set can include four subsets, the first subset is (s1, (pattern 1, utility 1)), the second subset is ( _s2 , (pattern 1, utility 1)), the third subset is ( _s3 , (pattern 2, utility 2), (pattern 1, utility 1)), and the fourth subset is ( _s4 , (pattern 2, utility 2).

In the above example, no corresponding combination module is configured for the Mapper in the second stage MapReduce. However, the present disclosure is not limited to this. For example, a corresponding combination module may also be configured for the Mapper in the second stage MapReduce.

Furthermore, in the present disclosure, the second mining unit 640 may be the integration part 130 (ie, the third stage MapReduce) described above.

The second mining unit 640 may determine the local utility value of each candidate global high-utility sequence pattern according to the utility value chain list of each sequence and the first set.

Specifically, at least one candidate global high-utility sequence pattern and the first set may be used as inputs of multiple mappers in the third stage MapReduce. For example, at least one candidate global high-utility sequence pattern may be divided into multiple groups, and then the multiple groups are respectively input into multiple mappers. In addition, the first set may be input into each mapper.

Then, each Mapper can determine the utility value of each candidate global high utility sequence pattern among the multiple candidate global high utility sequence patterns corresponding to it. For example, for a candidate global high utility sequence pattern among the multiple candidate global high utility sequence patterns corresponding to a Mapper, the Mapper can determine whether the first set includes the candidate global high utility sequence pattern. When the first set includes the candidate global high utility sequence pattern, the utility value of the candidate global high utility sequence pattern can be determined according to the first set. In addition, when the first set does not include the candidate global high utility sequence pattern, the utility value of the candidate global high utility sequence pattern can be determined according to the utility value chain list of the sequence.

In the present disclosure, each Mapper in the third stage MapReduce can output one or more new key-value pairs, wherein each new key-value pair can be composed of a candidate global high-utility sequence pattern and its utility value. For example, the new key-value pair can be expressed as (pattern, utility).

In addition, the same Mapper may output multiple key-value pairs (pattern, utility) corresponding to the same candidate global high-utility sequence pattern. For example, for the candidate global high-utility sequence pattern pattern y, the same Mapper may output two key-value pairs, namely (pattern y, utility 1) and (pattern y, utility 2). These two key-value pairs can also be expressed as (pattern y, G _u ), where G _u is a set including utility 1 and utility 2.

In addition, in this case, each Mapper can be configured with a combination module (for example, it can be called a combiner) to determine the local utility value of the same candidate global high-utility sequence pattern. Specifically, the local utility value of the same candidate global high-utility sequence pattern can be determined based on the utility values in multiple key-value pairs corresponding to the candidate global high-utility sequence pattern. For example, the local utility value of the same candidate global high-utility sequence pattern can be the sum of the utility values in multiple key-value pairs corresponding to the candidate global high-utility sequence pattern. For example, for the candidate global high-utility sequence pattern pattern y, the same Mapper may output two key-value pairs, namely (patterny, utility 1) and (pattern y, utility 2), then the local utility value local-utility for the candidate global high-utility sequence pattern pattern y is (utility 1+utility 2).

In the present disclosure, the combination module may also output one or more new key-value pairs, wherein each new key-value pair may be composed of a candidate global high-utility sequence pattern and its local utility value. For example, the new key-value pair may be expressed as (pattern, local-utility). In the example where the candidate global high-utility sequence pattern is pattern y, the combination pattern may output a key-value pair (pattern y, utility 1+utility 2).

Then, the second mining unit 640 can determine the global utility value of each candidate global high utility sequence pattern according to the local utility value of each candidate global high utility sequence pattern. For example, for each candidate global high utility sequence pattern, the global utility value of the candidate global high utility sequence pattern can be determined according to multiple local utility values of the candidate global high utility sequence pattern. For example, the sum of multiple local utility values of the candidate global high utility sequence pattern can be used as the global utility value of the candidate global high utility sequence pattern.

Specifically, the key-value pairs with the same key value in the output of multiple combination modules can be input into a Reducer in the third stage MapReduce. That is, multiple key-value pairs corresponding to the same candidate global high-utility sequence pattern in the output of multiple combination modules, for example, multiple key-value pairs corresponding to the candidate global high-utility sequence pattern pattern y, are input into a Reducer. The Reducer can sum the local utility values in these multiple key-value pairs as the global-utility value of the candidate global high-utility sequence pattern.

Then, the second mining unit 640 can determine the sequence pattern whose global utility value is greater than the first threshold as a global high-utility sequence pattern. For example, each Reducer in the third stage MapReduce can determine the sequence pattern whose global utility value is higher than or equal to the first threshold as a global high-utility sequence pattern. Each Reducer can output one or more new key-value pairs, wherein each new key-value pair can be composed of a global high-utility sequence pattern and the global utility value of the global high-utility sequence pattern. For example, when pattern y is a global high-utility sequence pattern, a certain Reducer can output a key-value pair (pattern y, global-utility). Therefore, the sequence patterns in the key-value pairs output by each Reducer in the third stage MapReduce are all global high-utility sequence patterns.

Through the device for mining global high-utility sequence patterns provided by this embodiment, the utility value linked list and the first set of each sequence in the sequence database are determined, and the global high-utility sequence pattern is mined based on these two data structures, which saves a lot of time, speeds up the calculation process of calculating the global utility value in the sequence database, speeds up the mining speed, and reduces the time complexity.

In addition, the apparatus according to the embodiment of the present disclosure can also be implemented with the aid of the architecture of the computing device shown in FIG7. FIG7 shows the architecture of the computing device. As shown in FIG7, the computing device 700 may include a bus 710, one or more CPUs 720, a read-only memory (ROM) 730, a random access memory (RAM) 740, a communication port 750 connected to a network, an input/output component 760, a hard disk 770, and the like. The storage device in the computing device 700, such as the ROM 730 or the hard disk 770, can store various data or files used for computer processing and/or communication and program instructions executed by the CPU. The computing device 700 may also include a user interface 780. Of course, the architecture shown in FIG7 is only exemplary. When implementing different devices, one or more components in the computing device shown in FIG7 may be omitted according to actual needs.

The embodiments of the present disclosure may also be implemented as a computer-readable storage medium. Computer-readable instructions are stored on a computer-readable storage medium according to an embodiment of the present disclosure. When the computer-readable instructions are executed by a processor, the method according to the embodiment of the present disclosure described with reference to the above figures may be executed. The computer-readable storage medium includes, but is not limited to, for example, a volatile memory and/or a non-volatile memory. The volatile memory may, for example, include a random access memory (RAM) and/or a cache memory (cache), etc. The non-volatile memory may, for example, include a read-only memory (ROM), a hard disk, a flash memory, etc.

Those skilled in the art will appreciate that the contents disclosed in this disclosure may be subject to various variations and improvements. For example, the various devices or components described above may be implemented by hardware, or by software, firmware, or a combination of some or all of the three.

In addition, as shown in the present disclosure and claims, unless the context clearly indicates an exception, the words "a", "an", "a kind" and/or "the" do not specifically refer to the singular, but may also include the plural. The words "first", "second" and similar words used in the present disclosure do not indicate any order, quantity or importance, but are only used to distinguish different components. Similarly, words such as "include" or "comprise" mean that the elements or objects appearing before the word include the elements or objects listed after the word and their equivalents, without excluding other elements or objects. Words such as "connect" or "connected" and similar words are not limited to physical or mechanical connections, but may include electrical connections, whether direct or indirect.

In addition, flow charts are used in the present disclosure to illustrate the operations performed by the system according to the embodiments of the present disclosure. It should be understood that the preceding or following operations are not necessarily performed precisely in order. On the contrary, various steps may be processed in reverse order or simultaneously. At the same time, other operations may also be added to these processes, or one or more operations may be removed from these processes.

Unless otherwise defined, all terms (including technical and scientific terms) used herein have the same meaning as commonly understood by one of ordinary skill in the art to which the invention belongs. It should also be understood that terms such as those defined in common dictionaries should be interpreted as having a meaning consistent with their meaning in the context of the relevant technology and should not be interpreted in an idealized or extremely formal sense, unless explicitly defined as such herein.

The present disclosure is described in detail above, but it is obvious to those skilled in the art that the present disclosure is not limited to the embodiments described in this specification. The present disclosure can be implemented as a modification and variation without departing from the purpose and scope of the present disclosure as determined by the claims. Therefore, the description in this specification is for the purpose of illustration and does not have any restrictive meaning for the present disclosure.

Claims (15)

1. A method for mining global high utility sequence patterns, comprising:

Determining a first type of item in the sequence database, wherein the first type of item is an item with a global sequence weight utility value higher than a first threshold value;

determining a utility value linked list of each sequence in the sequence database;

Mining at least one candidate global high utility sequence pattern from the sequence database and determining a first set according to the determined first class of items, wherein the first set comprises a plurality of subsets, each subset comprising the at least one candidate global high utility sequence pattern, an identification of a sequence comprising a respective candidate global high utility sequence pattern, and utility values of the respective candidate global high utility sequence pattern in the respective sequence; and

Mining a global high utility sequence pattern from the at least one candidate global high utility sequence pattern based on a linked list of utility values for each sequence and the first set,

Wherein mining global high utility sequence patterns from the at least one candidate global high utility sequence pattern according to the utility value linked list of each sequence and the first set comprises:

When the first set includes the at least one candidate global high utility sequence pattern, a utility value of the at least one candidate global high utility sequence pattern is determined from the first set.

2. The method of claim 1, wherein said determining a first type of entry in a sequence database comprises:

determining a global sequence weight utility value of each item in the sequence database; and

Items with global sequence weight utility values above a first threshold are determined to be of a first type.

3. The method of claim 2, wherein determining a global sequence weight utility value for each item in the sequence database comprises:

determining local sequence weight utility values of the item in each partition of the sequence database; and

And determining a global sequence weight utility value of the item according to the determined local sequence weight utility value.

4. A method as claimed in claim 3, wherein the local sequence weight utility value of the term at each partition of the sequence database is determined from utility values of sequences comprising the term in that partition.

5. The method of any one of claims 1 to 4, wherein said determining a linked list of utility values for each sequence in the sequence database comprises:

And determining a utility value linked list of the sequence according to the utility value of each item in the sequence and the position of each item in the sequence.

6. The method of any of claims 1 to 4, wherein the mining at least one candidate global high utility sequence pattern from the sequence database according to the determined first class of items comprises:

mining a local high utility sequence pattern from each partition of the sequence database according to the determined first class item; and

At least one candidate global utility sequence pattern is determined from the mined local utility sequence patterns.

7. The method of claim 6, wherein mining a local high utility sequence pattern from each partition of the sequence database according to the determined first type of item comprises:

For an item belonging to the first class of items in the respective sequences comprised by the partition,

Calculating utility values and remaining utility values of the item in each sequence, wherein the remaining utility values of the item in a sequence are the sum of utility values of all items in the sequence that follow the item;

Constructing a utility list of the item in each sequence;

determining a utility value chain of the item according to utility lists of the item in each sequence;

and mining a local high-utility sequence mode from the partition according to the utility value chains of the items in the partition.

8. The method of any of claims 1 to 4, wherein mining global utility sequence patterns from the at least one candidate global utility sequence pattern according to a utility value linked list of individual sequences and the first set comprises:

determining local utility values of each candidate global high utility sequence mode according to utility value linked lists of each sequence and the first set;

Determining the global utility value of each candidate global high utility sequence mode according to the local utility value of each candidate global high utility sequence mode; and

A sequence pattern having a global utility value greater than a first threshold is determined as a global high utility sequence pattern.

9. The method of claim 6, further comprising:

and dividing the sequence in the sequence database into a plurality of partitions according to a load balancing algorithm.

10. An apparatus for mining global high utility sequence patterns, comprising:

A first determining unit configured to determine a first type of item in the sequence database, wherein the first type of item is an item for which the global sequence weight utility value is higher than a first threshold value;

the second determining unit is configured to determine utility value linked lists of all sequences in the sequence database;

A first mining unit configured to mine at least one candidate global utility sequence pattern from the sequence database according to the determined first class item and determine a first set, wherein the first set comprises a plurality of subsets, each subset comprising the at least one candidate global utility sequence pattern, an identification of a sequence comprising a respective candidate global utility sequence pattern, and utility values of the respective candidate global utility sequence pattern in the respective sequence; and

A second mining unit configured to mine global high utility sequence patterns from the at least one candidate global high utility sequence pattern according to a utility value linked list of each sequence and the first set,

Wherein the second mining unit is further configured to determine utility values of the at least one candidate global high utility sequence pattern from the first set when the first set includes the at least one candidate global high utility sequence pattern.

11. The apparatus of claim 10, wherein the first determining unit is configured to determine global sequence weight utility values for respective items in the sequence database; and determining an item with a global sequence weight utility value higher than a first threshold as a first type item.

12. The apparatus according to claim 10 or 11, wherein the second determining unit is configured to determine a utility value linked list for each sequence based on the utility values of the respective items in the sequence and the positions of the respective items in the sequence.

13. The apparatus of claim 10 or 11, wherein the second mining unit is configured to determine local utility values for each candidate globally highly-utility sequence pattern from a linked list of utility values for each sequence and the first set; determining the global utility value of each candidate global high utility sequence mode according to the local utility value of each candidate global high utility sequence mode; and determining a sequence pattern having a global utility value greater than a first threshold as a global high utility sequence pattern.

14. An apparatus for mining global high utility sequence patterns, comprising:

a processor; and

A memory, wherein the memory has stored therein a computer executable program which, when executed by the processor, performs the method of any of claims 1-9.

15. A computer readable storage medium having stored thereon instructions which, when executed by a processor, cause the processor to perform the method of any of claims 1-9.