JP2008287550A - Recommendation device in consideration of order of purchase, recommendation method, recommendation program and recording medium with the program recorded thereon - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a recommendation device that reduces a calculation cost while considering the order of purchases, with high prediction accuracy. <P>SOLUTION: The recommendation device 1 comprises: a preprocessing part 21 for generating input data 46 that has extracted purchase history for each user by using a user purchase history log 45; an extended Markov model estimation part 22 for estimating the prior probability that the user purchases the product from the input data 46 and a gap Markov model representing the probability that a specific product is purchased in the past when the user purchases a predetermined product; a weight estimation part 23 for building a coupled model that couples the prior probability 47 and the gap Markov model 48 by the maximum entropy principle, and estimating the weight representing unknown parameters; and a recommendation part 24 for selecting a product that shows the highest probability of purchase by the user, which is calculated from the coupled model using the input data 46, the prior probability 47, the gap Markov model 48, and the weight 49, and presenting it as a recommended object. <P>COPYRIGHT: (C)2009,JPO&INPIT

Description

  The present invention relates to a recommendation technology for recommending a product to a user by predicting a product to be purchased next by using a purchase history as an input, and more particularly, to a recommendation technology for presenting a product as a recommendation target in an online store or the like. .

  In general, many product providers (sellers) such as online stores that sell products or services (hereinafter simply referred to as products) recommend products so as to influence the purchasing behavior of users who use online stores. Present as (recommend). A recommendation is a direct or indirect presentation of a product to the user, with the purpose of improving convenience so that the user can quickly access information on the desired product, and the revenue of the product provider. For the purpose of increasing. Recommendations are used in many online stores.

  Conventionally, various recommendation techniques are known (see, for example, Non-Patent Document 1 and Non-Patent Document 2). For merchandise providers, it is important to predict what products a user should recommend in order for a user who has purchased merchandise at an online store or the like to purchase merchandise next time. The product that the user purchases next is considered to represent the user's current interest most. Therefore, it can be said that a method with high prediction accuracy of the user's purchase is a method with high prediction accuracy of the user's interest. However, the recommendation method described in Non-Patent Document 1 does not consider the order in which products are purchased (hereinafter referred to as order information). For this reason, prediction accuracy is low.

