JP5981382B2 - Partial tree merging device, partial tree merging method, and partial tree merging program - Google Patents

Description

  The present invention relates to a subtree merging apparatus, a subtree merging method, and a subtree merging program for merging a plurality of subtrees.

  For example, Non-Patent Document 1 is a directory-type search service in which a user selects a category presented by the system and performs a search while narrowing down a search target. The user does not need to enter a search query, and even if the user has an ambiguous search request that is difficult to express as a search query or cannot be remembered as a specific search query, the category presented by the system can be selected. The search target can be narrowed down.

  Moreover, as a method of merging category hierarchies in which categories are regarded as nodes, there is a method shown in Non-Patent Document 2, for example.

“Goo category search”, <URL: http://category.goo.ne.jp/> Manabu Okumura, “Introduction to Machine Learning for Language Processing”, Corona, 2011

  Since the category hierarchy used in the directory search service is manually constructed for each service, the category hierarchy is different for each service. For this reason, the user has to follow different category hierarchies for each service, making it difficult to search, and the convenience of the user's search is reduced. Under such circumstances, there is a need to construct a category hierarchy that can be easily followed by a user by merging a plurality of category hierarchies constructed in one service or a category hierarchy individually constructed by a plurality of services.

  However, in the clustering method based on the shortest distance method based only on the relationship between two nodes at the time of merging shown in Non-Patent Document 2, for example, a category hierarchy having a large average depth of a hierarchy or a category having a large number of average child categories at each node There is a possibility that a category hierarchy having a high search cost for a user search, such as a hierarchy, may be constructed. In this case, there is a problem that an average search time of a user who uses the category hierarchy increases.

  The present invention has been made in view of the above circumstances, and an object of the present invention is to reduce a burden on a user's search and reduce a user's average search time, a partial tree merging apparatus, a partial tree merging method, and a partial To provide a tree merger program.

  In order to achieve the above object, the present invention according to claim 1 is a subtree merging apparatus for merging a plurality of subtrees, wherein the node information of a plurality of subtrees is input and stored in the subtree storage means. And node information of two subtrees from the subtree storage means, and the root node of the first subtree is arranged and merged so as to be a child node of each node other than the leaf node of the second subtree A loss cost calculation means for calculating the loss cost in each case, and storing the loss cost storage means in the loss cost storage means, specifying an arrangement where the loss cost is minimized from the loss cost storage means, and a first subtree and a second subtree Are generated and registered in the subtree storage means, and the node information of the first subtree before merging and the second from the subtree storage means are generated. Part of Merging means for deleting tree node information, and the loss cost includes a search cost of a subtree after merging, a search cost of a first subtree before merging, and a search cost of a second subtree before merging. The gist is that it is a difference from the sum.

  The present invention according to claim 2 is the subtree merging device, wherein the loss cost calculating means and the merging means are configured to perform a loss cost until the node information of the subtree stored in the subtree storage means becomes one. The merging means outputs the node information of the subtree as a category hierarchy when the subtree node information stored in the subtree storage means becomes one. To do.

  The invention according to claim 3 is the subtree merging device, wherein the loss cost calculation means sets a parent-child score indicating the strength of the parent-child relationship between the nodes and a sibling score indicating the strength of the sibling relationship between the nodes. The gist is to calculate the search cost with reference to the paired relationship score storage means.

  The present invention according to claim 4 is a subtree merging method for merging a plurality of subtrees performed by a computer, wherein the input step of inputting node information of a plurality of subtrees and storing it in a subtree storage unit; Loss cost when node information of two subtrees is acquired from the subtree storage unit, and the root node of the first subtree is arranged and merged so as to be a child node of each node other than the leaf node of the second subtree. Respectively, and a loss cost calculating step for storing the loss cost in the loss cost storage unit, an arrangement in which the loss cost is minimized from the loss cost storage unit, and the first subtree and the second subtree are specified. Node information of the merged subtree after merging is generated and registered in the subtree storage unit, and the node information of the first subtree before merging and the second subtree are merged from the subtree storage unit. No A merging step of deleting information, and the loss cost is calculated by subtracting the subtree after merging, the sum of the search cost of the first subtree before merging and the search cost of the second subtree before merging. The gist is that it is a difference.

  The present invention according to claim 5 is a subtree merging method, wherein the loss cost calculation step and the merging step are performed until node information stored in the subtree storage unit becomes one, and When the node information of the subtree stored in the subtree storage unit becomes one, the gist is to further perform an output step of outputting the node information of the subtree as a category hierarchy.

  The present invention according to claim 6 is the subtree merging method, wherein the loss cost calculating step sets a parent-child score indicating the strength of the parent-child relationship between the nodes and a sibling score indicating the strength of the sibling relationship between the nodes. The gist is to calculate the search cost with reference to the pair relationship score storage unit.

  The present invention according to claim 7 is a partial tree merging program for causing a computer to function as the partial tree merging device.

  According to the present invention, it is possible to provide a subtree merging apparatus, a subtree merging method, and a subtree merging program that reduce the burden on the user's search and reduce the average search time of the user.

