JP6386931B2 - Multidimensional data prediction apparatus, multidimensional data prediction method, multidimensional data prediction program - Google Patents

Description

  The present invention belongs to a technical field that handles prediction of multidimensional data with improved accuracy of IRM (Infinite Relational Model) in consideration of Semantics.

  On the Web and NW (network), systemized dictionaries such as “WikiPedia (registered trademark)” have become widespread as user requests for reference to the meaning and concept of objects increase.

  In order to allow such a user's request to be processed by a service on behalf of a person instead of a human and customized and presented to the user, a concept reference API (Application Programming Interface) that can be machine-processed is widely used. For example, various information providers such as “DBpedia”, “WorldNet”, “FreeBase”, “GeoNames”, “Open Street Map (OSM)” systematize and present them at low cost or free through API. ("Linked Open Data Project" in Non-Patent Document 1).

  On the other hand, a recommendation system that guesses a concept of interest of a user and collects and presents information on behalf of the user is also required and studied. In particular, a product recommendation method based on a method of decomposing a two-dimensional matrix between a product and a user is becoming widespread, and for example, application to a field such as prediction of a score given to a product by a user and practical use have been performed.

  Also, as represented by “Google (registered trademark) Now” of Non-Patent Document 2, a method for predicting a visit location by a method of decomposing a two-dimensional matrix of the user and the visit location is becoming widespread. Application to the field of predicting whether or not to visit a place and its practical application have been made. If the concept to which the product belongs can be applied to research on such a recommendation method, there is a possibility that the user's interest can be estimated in more detail and in a wide range.

  For example, based on the tags that users give to products, multi-dimensional data is created based on the relationship “user, tag, product” and the value “score” that indicates the relationship. Research has been conducted to predict whether or not to purchase products that have not been purchased in the future (see Non-Patent Document 3). The IRM of Non-Patent Document 3 performs binary prediction that values that can be taken by multidimensional data are “0” or “1” while clustering multidimensional data.

  However, in multidimensional data, although the number of relationships that can be taken between data crossing each dimension is very large, the number of observed data is small, and in this case, the analysis results are adversely affected.

  The problem in the case where the observation becomes dilute with respect to the possibility of the observation is called a sparse problem. Non-Patent Document 5 solves the sparse problem by using the semantics that is the background of multidimensional data in tensor decomposition.

“Linked Data-Connect Distributed Data across the web” [online], [searched January 23, 2015], Internet <URL http://lindeddata.org/> “What you can do with Google Google Now” [online], [Search January 26, 2015], Internet <URL http://www.google.co.jp/dekiru/android/tips/android_search_tip23.html> Osamu Ueda, Takeshi Yamada “Non-parametric Bayes model” [online], [searched January 26, 2015], Internet <URL {HYPERLINK "http://www.kecl.ntt.co.jp/as/members/yamada /dam_ueda_yamada2007.pdf ", http: //www.kecl.ntt.co.jp/as/members/yamada/dam_ueda_yamada2007.pdf}> Charles Kemp, Joshua B. Tenenbaum, Thomas L. Griffiths, Takeshi Yamada, Naonori Ueda “Learning Systems of Concepts with an Infinite Relational Model”, AAAI2006 Makoto Nakatsuji, Yasuhiro Fujiwara, Hiroyuki Toda, Hiroshi Sawada, Jin Zheng, James A. Hendler “Semantic Data Representation for Improving Tensor Factorization” [online], [Search January 26, 2015], Internet <URL http: // www .aaai.org / ocs / index.php / AAAI / AAAI14 / paper / viewFile / 8372/8842

  However, the methods of Non-Patent Documents 4 and 5 cannot sufficiently cope with binary prediction such as whether to buy, whether to visit, whether or not to go.

  That is, the methods of Non-Patent Documents 4 and 5 assume that the prior distribution of observation data is a Gaussian distribution, and do not assume a Bernoulli distribution suitable for binary prediction. Therefore, it is difficult to use for binary prediction, and accuracy may deteriorate even if it is used for binary prediction.

  The present invention is made to solve such a conventional problem, and an object of the present invention is to improve the accuracy of binary prediction in observation data showing a multidimensional relationship.

  The multidimensional data prediction apparatus according to the present invention receives observation data indicating a multidimensional relationship and a taxonomy having a class hierarchical structure as background knowledge of each dimension, and is sparsely observed in each dimension based on the taxonomy. Observation data expansion unit that expands the observation data by adding class knowledge to the object, observation data before expansion by the observation data expansion unit, and observation data after the expansion are analyzed simultaneously A missing value prediction unit that performs binary prediction on the data.

  The method for predicting multidimensional data according to the present invention receives input of observation data indicating a multidimensional relationship and a taxonomy having a class hierarchy structure as background knowledge of each dimension, and sparsely observes in each dimension based on the taxonomy. The observation data expansion step for extending the observation data by adding class knowledge to the object to be processed, the observation data before the expansion by the observation data expansion step, and the observation data after the expansion are not analyzed simultaneously. And a missing value prediction step for performing binary prediction on the observation data.

  In addition, this invention is good also as an aspect of the program which makes a computer function as said prediction apparatus. This program can be provided through a network or a recording medium.

  ADVANTAGE OF THE INVENTION According to this invention, the precision of the binary prediction in the observation data which shows a multidimensional relationship can be improved.