On the other hand, in the recommendation method described in Non-Patent Document 2, the maximum entropy model is applied in consideration of order information. Note that the maximum entropy model refers to a probability model obtained using the maximum entropy principle. In the recommendation method described in Non-Patent Document 2, only the product purchased by the user immediately before is considered. This is because it is considered that the product purchased by the user immediately before, that is, recently purchased includes a lot of information related to the user's current interest. Further, in the conventional recommendation technique considering the order information in this way, a Markov model or a maximum entropy model is applied.
Badrul Sarwar, George Karypis, Joseph Konstan, and John Reidl: Item-based co11aborative fi1tering recommendation algorithms.In Proceedings of the 10th international conference on World Wide Web, pp.285-295, New York, NY, USA, 2001.ACM Press . Xin Jin, Bamshad Mobasher, and Yanzan Zhou: A web recommendation sustem based on maximum entropy.In Proceedings of the international conference on Information Technology: Coding and Computing (ITCC'05) -Volume I, pp.213-218, Washington, DC , USA, 2005. IEEE Computer Society.

  However, in the recommendation method described in Non-Patent Document 2, information other than the product purchased by the user immediately before is not considered. That is, information on the current interest of the user, which is considered to be included to some extent in the products purchased by the user in the past, is ignored. As a result, there is a problem that prediction accuracy is low.

  In addition, the Markov model used in the conventional recommendation technique considering order information can estimate and update parameters at high speed, but has a problem of low prediction accuracy. In addition, the maximum entropy model used in the conventional recommendation technique considering order information has a problem that the prediction accuracy is high, but a large amount of calculation is required for parameter estimation and update.

  Therefore, the present invention has been made in view of the above problems, and an object thereof is to provide a recommendation technique with low calculation cost and high prediction accuracy in consideration of the purchase order.

  In order to solve the above-mentioned problem, the recommendation device according to the present invention is based on the purchase order of a plurality of users who have purchased a sales target indicating a product or a service. A recommendation device for presenting any of the individual objects belonging to the recommendation object, the purchase apparatus including purchase history information including information on one or more individual objects purchased by the user in the past, Pre-processing means for creating processing data indicating data from which purchase history is extracted, and prior probability estimation for estimating a prior probability indicating the probability that the user will purchase the individual object using the created processing data Using the means and the created processing data, when the user purchases a predetermined individual object, the individual object purchased before that is specified Gap Markov model estimation means for estimating a Gap Markov model indicating the probability of being an individual object, and a combined model indicating a model in which the estimated prior probability and the estimated gap Markov model are combined based on a maximum entropy principle. , Weight estimation means for estimating a weight indicating an unknown parameter of the constructed coupled model, the created processing data, the estimated prior probability, the estimated gap Markov model, and the estimated weight And recommending means for selecting and presenting the individual object having the highest probability of purchase by the user calculated from the combined model as a recommendation object.

  In order to solve the above-mentioned problem, the recommendation method according to the present invention is based on the purchase order of a plurality of users who have purchased a sales target indicating a product or service, and the sales method is performed for each user. A recommendation method for a recommendation device that presents one of individual objects belonging to an object as a recommendation object, using purchase history information including information on one or more individual objects purchased by the user in the past by a preprocessing unit. For each user, a preprocessing step for creating processing data indicating data obtained by extracting the purchase history of the individual object, and the user using the processing data created by the prior probability estimation means, the user Prior probability estimation step that estimates the probability of purchasing an individual object, and Gap Markov model estimation means Thus, using the created processing data, when the user purchases a predetermined individual object, a gap for estimating a gap Markov model indicating the probability that the individual object purchased before that user is a specific individual object A Markov model estimation step and a weight estimation means construct a coupled model indicating a model in which the estimated prior probability and the estimated gap Markov model are coupled by the maximum entropy principle, and an unknown parameter of the constructed coupled model is set. Using the weight estimation step for estimating the weight to be shown, and the processing data created by the recommendation means, the estimated prior probability, the estimated gap Markov model, and the estimated weight, Select the individual target that maximizes the probability of purchase by the user calculated from the combined model And having a recommendation step of presenting a recommendation-receiving Te.

  According to the recommendation device having such a configuration or the recommendation method of such a procedure, the recommendation device creates processing data for each user using the purchase history information as the first stage. Here, the purchase history information is, for example, information indicating what user has purchased what at which timing. The purchase history information can be acquired, for example, in the form of an online processing log when a product in an online store is to be sold. The processing data is data indicating what is purchased in what order for each user. Then, the recommendation device estimates the prior probability and the Gap Markov model as the second stage using the processing data. Here, the prior probability means, for example, the probability of obtaining the probability that a specific type of product was purchased by any user among all types of products sold so far, by product (by type). To do. In addition, the Gap Markov model, for example, when a user purchases a product at several purchase timings, the probability of purchasing a specific type of product several times before is calculated by product ( This means the probability obtained by type). As a result, it is possible to capture information on the current interest of the user, which is considered to be included to some extent in the products purchased by the user in the past. As the estimation method, for example, maximum posterior probability (MAP: Maximum A Posteriori) estimation can be used.

  Then, as a third stage, the recommendation device estimates a weight indicating an unknown parameter of a combined model obtained by combining the prior probability and the Gap Markov model by the maximum entropy principle. As a result, the combined model has a feature that combines a high prediction accuracy by the maximum entropy model and a low calculation cost by the Markov model. Then, as a fourth stage, the recommendation device recommends an individual object that maximizes the probability of purchase by the user calculated from the combined model, using the processing data and each parameter estimated in advance. Therefore, it is possible to accurately obtain a product that is considered to represent the interest at that point in time for a certain user with high accuracy and low cost.

  In the recommendation apparatus according to the present invention, the weight estimation unit may expect an expected combination model expressed by a product of a logarithmic likelihood of a prior distribution based on an empirical distribution and a log likelihood of the combined model and the prior distribution. The first condition indicating that the values are equal, the log likelihood of the Gap Markov model, and the expected value for the combined model represented by the product of the combined model and the log likelihood of the Gap Markov model. And constructing the combined model using the second condition shown, and maximizing the log likelihood of the purchase probability of all target individual targets from the processing data for all target users Is preferably estimated.

  In the recommendation method according to the present invention, the weight estimation step is expected for a combined model expressed by a product of a logarithmic likelihood of a prior distribution based on an empirical distribution and a log likelihood of the combined model and the prior distribution. The first condition indicating that the values are equal, the log likelihood of the Gap Markov model, and the expected value for the combined model represented by the product of the combined model and the log likelihood of the Gap Markov model. And constructing the combined model using the second condition shown, and maximizing the log likelihood of the purchase probability of all target individual targets from the processing data for all target users Is preferably estimated.

  According to the recommendation apparatus having such a configuration or the recommendation method of such a procedure, the estimated combined model can achieve higher prediction accuracy than the prediction accuracy based on the maximum entropy model considering the purchase order.

  In addition, the recommendation program according to the present invention causes a computer to execute the above-described recommendation method. By being configured in this way, a computer in which this program is installed can realize each function based on this program.

  A computer-readable recording medium according to the present invention is characterized in that the above-mentioned recommendation program is recorded. By being configured in this way, a computer equipped with this recording medium can realize each function based on a program recorded on this recording medium.

  According to the present invention, it is possible to provide a recommendation technique with low calculation cost and high prediction accuracy while considering the purchase order. As a result, it becomes possible to quickly access information on the product desired by the user, and increase the profit of the product provider.

  The best mode for carrying out the recommendation device and the recommendation method of the present invention (hereinafter referred to as “embodiment”) will be described below in detail with reference to the drawings.

  FIG. 1 is a block diagram showing a configuration of a recommendation device according to an embodiment of the present invention. The recommendation apparatus 1 is based on the purchase order of a plurality of users who have purchased a sales target (product group) indicating a product or a service, and each individual user belongs to the sales target (product group) ( Product) is presented as a recommendation target (recommended). As shown in FIG. 1, the recommendation device 1 includes a calculation means 2, an input means 3, a storage means 4, and an output means 5, and these means 2 to 5 are connected to a bus line 6. Yes.

  The computing means 2 is a main control device composed of, for example, a CPU (Central Processing Unit) and a RAM (Random Access Memory). As shown in FIG. 1, the computing unit 2 includes a preprocessing unit (preprocessing unit) 21, an extended Markov model estimation unit (extended Markov model estimation unit) 22, a weight estimation unit (weight estimation unit) 23, A recommendation unit (recommendation means) 24 and a memory 25 are included. A detailed description of each part 21 to 24 will be given later.

  The input unit 3 includes, for example, a keyboard, a mouse, a disk drive device, and the like. This input means 3 inputs, for example, a purchase history log (purchase history information) as data and stores it in the storage means 4.

  The purchase history log (purchase information) includes information on one or more individual objects (products) purchased by the user in the past. For example, as shown in Table 1, the purchase history log is a log in which a user number, a product number, and a purchase time are recorded for each purchase of a product (for each sale). In the example of Table 1, it can be seen that the user with the user number “1” has purchased the products with the product numbers “3”, “1”, and “6”.

  The storage unit 4 is composed of, for example, a general hard disk device, and stores various programs and various data used by the calculation unit 2. The storage means 4 stores a preprocessing program 41, an extended Markov model estimation program 42, a weight estimation program 43, and a recommendation program 44 as programs in the program storage unit 40a. And the calculating means 2 reads these programs 41-44 from the memory | storage means 4, expand | deploys to the memory 25, and executes them, The above-mentioned pre-processing part 21, extended Markov model estimation part 22, weight estimation part 23, Each function of the recommendation unit 24 is realized.

  In addition, the storage unit 4 stores a purchase history log 45, input data (processing data) 46, a priori probability 47, a gap Markov model 48, and a weight 49 in the data storage unit 40b. Here, the purchase history log 45 is data input from the input means 3 and is, for example, as shown in Table 1 described above. The input data 46 is data indicating the calculation processing result of the preprocessing unit 21 of the calculation means 2. The prior probability 47 and the gap Markov model 48 are data indicating the calculation processing result of the extended Markov model estimation unit 22 of the calculation means 2. The weight 49 is data indicating the calculation processing result of the weight estimation unit 23 of the calculation means 2.

  The output means 5 is, for example, a graphic board (output interface) and a monitor connected thereto. The monitor is composed of, for example, a liquid crystal display or the like, and displays a calculation processing result (for example, information on recommended products).

Next, the detail of the structure of each part of the calculating means 2 is demonstrated.
<Pre-processing section>
FIG. 2 is a functional block diagram illustrating the configuration of the preprocessing unit. The pre-processing unit 21 uses the purchase history log 45 to create input data (processing data) indicating data obtained by extracting a purchase series (purchase history) of products (individual targets) for each user. As shown in FIG. 2, a purchase history log reading unit 211 and an input data writing unit 212 are provided.

The purchase history log reading unit 211 reads information on the user, time, and product of each purchase from the purchase history log 45 and outputs the information to the input data writing unit 212.
The input data writing unit 212 calculates a purchase sequence of purchased products for each user based on the user number, the product number, and the purchase time for each purchase of the product included in the purchase history log 45. Further, the input data writing unit 212 writes the purchase series calculated for each user into the storage unit 4 (see FIG. 1) as input data (processing data) 46. The written input data 46 is used by the extended Markov model estimation unit 22, the weight estimation unit 23, and the recommendation unit 24.

  In the following, it is assumed that the user set U is defined by equation (1) and the product set S is defined by equation (2). In Expression (1), n represents a user number (also simply referred to as a user), and N represents the number of users. In Expression (2), j represents a product number (also simply referred to as a product), and V represents the number of products.

A product x _{n, k} purchased by a user n in the k-th order is included in the product set S as shown in Equation (3), and a purchase sequence _unk of the user n at that time is expressed by Equation (4). . The purchase sequence _unk shown in Expression (4) is a sequence of (k−1) items purchased before the user n purchases the k-th item x _{n, k} . This purchase sequence _unk is calculated from the purchase history log 45 by the input data writing unit 212.

  A specific example of the input data (processing data) 46 will be described with reference to Table 2. As shown in Table 2, the input data is composed of purchase series of purchased products of each user.

For example, according to the purchase history log 45 shown in Table 1, a user (n = 1) with a user number “1” purchases a product with a product number “1” following a product with a product number “3”. ing. As a result, as shown in Table 2, “x _1,1 ”, which is an element of the purchase series whose user number n is “1”, indicates the product with the product number “3”, and similarly “x _1,2 ”. Indicates the product of the product number “1”.

<Extended Markov model estimation unit>
FIG. 3 is a functional block diagram illustrating a configuration of the extended Markov model estimation unit.
As shown in FIG. 3, the extended Markov model estimation unit 22 includes an input data reading unit 221, a prior probability estimation unit 222, a gap Markov model estimation unit 223, and an extended Markov model writing unit 224.
The input data reading unit 221 reads the input data 46 and outputs the input data 46 to the prior probability estimation unit 222 and the gap Markov model estimation unit 223.

≪A priori probability estimation part≫
The prior probability estimation unit (prior probability estimation means) 222 estimates the prior probability indicating the probability that the user purchases a product (individual target) using the input data 46 created by the preprocessing unit 21 (see FIG. 1). To do.
In the present embodiment, the prior probability estimation unit 222 calculates the prior probability P ^ (i) shown in Expression (5). In this specification, the symbol “＾ (hat)” means to be written on the immediately preceding character.
According to the maximum posterior probability (MAP: Maximum A Posteriori) estimation, the prior probability P ^ (i) for purchasing the product i is estimated by the equation (5). In Expression (5), δ is a hyperparameter that plays a role of stabilizing the calculation when the number of data is small, and can be estimated by a leave-one-out cross-validation method.

  Prior probability estimation unit 222 outputs prior probability P ^ (i) estimated by prior probability estimation unit 222 to extended Markov model writing unit 224.

≪Gap Markov model estimation part≫
The gap Markov model estimation unit (gap Markov model estimation means) 223 uses the input data 46 created by the preprocessing unit 21 (see FIG. 1), and when the user purchases a predetermined product (individual target) A gap Markov model indicating the probability that a previously purchased product (individual target) is a specific product (individual target) is estimated.
In the present embodiment, the gap Markov model estimation unit 223 calculates the l gap Markov model P _l (j _l | i) shown in Expression (6). The l-gap Markov model P _l (j _l | i) represents the probability that the l-th previous product that purchased the product i is j. According to the MAP estimation, the l-gap Markov model is estimated by Equation (6). The gap Markov model estimation unit 223 outputs the estimated l-gap Markov model to the extended Markov model writing unit 224.

  The prior probabilities shown in equation (5) and the parameters in the l-gap Markov model shown in equation (6) can be calculated by simple sums. Therefore, the amount of calculation required for these estimations is small, and when new data increases, these updates can be easily performed.

  The extended Markov model writing unit 224 stores the prior probability shown in Expression (5) as the prior probability 47 in the storage unit 4 (see FIG. 1). The extended Markov model writing unit 224 stores the gap Markov model shown in the equation (6) in the storage unit 4 (see FIG. 1) as the gap Markov model 48. The stored prior probabilities 47 and gap Markov models 48 are used by the weight estimation unit 23 and the recommendation unit 24.

<Weight estimation unit>
FIG. 4 is a functional block diagram showing the configuration of the weight estimation unit. The weight estimation unit 23 constructs a coupled model indicating a model in which the prior probability 47 estimated by the extended Markov model estimating unit 22 (see FIG. 1) and the gap Markov model 48 are coupled by the maximum entropy principle, and the constructed coupled model The weight indicating the unknown parameter is estimated. This combined model is also called an extended Markov model.

As shown in FIG. 4, the weight estimation unit 23 includes an input data reading unit 231, an extended Markov model reading unit 232, a gap weight estimation unit 233, and a weight writing unit 234.
The input data reading unit 231 reads the input data 46 and outputs it to the gap weight estimation unit 233.
The extended Markov model reading unit 232 reads the prior probability 47 and the gap Markov model 48 and outputs them to the gap weight estimation unit 233.

≪Gap weight estimation part≫
The gap weight estimation unit 233 uses the input data 46, the prior probability 47, and the gap Markov model 48 to maximize the entropy under the constraints of the equations (7) and (8). The probability 47 and the gap Markov model 48 are combined according to the maximum entropy principle to construct a combined model shown in Expression (9), and the weight is estimated. In the following, it is assumed that the logarithm is a natural logarithm, that is, the base of the logarithm log is “e”. Further, in the equation (9), let j _l be the product purchased ₁ item before purchasing the product i. L represents the number of products purchased before the k-th product is purchased.

  The left side of Expression (7) is “log likelihood of prior distribution based on experience distribution”. The right side of Expression (7) indicates a product of “model P (probability)” and “log likelihood of prior distribution” (this corresponds to an expected value for model P). Then, assuming that the left side of Expression (7) is equal to the right side of Expression (7) (first condition) means “constraint”.

  The left side of Equation (8) is “log likelihood of Gap Markov model”. In addition, the right side of the equation (8) represents a product of “model P (probability)” and “log likelihood of Gap Markov model” (this corresponds to an expected value for model P). . Then, assuming that the left side of Expression (8) is equal to the right side of Expression (8) (second condition) means “constraint”.

  In this case, the combined model shown in Equation (9) can be developed as shown in Equation (10). In Expression (10), Z is a normalization term represented by Expression (11), and α is an unknown parameter (hereinafter also referred to as weight) represented by Expression (12). In the present specification, when subscript is added to α, it indicates an individual parameter, and when α is not subscripted, it indicates a set of L parameters.

  For the unknown parameter α, a global optimal solution can be obtained by maximizing the log likelihood J shown in Equation (13) using an optimization method such as a quasi-Newton method.

The log likelihood J shown in the equation (13) is the purchase series u _nk for all target users, that is, all target products (all individual targets) x _n, obtained from input data (processing data) _. Indicates the log likelihood of the purchase probability of _k . Therefore, the gap weight estimation unit 233 estimates the weight α by maximizing the log likelihood J shown in Expression (13).

  In the present embodiment, the gap weight estimation unit 233 uses a normal distribution with an average of 0 as the prior distribution of the unknown parameter α in order to suppress overlearning. Note that the phenomenon in which the generalization error for data not used for learning becomes large is called overlearning. Here, if the learning data used for the estimation of the prior probabilities and the gap Markov model by the extended Markov model estimation unit 22 among the predetermined learning data is used for the estimation of the unknown parameter α, there is a possibility of overlearning. . Therefore, the unknown parameter α is estimated by cross-validation. That is, the weight α is estimated by dividing predetermined learning data and maximizing the log likelihood of the data that was not used for the estimation of the prior probability and the Gap Markov model using an optimization method such as the quasi-Newton method. To do.

  The weight writing unit 234 stores the weight α estimated by the gap weight estimation unit 233 as the weight 49 in the storage unit 4 (see FIG. 1). The stored weight 49 is used by the recommendation unit 24.

<Recommendation>
FIG. 5 is a functional block diagram showing the configuration of the recommendation unit.
The recommendation unit 24 uses the input data (processing data) 46, the estimated prior probability 47, the estimated gap Markov model 48, and the estimated weight 49 from the combined model (extended Markov model). A product (individual target) having the maximum probability of purchase of the user to be calculated is selected and presented as a recommendation target.

  As shown in FIG. 5, the recommendation unit 24 includes an input data reading unit 241, an extended Markov model reading unit 242, a weight reading unit 243, a maximum product selection unit 244, and a recommendation output unit 245.

The input data reading unit 241 reads the input data 46 and outputs it to the maximum product selection unit 244.
The extended Markov model reading unit 242 reads the prior probability 47 and the gap Markov model 48 and outputs them to the maximum product selection unit 244.
The weight reading unit 243 reads the weight 49 and outputs it to the maximum product selection unit 244.

The maximum product selection unit 244 executes the calculation shown in Expression (14). Here, the purchase history u _n users n and equation (15). K _n is the number of products purchased by user n.

を選択する。 In the present embodiment, the maximum product selection unit 244 selects a product having the highest probability of purchase by the user n calculated from Expression (14). In other words, the maximum product selection unit 244 selects a product (product number) having the maximum probability represented by the formula (14) from the product set S (product number 1 ≦ i ≦ V) of products purchased by the user u.

Select.

  The recommendation output unit 245 outputs the product number selected by the maximum product selection unit 244 to present the product with the product number as a recommendation target. This recommendation target is output to the output means 5.

[Recommendation unit operation]
The operation of the recommendation device 1 shown in FIG. 1 will be described with reference to FIG. 6 (see FIG. 1 as appropriate). FIG. 6 is a flowchart showing the operation of the recommendation device. The recommendation device 1 uses the purchase history log 45 by the preprocessing unit 21 to generate input data (step S1: preprocessing step). And the recommendation apparatus 1 performs an extended Markov model estimation process by the extended Markov model estimation part 22 (step S2: extended Markov model estimation step). Then, the recommendation apparatus 1 performs a weight estimation process by using the prior probability 47 and the gap Markov model 48 estimated in step S2 by the weight estimation unit 23 (step S3: weight estimation step). The recommended device 1, the recommendation unit 24, the probability of purchase of the user is calculated from binding model (extended Markov model) is recommended to select a product (individual subject) as the maximum (Step S 4: recommendation step ).

  Next, the extended Markov model estimation process in step S2 and the weight estimation process in step S3 will be described with reference to FIGS. 7 and 8, respectively. FIG. 7 is a flowchart showing the extended Markov model estimation process, and FIG. 8 is a flowchart showing the weight estimation process.

First, in the extended Markov model estimation process in step S2, as shown in FIG.
The extended Markov model estimation unit 22 reads the input data 46 from the storage unit 4 (see FIG. 1) by the input data reading unit 221 (step S21). Then, the extended Markov model estimation unit 22 estimates the prior probability by the prior probability estimation unit 222 (step S22), and the extended Markov model estimation unit 22 estimates the gap Markov model by the gap Markov model estimation unit 223 ( Step S23). Then, the extended Markov model estimation unit 22 stores the estimated prior probability and the gap Markov model in the storage unit 4 (see FIG. 1) by the extended Markov model writing unit 224 (step S24). Note that the execution order of the process of step S22 and the process of step S23 is arbitrary, and the processes may be executed in parallel.

  Next, in the weight estimation process of step S3 described above, as shown in FIG. 8, the weight estimation unit 23 reads the input data 46 from the storage means 4 (see FIG. 1) by the input data reading unit 231 (step S3). S31). Further, the weight estimation unit 23 reads the prior probability 47 and the gap Markov model 48 from the storage unit 4 (see FIG. 1) by the extended Markov model reading unit 232 (step S32). Subsequently, the weight estimation unit 23 uses the gap weight estimation unit 233 to estimate the unknown parameter α of the combined model using the input data 46, the prior probability 47, and the gap Markov model 48 (step S33). Then, the weight estimation unit 23 stores the parameter α estimated by the weight writing unit 234 in the storage unit 4 (see FIG. 1) as the weight 49 (step S34). Note that the execution order of the process of step S31 and the process of step S32 is arbitrary, and the processes may be executed in parallel.

  The recommendation device 1 can also be realized by executing a recommendation program that causes a general computer to execute the above steps. This program can be distributed via a communication line, or can be written on a recording medium such as a CD-ROM for distribution.

  According to the present embodiment, it is possible to recommend a product having a low calculation cost and a high prediction accuracy to the user in consideration of the purchase order. As a result, it becomes possible to quickly access information on the product desired by the user, and increase the profit of the product provider.

  As mentioned above, although embodiment of this invention was described, this invention is not limited to this, It can implement in the range which does not change the meaning. For example, the number of devices constituting the recommendation device 1 is not limited to one, and the functions may be distributed to a plurality of devices. For example, the preprocessing unit 21, the extended Markov model estimation unit 22, the weight estimation unit 23, the recommendation unit 24, and the data storage unit 40b of the storage unit 4 may be configured as separate devices. As a result, the load on each device is distributed, and high-speed processing can be realized.

  In order to confirm the effect of the present invention, when the purchase history log of the music distribution service is input to the recommendation device 1 according to the present embodiment and the purchase history log of the video distribution service is input. The prediction accuracy of the product was obtained.