It is a block diagram of the partial tree merger which concerns on embodiment of this invention. It is a figure which shows the example of data of category pair relation score DB. It is a figure which shows the example of data of subtree DB. It is a figure which shows the example of data of loss cost DB. It is a flowchart which shows the process of this embodiment. An example of merging subtrees is shown. It is a figure which shows typically the search cost of the subtree before merging, and the search cost of the subtree after merging.

  Embodiments of the present invention will be described below with reference to the drawings.

  FIG. 1 is a configuration diagram showing a configuration of a subtree merging apparatus 1 in the present embodiment. The subtree merging apparatus 1 of this embodiment selects a category that is presented by the user from the system and searches the user for difficulty in searching the user in a directory type search service or the like that performs a search while narrowing down the search target. This is expressed as a numerical value as a cost (hereinafter referred to as “search cost”), and a category hierarchy having a low search cost is constructed by merging a plurality of category hierarchies. Specifically, the subtree merging apparatus 1 accepts the category pair relation score DB2 and the subtree DB3 as inputs, and outputs the category hierarchy DB050.

  The partial tree merging apparatus 1 shown in the figure includes a category pair relationship score DB 010, a partial tree DB 020, a control unit 030, a loss cost DB 040, and a category hierarchy DB 050. The control unit 030 includes an input unit 031, a loss cost calculation unit 032, and a subtree merging unit 033.

  The input unit 031 inputs the category pair relation score DB2 and the subtree DB3 and stores them in the working category pair relation score DB010 and the subtree DB020. The category pair relationship score DB 2 and the partial tree DB 3 may be DBs generated based on a plurality of category hierarchies (hereinafter referred to as “partial trees”) created by one directory search service. The DB may be generated based on a plurality of category hierarchies (hereinafter referred to as “partial trees”) individually created by a plurality of directory search services.

  The loss cost calculation unit 032 acquires a node set (node information) of two arbitrary unprocessed subtrees from the subtree DB 020, and sets the root node of the first subtree as a node of each node other than the leaf nodes of the second subtree. Loss costs are calculated when they are arranged so as to become child nodes and merged, and stored in the loss cost DB 040. The loss cost is the difference between the search cost of the subtree after merging and the sum of the search cost of the first subtree before merging and the search cost of the second subtree.

  The subtree merging unit 033 identifies an arrangement that minimizes the loss cost from the loss cost DB 040, and generates a node set of the subtree after merging that has merged the first subtree and the second subtree with the arrangement specified. Then, the node set is registered in the subtree DB 020, and the node set of the first subtree and the node set of the second subtree before merging are deleted from the subtree DB020.

  Further, the loss cost calculation unit 032 and the subtree merging unit 033 calculate and merge the loss cost until the node set of the subtree stored in the subtree DB 020 becomes one, and the subtree merging unit 033 When the node set of the subtree stored in the tree DB 020 becomes one, the node set of the subtree is output to the category hierarchy DB 050 as a category hierarchy.

  FIG. 2 shows a data example of the category pair relationship score DB 010 (or category pair relationship score DB 2). In the category pair relationship score DB 010, one record holds information on the relationship between two nodes. In this embodiment, a parent-child score indicating the strength of the parent-child relationship between the nodes and the strength of the sibling relationship between the nodes are stored. It shall hold a sibling score indicating The illustrated category pair relationship score DB 010 has a category 1 column, a category 2 column, a parent-child score column, and a sibling score column.

  For two nodes labeled with category kw1 in category 1 column and category kw2 in category 2 column, parent-child score oyako score (kw1, kw2) is an estimate that indicates the possibility that kw1 is the parent node of kw2. And Also, the brother score kyodai score (kw1, kw2) is an estimated value indicating the possibility that two nodes have a sibling relationship.

  It is assumed that all combinations of arbitrary two nodes (categories) of all nodes stored in the partial tree DB 020 are stored in the category pair relationship score DB 010. That is, the categories stored in the category 1 column and the category 2 column of the category pair relation score DB 010 are combinations of arbitrary two nodes of all the nodes (categories) stored in the node set column of the subtree DB 020. And one record for one combination.

  In an existing directory search service such as the goo category search of Non-Patent Document 1, these scores can be easily calculated based on the arrangement relationship of nodes having kw1 and kw2 as labels in the category hierarchy of the search service system. Shall.

  For example, one node is arranged higher than the other node, and a score that is higher as the difference in the depth between the two nodes is smaller is calculated and used as the parent-child score. In addition, a score that is high when two nodes have the same parent node and is low when the two nodes do not have the same parent node is calculated as a sibling score.

  FIG. 3 shows a data example of the subtree DB020 (or subtree DB3). In the subtree DB 020, one record holds information of one subtree. Each record (subtree) has a subtree ID column and a node set column. The subtree has a tree structure in which the category is regarded as a node.

  The node set column stores information on a plurality of nodes included in the subtree. For each node, the label name of the node, the label name of the parent node of the node, and the label name of the child node set of the node are stored. Retained. However, when the node is a root node, the label name of the parent node is None. If the node is a leaf node, the label name of the child node set is None.

  FIG. 4 shows an example of data in the loss cost DB 040. The loss cost DB 040 includes a subtree ID1 column, a subtree ID2 column, a category 1 column, a category 2 column, and a loss cost column. Assume that the categories stored in the category 1 column and the category 2 column are categories (nodes) stored in the node set column of the subtree DB 020.

  The category hierarchy DB 050 stores a category hierarchy as a result of merging the partial trees of the partial tree DB 020 into one. The category hierarchy DB 050 stores one node set column similar to the node set column of the subtree DB 020 as the category hierarchy.

  As the partial tree merging apparatus 1 described above, for example, a general-purpose computer system including a CPU, a memory, and an external storage device such as an HDD can be used. In this computer system, each function of the subtree merging apparatus 1 is realized by the CPU executing a program for the subtree merging apparatus 1 loaded on the memory. The program for the partial tree merging apparatus 1 can be stored in a computer-readable recording medium such as a hard disk, a flexible disk, a CD-ROM, an MO, and a DVD-ROM, or can be distributed via a network.

  Next, processing of the partial tree merging apparatus 1 of the present embodiment will be described.

  FIG. 5 is a flowchart showing a process flow of the control unit 030.

  S100: The input unit 031 inputs the category pair relation score DB2 and the subtree DB3 and stores them in the working category pair relation score DB010 and the subtree DB020.

  S110: The loss cost calculation unit 032 empties the loss cost DB 040.

  S120: The loss cost calculation unit 032 acquires records of any two unprocessed subtrees from the subtree DB 020. Here, the acquired subtree IDs of the two subtrees are t1 and t2.

  S130: The loss cost calculation unit 032 selects a node whose label name of the child node set is other than None from all the nodes in the node set column of the record whose subtree ID is t2 in the subtree DB020 (ie, a node other than a leaf node) ) And let X be the set of all nodes other than the leaf node of t2. Loss cost cost (n1) when subtrees t1 and t2 are merged with n1 placed as a child node of n2 for root node n1 of t1 and each node n2 of the set X of t2 , n2).

  FIG. 6 shows a subtree obtained by merging two subtrees t1 and t2 with subtrees t1 and t2 before merging arranged so that root node n1 of t1 becomes a child node of n2 of t2. . Here, the subtree ID of the subtree after merging is assumed to be t3.