The block diagram of the prediction apparatus of the multidimensional data which concerns on embodiment of this invention. The figure which shows the example of application to simultaneous space information.

≪Basic idea≫
As is well known, various events are represented by the relationship between several things. For example, if there are two types of objects, data can be represented by a matrix as a two-dimensional array, but if more objects are involved at the same time, it can be represented in the form of a high-dimensional array, that is, a tensor. .

  At this time, it is not uncommon for the observation data to be deficient because of the large error or the fact that only part of the data can be observed due to the cost of the experiment. This not only causes the above-mentioned dilution problem, but the observation data in which the defect has occurred is not suitable for analysis as it is, and in many cases cannot be used satisfactorily and is wasted as it is.

  If unknown observation data missing in such a case can be estimated, only part of the observation data can be observed from the beginning to reduce costs and labor. In addition, since the number of combinations is enormous, even if comprehensive observation is difficult in the first place, it may be possible to capture the whole picture from some observations.

  For this purpose, a technique for complementing tensors is important, and this technique can also be applied to user purchase prediction and user behavior prediction. Therefore, the present invention supplements unknown observation data in IRM widely used for binary prediction, and predicts binary (“0” or “1”) of future multidimensional data.

  Explaining the basic concept of the present invention, for example, “User A, Rock / Classic, Beatles” and “User B, Rock / Guitar, Eric Clapton” have different child genres, Large genres are equal.

  For this reason, the two are considered to have a close relationship with the genre “rock” connection, and not only the terminal class but also the relationship born from the higher class can be handled on the multidimensional data to improve the accuracy of the analysis.

≪Example of binary prediction device configuration≫
Based on FIG. 1, the structural example of the prediction apparatus of the multidimensional data which concerns on embodiment of this invention is demonstrated. The prediction device 1 can be used in a field of information recommendation for recommending products based on emphasis filtering, a field of user behavior prediction such as prediction of a visit destination at a user's destination, and the like.

  Specifically, the prediction device 1 is configured by a computer, and includes hardware leases such as a CPU, a main storage device (RAM, ROM, etc.), an auxiliary storage device (hard disk drive device, solid state drive device, etc.). As a result of the cooperation between the hardware resource and the software resource (OS, application, etc.), the binary prediction device 1 implements the observation data extension unit 2 and the missing value prediction unit 3.

  This observation data expansion unit 2 adds, for example, a sparse object v to a class c (superordinate concept) in addition to the multidimensional relationship (u, v, t) of “user u”, “object v”, “time t”. Lift and build an augmented multidimensional relationship (u, c, t).

  The missing value prediction unit 3 applies the technique of Non-Patent Document 3 to solve the sparse problem. That is, if it is not a sparse object, the formula (5.6) described in P14 of Non-Patent Document 3 is used. On the other hand, if the object is a sparse object, a missing value is predicted using an increased multidimensional relationship, and a future multidimensional relationship is predicted at this point.

≪Observation data expansion part 2≫
The observation data extension unit 2 receives observation data D1 indicating a multidimensional relationship and a taxonomy D2 having a class hierarchy structure as background knowledge of each dimension. The observation data extension unit 2 receives the input observation data D1 and taxonomy D2, and gives the class knowledge of the taxonomy D2 to the object of the observation data D1 observed sparsely in each dimension, thereby extending the observation data. Can do.

  At this time, among the objects in the observation data D1, the taxonomy D2 is referred to replace a sparse object with the belonging class of the object, the replaced belonging class is added to the object of the observation data D1, and the data D3 of the increased multidimensional relationship Build up. The constructed data D3 is output to the missing value prediction unit 3 together with the observation data D1. Hereinafter, the processing content of the observation data extension part 2 is demonstrated.

(1) Definition of terms First, terms used for the processing of the observation data expansion unit 2 will be described. Here, a three-dimensional relationship among “user u _i ”, “visit place v _j ”, and “time zone t _k ” is used as an example of the relationship between a plurality of objects in the observation data D1.

  This three-dimensional relationship is expressed as “Equation (1)” in “calligraphic letter”. A row example of this three-dimensional relationship is expressed as “bold capital letters” as in equation (2), and a vector is expressed as “bold lowercase letters, eg” as in equation (3).

  The three-dimensional relationship of Expression (1) is constructed from the relationship between “U”, “V”, and “T”, and the user set of Expression (4), the visited place set of Expression (5), and Expression (6) ) Of the time set.

  The (i, j, k) element is written as in equation (7). Here, a score with the kth time zone is stored for the jth place visited by the ith user. Further, the development related to the time zone k of the three-dimensional relationship is expressed as in Expression (8).