<Setting>
The purchase history log of the music distribution service (hereinafter referred to as music data) is a log indicating the purchase history of the music distribution service from April 1, 2005 to June 30, 2005. In this music data, the number of users was “2,104”, the number of products (number of songs) was “561”, and the number of purchases was “15,216”.
The purchase history log of the moving image distribution service (hereinafter referred to as moving image data) is a log indicating the purchase history of the moving image distribution service on January 1, 2007. In this moving image data, the number of users was “3,085”, the number of products was “1,569”, and the number of purchases was “25,363”.

  Note that, from music data and moving image data, products whose sales number is less than “10” are omitted, and users whose purchase number is less than “5” are omitted. Further, when a user purchases the same product twice or more, the second and subsequent purchases regarding the product are omitted from the purchase history. In addition, the product purchased last by each user is used as test data, and the previous purchase history is used as learning data. Here, when the product purchased last by the user is not included in the learning data, the product is omitted from the test data.

The Example (Our Method) was compared with the following six models (Comparative Examples 1 to 6).
Comparative Example 1: 1st order Markov model (1stMarkov)
Comparative Example 2: Second-order Markov model (2ndMarkov)
Comparative Example 3: Third-order Markov model (3rdMarkov)
Comparative example 4: Gap Markov model assuming that each is independent (GapMarkov)
Comparative Example 5: Maximum entropy model considering purchase order (MaxEnt (seq))
Comparative Example 6: Maximum entropy model (MaxEnt) without considering the purchase order