Loss cost cost (n1, n2) is the sum of the search costs before merging and the merged t1 and t2 by placing t1 and t2 so that root node n1 of t1 becomes the child node of n2 of t2. This represents the difference from the search cost. That is, the loss cost cost (n1, n2) can be calculated by the following equation using the search cost search cost (t1), search cost (t2), and search cost (t3).

  FIG. 7 is a diagram schematically showing the search cost of the subtrees t1 and t2 before merging shown in FIG. 6 and the search cost of the subtree t3 after merging.

The search cost (T) of the subtree T is the subtree score division score (p, calculated for each subtree of height 1 when the subtree T is divided by subtrees of height 1. Cp) is the sum of the reciprocals. That is, the search cost search cost (T) can be calculated by the following equation using the subtree score division score (p, Cp).

Here, let P be a set having elements other than leaf nodes included in T as elements, and Cp be a child node set in element p of P. The subtree score division score (p, Cp) is an estimated value indicating the strength of the parent-child relationship and the strength of the sibling relationship in the height-1 subtree having the parent node as p and the child node set of p as Cp. The subtree score division score (p, Cp) can be calculated by the following equation, for example.

  Here, for the parent-child score oyako score (p, c) and sibling score kyodai score (c1, c2) of the above formula, the corresponding parent-child score or sibling score is obtained by referring to the category pair relationship score DB 010.