(2) Content of processing The conventional IRA calculates the predicted distribution of unobserved scores from only the observed evaluation values. At this time, if it is useful for the sparse problem, a model using auxiliary information obtained from the taxonomy of the object is desirable.

  Therefore, the observation data expansion unit 2 applies the knowledge (Non-Patent Document 5) that it is useful for the sparse problem to use the item taxonomy in research on tensor decomposition. At this time, among the objects observed in the three-dimensional relationship of the expression (1) related to the original observation data D1, the object is replaced with the class to which the object belongs. For the replacement here, the input taxonomy D2 is used.

That is, if observation of a certain object (eg, visited place) v _j is sparse, the visited place is lifted to the belonging class c _l and added to the three-dimensional relationship composed of (u _i , v _j , t _k ). Then, (u _i , c _l , t _k ) is added to the three-dimensional relationship of equation (1) to construct the increased multidimensional relationship of equation (9).

An example will be described based on the observation data D1 and the taxonomy D2 in FIG. 1 (in the observation data D1 in FIG. 1, the time zone t _k is omitted). Here, it is assumed that “restaurant A” and “movie theater D” are rarely observed in the observation data D1.

In this case, referring to the taxonomy D2, the superordinate concept “Chinese Chinese” of “Restaurant A” is lifted to the “visited place v _j ” of the user 1, and the superordinate concept “theatre” of “Cinema D” is raised to the “visiting place of the user 3” Lift up to v _j ". As a result, the visit destination candidate data D3 obtained by adding “user 1, Chinese” and “user 3, theater” to the original observation data D1 is constructed as an increased multidimensional relationship of Expression (9).

The details of the method for constructing this increased multidimensional relationship will be described. First, a sparse set of objects shown in Expression (10) is defined. This shows a set of objects v _s that are observed relatively sparse among all items.

The element “o _{m, n ′, k ′} ” of the multidimensional relationship O is a multi-object relationship constituted by the user “u _m , visited place v _n , time zone t _k ” in the multidimensional relationship of Expression (11). When the observation exists, it has “1” as an element, and when the observation does not exist, it has “0” as an element. Then, a sparse set of objects shown in Expression (10) is calculated by Expression (12).

  Here, “δ” indicates a parameter used to determine the number of sparse objects in Equation (10), and is generally set to “0.1 to 0.3”. The affiliation class of a sparse object is expressed as equation (13), and the affiliation class of the sparse object is expressed as equation (14).

  Next, the processing of the observation data expansion unit 2 (SIRM: Semantic IRM) is a three-dimensional relationship of the formula (1) that is a relationship between a plurality of objects composed of “user”, “class belonging to a sparsely visited place”, and “time zone”. Is inserted into the increased multidimensional relationship of equation (9) as shown in equation (15).

≪Missing value prediction part 3≫
The missing value prediction unit 3 receives the observation data D1 together with the data D3, executes a process that improves a part of the non-patent document 3, and the value that the multidimensional data can take is “ Binary prediction of “0” or “1” is performed. Here, the processing content improved mainly by the missing value prediction unit 3 will be described.

  That is, P15 of Non-Patent Document 3 describes the outline of Gibbs sampling, that is, five processing steps. The processing content of the missing value prediction unit 3 improves the new cluster allocation in the fourth step. This will be described below.

(A) Processing contents of non-sparse objects For non-sparse objects, the original multidimensional relationship in the observation data D1 is used in the calculation of the equation (5.6) of Non-Patent Document 3 corresponding to the cluster assignment.

Specifically, “m (k ^* , l)” is a cluster based on the cluster calculated using the equation (5.1) of Non-Patent Document 3 (see P13) for the original multidimensional relationship. Calculate the number of links between k and cluster l.

(B) Processing contents of sparse object For a sparse object, the above equation (5.6) of Non-Patent Document 3 corresponding to the cluster allocation is used for the increased multidimensional relationship of equation (9).

Specifically, “m (k ^* , l)” uses a cluster calculated using the equation (5.1) of Non-Patent Document 3 with respect to the original multidimensional relationship and links between the clusters. The following improvements were made when calculating numbers:

That is, when the object belonging to the cluster is a sparse object, the parent class of the object is used, the relationship with the parent class is also measured, and the number of links is calculated. For example, if “k” is the user class, “l” is the item cluster, and “c” indicates the parent class of the sparse object of Expression (16), “m (k ^* , l)” is expressed by Expression (17). ).