Here, the prior probability and the hyperparameter in the Gap Markov model were obtained by the leave-one-out cross-validation method. That is, in the recommendation device 1 of the present embodiment, the hyper parameter “δ” in the above equation (5) and the hyper parameter “δ” in the equation (6) are obtained by the leave-one-out cross-validation method.
The parameter prior distribution in the maximum entropy model is a normal distribution with a variance of “1”. That is, in the recommendation device 1 of the present embodiment, the prior distribution of the unknown parameter (weight) α in the above-described equation (12) is a normal distribution with a variance of “1”.
In the recommendation device 1 of the present embodiment, the weight α is obtained by a 10-fold cross validation method.

<Result (correct answer rate)>
Table 3 shows the experimental results (correct answer rate) of each method at this time.

  In Comparative Example 4 (GapMarkov), Comparative Example 5 (MaxEnt (seq)), and Example (Our Method), an experiment was performed using a method (l = 1,..., 10) using the purchase history up to the previous one. The value when the correct answer rate is obtained is displayed, and l at that time is displayed in parentheses. That is, in Table 3, for example, in the case of the Example (Our Method), music data has the best correct answer rate when l = 8, and video data has the best correct answer rate when l = 9. Show.

  As shown in Table 3, the correct answer rate of the Example (Our Method) was the highest in both music data and moving image data. The reason why the correct answer rate of Comparative Example 4 (GapMarkov) is lower than the correct answer rate of Example (Our Method) is considered to be because the assumption that “the Gap Markov model is independent” is not appropriate. .

  Further, as shown in Table 3, in Comparative Example 3 (3rdMarkov), the correct answer rate is lower in all data sets than in Comparative Example 1 (1stMarkov) and Comparative Example 2 (2ndMarkov). This is thought to be because the number of parameters increases compared to the number of data at higher orders, and robust estimation cannot be performed.

  Further, when Comparative Example 5 (MaxEnt (seq)) and Comparative Example 6 (MaxEnt) are compared, Comparative Example 5 (MaxEnt (seq)) is correct in comparison with Comparative Example 6 (MaxEnt) in all data sets. The rate is high. This suggests that considering the purchase order is important for increasing the correct answer rate.