| Cp | represents the number of elements of the set Cp. Further, γ is the number of combinations of any two elements of the set Cp, and is expressed by the following equation. Α represents the contribution ratio of two scores, and 0 ≦ α ≦ 1.

  The subtree score division score (p, Cp) is higher as the average of the parent-child scores of p and the set Cp is higher, and is higher as the average of the sibling scores of the child node set is higher. When the division score (p, Cp) of each subtree of height 1 is high, the parent-child relationship and sibling relationship between the parent node and child node set in T are strong, and the search cost is low.

  The loss cost calculation unit 032 calculates the loss cost cost (n1, n2) when the root node n1 of t1 is arranged to be a child node of each n2 for each node n2 of the set X of t2. And stored in the loss cost DB 040. Specifically, each record of (t1, t2, n1, n2, cost (n1, n2)) is generated and stored in the loss cost DB 040.

  S140: The loss cost calculation unit 032 selects a node whose label name of the child node set is other than None from all the nodes in the node set column of the record whose subtree ID is t1 in the subtree DB020 (that is, a node other than a leaf node) ) And Y is a set of all nodes other than the leaf node of t1. For each root node n2 of t2 and each node n1 of the elements of set Y of t1, loss cost cost (n2 when n2 is arranged to be a child node of n1 and subtrees t1 and t2 are merged , n1) is calculated in the same manner as in S130, and stored in the loss cost DB 040. Specifically, each record of (t2, t1, n2, n1, cost (n2, n1)) is generated and stored in the loss cost DB 040.

  S150: If there is a combination of two unprocessed subtrees (S150: YES), the loss cost calculation unit 032 returns to S120 and performs S130 and S140 on the two unprocessed subtrees. On the other hand, when there is no combination of two unprocessed subtrees, that is, when the processes of S130 and S140 are performed in all combinations (S150: NO), the process proceeds to S160.

  S160: The subtree merging unit 033 has the smallest loss cost cost (n1, n2) (or cost (n2, n1)) among the records stored in the loss cost DB 040 (t1, t2, n1, n2). , cost (n1, n2)) (or (t2, t1, n2, n1, cost (n2, n1))), and n1 is a child node of n2 (or n2 is a child node of n1) Thus, the partial trees t1 and t2 are arranged and merged. Specifically, the subtree merging unit 033 sets an unused subtree ID as a subtree ID of the subtree DB 020 as a subtree ID of the subtree after merging, and the subtree t1 based on the specified record arrangement. And t2 are merged, and the merged partial tree is registered in the partial tree DB 020 as one partial tree record.

  The subtree merging unit 033 deletes records corresponding to the subtrees t1 and t2 before merging from the subtree DB 020. In this way, each time the subtree merging process of S160 is executed, one record is reduced from the subtree DB020.

  S170: If the number of records in the subtree DB 020 is 2 or more (S170: YES), the process returns to S110 and the subsequent processing is repeated. On the other hand, if the number of records in the subtree DB 020 is 1 (S170: NO), the process proceeds to S180.

  S180: The subtree merging unit 033 stores the node set column of the record in the category hierarchy DB050 when the number of records in the subtree DB020 is 1. When the number of records in the subtree DB 020 is 1, it means that a plurality of subtrees stored in the subtree DB 020 at the start of processing are merged into one. That is, at this time, the partial tree stored in the partial tree DB 020 becomes the category hierarchy.

  In the subtree merging apparatus 1 of the present embodiment described above, the difficulty of the user search is expressed numerically as the cost for the user search, and a category hierarchy having a low search cost is constructed by merging a plurality of category hierarchies. To do. Specifically, category hierarchies are constructed by merging sequentially from the one with the lowest loss cost, which is the difference between the search cost of the subtree after merging and the sum of the search costs of the subtrees before merging.

  As a result, in this embodiment, subtrees can be merged in consideration of the search cost after the search, so that a category hierarchy with a low search cost can be constructed, and a directory-type search service that is easy for a user to search and search is provided. Can be offered. That is, it is possible to reduce the burden on the user's search, reduce the user's average search time, and improve the user's convenience.

  Further, in this embodiment, in S130 and S140 of FIG. 5, the subtrees are merged using the node sets X and Y excluding the leaf nodes. In this way, by placing the root node of another subtree in a node other than the leaf node, the depth of the subtree (or category hierarchy) after merging is increased and the search cost is prevented from increasing. Can do.

  In addition, this invention is not limited to the said embodiment, Many deformation | transformation are possible within the range of the summary.