By repeatedly executing the processes (A) and (B), the number of links between the clusters “k ^* ” and “l” uses the parent class of the object for a sparse object. , More than using the original multidimensional relationship, which can solve the sparse problem.

  For example, in FIG. 1, since “Restaurant A” and “Movie Theater D” are sparsely observed, the number of links is calculated using the parent classes “Chinese Chinese” and “Vietnam” included in the candidate site D2. The As a result, the visit destination candidate data D4 including “user 1, movie theater, Roppongi”, “user 1, museum, Roppongi”, “user 1, convenience store, Roppongi”, and the like are output.

  Therefore, according to the prediction apparatus 1, the background knowledge of the class is utilized to improve the accuracy of binary prediction for multi-dimensional missing values. This point is particularly useful for prediction of data expressed in binary, such as prediction of user purchases and prediction of user visits. Furthermore, many applications such as user navigation can be promoted from marketing, and it can be expected to be used in the future industry.

For non-sparse objects, the number of links between clusters “k ^* ” and “l” does not take into account the parent class and therefore does not include class bias, and noise can be prevented in this respect.

≪Example of application to spatio-temporal information≫
In binary prediction, “0” represents “nagative” and “1” represents “positive”.

  On the other hand, in the spatiotemporal information, “0” is not necessarily “negative” and is often not known. Here, the binary data retention characteristic in the prediction apparatus 1 will be described. As shown in FIG. 2, the map data is displayed in a grid, and first the user's action range is taken in detail.

  In addition, the place that has been visited in the action range is “1”, and the place that has not been taken is considered “negative” to indicate that the place has not been taken regardless of the narrow action range, and is set to “0”.

  Then, binary data outside this range of action is predicted. In this way, the effectiveness of using semantics is recognized for predicting using the observation data of the user's range of action (location known by the user) for the range of activity that the user does not go (location that the user does not know). It is done. This is because the user is considered to go to a facility that is semantically close even if the user does not know the place.

  The present invention can also be configured as a binary prediction program that causes a computer to function as part or all of the units 2 and 3 of the binary prediction device 1. This program can be provided through a network such as a website or e-mail.

  The program is stored in a recording medium such as a CD-ROM, DVD-ROM, CD-R, CD-RW, DVD-R, DVD-RW, MO, HDD, BD-ROM, BD-R, or BD-RE. It is also possible to record, save and distribute. This recording medium is read using a recording medium driving device, and the program code itself realizes the processing of the above embodiment, so that the recording medium also constitutes the present invention.

DESCRIPTION OF SYMBOLS 1 ... Binary prediction apparatus 2 ... Observation data expansion part 3 ... Missing value prediction part

Claims (7)

Observation data indicating multi-dimensional relationships and taxonomies of class hierarchy as background knowledge of each dimension are input, and the observation is performed by giving class knowledge to objects that are sparsely observed in each dimension based on the taxonomy An observation data extension for extending the data;
A missing value prediction unit that performs binary prediction on unobserved data by simultaneously analyzing the observation data before expansion by the observation data expansion unit and the observation data after the expansion;
An apparatus for predicting multidimensional data, comprising: The observation data extension unit replaces a sparse object among the objects in the observation data with the affiliation class of the sparse object,
The multidimensional data prediction apparatus according to claim 1, wherein an increased multidimensional relationship is constructed by adding the replaced affiliation class to the object of the observation data. The missing value prediction unit calculates an expression corresponding to cluster assignment for a non-sparse object using the original multidimensional relationship,
The multidimensional data prediction apparatus according to claim 2, wherein an expression corresponding to a cluster assignment for a sparse object is calculated using the increased multidimensional relationship. A method for predicting observation data showing a multidimensional relationship by a computer comprising an observation data extension unit and a missing value prediction unit ,
The observation data extension unit receives input of the observation data and a taxonomy having a class hierarchy structure as background knowledge of each dimension, and gives class knowledge to an object observed sparsely in each dimension based on the taxonomy. An observation data expansion step of extending the observation data with
The missing value prediction unit performs a binary prediction on unobserved data by simultaneously analyzing the observation data before expansion by the observation data expansion step and the observation data after the expansion,
A method for predicting multidimensional data, comprising:
The observation data expansion step replaces a sparse object among the objects in the observation data with a belonging class of the sparse object;
Building an augmented multidimensional relationship by adding the replaced affiliation class to the object of the observation data;
The multidimensional data prediction method according to claim 4, further comprising: The missing value prediction step calculates an equation corresponding to a cluster assignment for a non-sparse object using the original multidimensional relationship;
Calculating an expression corresponding to a cluster assignment for a sparse object using the augmented multidimensional relationship;
The multidimensional data prediction method according to claim 5, wherein:   A multidimensional data prediction program that causes a computer to function as the multidimensional data prediction apparatus according to any one of claims 1 to 3.

Images