<Relationship between weight α and gap l>
FIG. 9 shows the relationship between the weight α estimated by the recommendation device 1 in this embodiment and the gap l. In FIG. 9, music indicates music data, and movie indicates moving image data. Α _l (l = 1 to 10) indicates the weight of the l-gap Markov model, and α _l (l = 0) indicates the weight of the prior probability. As shown in the graph of FIG. 9, the weight of the gap Markov model with a small gap is large in all the data sets. This is consistent with the intuition that recent history gives great information about purchase forecasts.

<Accuracy rate using weight α estimated from data up to d days ago>
For music data, FIG. 10 shows the correct answer rate when only the prior probability and the Gap Markov model are updated using the weight α estimated from data up to d days ago. Here, the prior probability and the hyperparameter “δ” in the Gap Markov model were also estimated using data up to d days ago. In addition, the vertical axis | shaft of FIG. 10 is a correct answer rate (accuracy), and a unit is%.

  As shown in FIG. 10, the example (Our Method) has a higher accuracy (accuracy) than Comparative Example 6 (MaxEnt), Comparative Example 4 (GapMarkov) and Comparative Example 1 (1stMarkov). Further, in the example (Our Method), the accuracy rate (accuracy) varies depending on how many days of data are used. Therefore, the Example (Our Method) has a case where the correct answer rate is higher than that of Comparative Example 5 (MaxEnt (seq)) and is lower than that of Comparative Example 5; It can be said that it is performance. In the example (Our Method), when the weight estimated using data up to 30 days ago is used as past data, the correct answer rate is higher than the correct answer rate of Comparative Example 5 (MaxEnt (seq)). About 1% higher.

  From these results, the following can be understood. That is, when new data is added to the purchase history log 45 shown in FIG. 1, that is, when input data (processing data) 46 is added, the prior probability 47, the Gap Markov model 48, and the weight 49 are respectively Need to update. Of these, the weight 49 requires a larger amount of calculation for updating the parameters than the prior probability 47 and the gap Markov model 48. Therefore, even if the weight α is updated at a rate of about once a month and the prior probability and the Gap Markov model are updated at shorter intervals, the same as when the weight α is updated frequently. High prediction accuracy can be realized. Therefore, by updating the weight α at a rate of about once a month, it is possible to effectively suppress the calculation cost of the long span.