1: Partial tree merging device 2: Category pair relation score DB
3: Partial tree DB
010: Category pair relation score DB
020: Partial tree DB
030: Control unit 031: Input unit 032: Loss cost calculation unit 033: Subtree merger 040: Loss cost DB
050: Category hierarchy DB

Claims (7)

A subtree merging device that merges a plurality of subtrees,
Input means for inputting node information of a plurality of subtrees and storing them in the subtree storage means;
Loss when node information of two subtrees is acquired from the subtree storage means and the root node of the first subtree is arranged and merged so as to be a child node of each node other than the leaf node of the second subtree A loss cost calculating means for calculating each cost and storing it in a loss cost storage means;
Identifying an arrangement that minimizes the loss cost from the loss cost storage means, generating node information of a merged subtree obtained by merging the first subtree and the second subtree in the identified arrangement; Merging means for registering in the tree storage means and deleting the node information of the first subtree and the second subtree before merging from the subtree storage means,
The loss cost is the difference between the search cost of the subtree after merging and the sum of the search cost of the first subtree and the search cost of the second subtree before merging. apparatus. The partial tree merging device according to claim 1,
The loss cost calculating means and the merging means perform calculation and merging of the loss cost until there is only one subtree node information stored in the subtree storage means,
The submergence merging device, wherein when the node information stored in the subtree storage unit becomes one, the merger outputs node information of the subtree as a category hierarchy. The subtree merging device according to claim 1 or 2,
The loss cost calculation means calculates the search cost with reference to a pair relation score storage means in which a parent-child score indicating the strength of the parent-child relationship between the nodes and a sibling score indicating the strength of the sibling relationship between the nodes are set. This is a partial tree merger. A subtree merging method for merging a plurality of subtrees performed by a computer,
An input step of inputting node information of a plurality of subtrees and storing it in a subtree storage unit;
Loss when node information of two subtrees is acquired from the subtree storage unit, and the root node of the first subtree is arranged and merged so as to be a child node of each node other than the leaf node of the second subtree. A loss cost calculating step of calculating each cost and storing in the loss cost storage unit;
The arrangement that minimizes the loss cost from the loss cost storage unit, generates node information of a merged subtree obtained by merging the first subtree and the second subtree in the specified arrangement, and Registering in the tree storage unit, and performing a merging step of deleting the node information of the first subtree and the node information of the second subtree before merging from the subtree storage unit,
The loss cost is the difference between the search cost of the subtree after merging and the sum of the search cost of the first subtree and the search cost of the second subtree before merging. Method. A sub-tree merging method according to claim 4,
The loss cost calculation step and the merging step are performed until the node information of the subtree stored in the subtree storage unit becomes one,
The subtree merging method, further comprising: an output step of outputting the node information of the subtree as a category hierarchy when the node information of the subtree stored in the subtree storage unit becomes one. The subtree merging method according to claim 4 or 5,
The loss cost calculating step calculates the search cost with reference to a pair relationship score storage unit in which a parent-child score indicating the strength of a parent-child relationship between nodes and a sibling score indicating the strength of a sibling relationship between nodes are set. This is a method for merging subtrees.   A subtree merging program for causing a computer to function as the subtree merging device according to claim 1.

Images