It is a block diagram which shows the structure of the recommendation apparatus which concerns on embodiment of this invention. It is a functional block diagram which shows the structure of a pre-processing part. It is a functional block diagram which shows the structure of an extended Markov model estimation part. It is a functional block diagram which shows the structure of a weight estimation part. It is a functional block diagram which shows the structure of a recommendation part. It is a flowchart which shows operation | movement of a recommendation apparatus. It is a flowchart which shows an extended Markov model estimation process. It is a flowchart which shows a weight estimation process. It is a graph which shows the weight estimated using the purchase log | history up to 1 piece ago as a gap. It is a graph which shows the correct answer rate in music data when using the weight estimated by the data until d days ago.

Explanation of symbols

DESCRIPTION OF SYMBOLS 1 Recommendation apparatus 2 Calculation means 3 Input means 4 Memory | storage means 5 Output means 6 Bus line 21 Pre-processing part (pre-processing means)
22 extended Markov model estimation unit 23 weight estimation unit (weight estimation means)
24 recommendation section (recommendation means)
25 memory 40a program storage unit 41 preprocessing program 42 extended Markov model estimation program 43 weight estimation program 44 recommendation program 40b data storage unit 45 purchase history log 46 input data 47 prior probability 48 gap Markov model 49 weight 211 purchase history log reading unit 212 Input data writing unit 221 Input data reading unit 222 Prior probability estimation unit (prior probability estimation means)
223 Gap Markov model estimation unit (gap Markov model estimation means)
224 Gap Markov Model Writing Unit 231 Input Data Reading Unit 232 Extended Markov Model Reading Unit 233 Gap Weight Estimation Unit 234 Weight Writing Unit 241 Input Data Reading Unit 242 Extended Markov Model Reading Unit 243 Weight Reading Unit 244 Maximum Product Selection Unit 245 Recommendation Output section

Claims (6)

A recommendation device that presents, as a recommendation target, one of the individual targets belonging to the sales target to each user based on the purchase order of a plurality of users who have purchased the sales target indicating a product or service. And
Preprocessing means for creating processing data indicating data obtained by extracting the purchase history of the individual object for each user using purchase history information including information on one or more individual objects purchased by the user in the past; ,
A prior probability estimating means for estimating a prior probability indicating a probability that the user purchases the individual object using the generated processing data;
Gap Markov model estimation that uses the created processing data to estimate a Gap Markov model indicating the probability that an individual object purchased before the user purchases a predetermined individual object is a specific individual object Means,
A weight estimation means for constructing a combined model indicating a model obtained by combining the estimated prior probability and the estimated gap Markov model by a maximum entropy principle, and estimating a weight indicating an unknown parameter of the combined model;
Using the generated processing data, the estimated prior probability, the estimated gap Markov model, and the estimated weight, the probability of purchase by the user calculated from the combined model is the maximum. Recommending means for selecting the individual object to be presented as a recommendation object;
A recommendation device comprising: The weight estimation means includes
A first condition indicating that a logarithmic likelihood of a prior distribution based on an empirical distribution and an expected value for a combined model expressed by a product of the combined model and the log likelihood of the prior distribution are equal;
Using the logarithmic likelihood of the Gap Markov model and the second condition indicating that an expected value of the coupled model represented by a product of the coupled model and the log likelihood of the Gap Markov model is equal. Build
From the processing data for all target users, the weight is estimated by maximizing the log likelihood of the purchase probability of all target individual targets.
The recommendation device according to claim 1. Recommendation of a recommendation device that presents, as a recommendation target, one of the individual objects belonging to the sales target to each user based on the purchase order of a plurality of users who have purchased the sales target indicating goods or services A method,
Preprocessing means creates processing data indicating data obtained by extracting the purchase history of the individual object for each user, using purchase history information including information on one or more individual objects purchased by the user in the past. Preprocessing steps to
A prior probability estimating step of estimating a prior probability indicating a probability that the user purchases the individual object by using the created processing data by a prior probability estimating unit;
Gap Markov model indicating the probability that an individual object purchased before the user purchases a predetermined individual object by the gap Markov model estimation means using the generated processing data is a specific individual object Gap Markov model estimation step for estimating
A weight for estimating a weight indicating an unknown parameter of the constructed coupled model by constructing a coupled model indicating a model obtained by combining the estimated prior probability and the estimated gap Markov model by the maximum entropy principle by weight estimation means An estimation step;
User purchase calculated from the combined model using the created processing data, the estimated prior probability, the estimated gap Markov model, and the estimated weight by a recommendation means A recommendation step of selecting the individual object with the highest probability of being presented and presenting it as a recommendation object;
A recommending method characterized by comprising: The weight estimation step includes:
A first condition indicating that a logarithmic likelihood of a prior distribution based on an empirical distribution and an expected value for a combined model expressed by a product of the combined model and the log likelihood of the prior distribution are equal;
Using the logarithmic likelihood of the Gap Markov model and the second condition indicating that an expected value of the coupled model represented by a product of the coupled model and the log likelihood of the Gap Markov model is equal. Build
From the processing data for all target users, the weight is estimated by maximizing the log likelihood of the purchase probability of all target individual targets.
The recommendation method according to claim 3.   A recommendation program for causing a computer to execute the recommendation method according to claim 3.   6. A computer-readable recording medium on which the recommendation program according to claim 5 is recorded.

Images