Reinforced clustering of multi-type data objects for search term suggestion
Systems and methods for related term suggestion are described. In one aspect, relationships among respective ones of two or more multi-type data objects are identified. The respective ones of the multi-type data objects include at least one object of a first type and at least one object of a second type that is different from the first type. The multi-type data objects are iteratively clustered in view of respective ones of the relationships to generate reinforced clusters.
1. A computer-implemented method performed by a computing device that has one or more processors to execute instructions, the method comprising:
identifying relationships between multi-type data objects that include at least one object of a first type and at least one object of a second type different from the first type, the relationships being at least one of intra-layer relationships or inter-layer relationships among the multi-type data objects;
iteratively clustering the multi-type data objects based on the relationships to generate reinforced clusters;
generating a list of suggested search terms associated with a bid term using the reinforced clusters, the search terms generated in response to receiving the bid term from a user;
transmitting, via a network interface, the list of suggested search terms to a user; and
mutually reinforcing an importance of individual ones of the multi-type data objects within an object type and between different object types based on the following:
{
a
(
X
)
=
β
L
X
T
h
(
X
)
+
(
1
-
β
)
L
XY
i
(
Y
)
h
(
X
)
=
β
L
X
a
(
X
)
+
(
1
-
β
)
L
XY
i
(
Y
)
i
(
X
)
=
a
(
X
)
+
h
(
X
)
a
(
Y
)
=
γ
L
Y
T
h
(
Y
)
+
(
1
-
γ
)
L
YX
i
(
X
)
h
(
Y
)
=
γ
L
Y
a
(
Y
)
+
(
1
-
γ
)
L
YX
i
(
X
)
i
(
Y
)
=
a
(
Y
)
+
h
(
Y
)
wherein X={x 1 , x 2 , . . . x m } and Y={y 1 , y 2 , . . . y n } represent respective object sets of heterogeneous object type with relationships R X , R Y , R XY and R YX if directionality is considered L X and L Y represent adjacent matrixes of links identifying relationships within set X and Y respectively, L XY and L YX represent adjacent matrixes of links identifying relationships from objects in X to objects in Y, a(X) and h(X) are an authority score and a hub score of nodes within X respectively, a(Y) and h(Y) respectively represent authority scores and hub scores of nodes in Y, i(X) and i(Y) respectively represent an importance of the nodes in X and Y, and β and γ are weight parameters to adjust influence of links derived from different relationships.
2. The method of claim 1 , wherein the inter-layer relationships include at least one of content related information, user interest in an associated topic, and user interest in an associated Web page.
3. The method of claim 1 , wherein the intra-layer relationships include at least one of query refinement, recommended Web page, and relationship between respective users.
4. The method of claim 1 , wherein each of the multi-type data objects are related to at least one of a selected Web page type and a user information type.
5. The method of claim 1 , wherein the intra-layer relationships include a first weighting scheme and the intra-layer relationships include a second weighting scheme different than the first weighting scheme to indicate importance to associated objects of the multi-type data objects.
6. The method of claim 1 , wherein the identifying and the iteratively clustering are performed for the suggested searched terms.
7. The method of claim 1 , wherein the iteratively clustering comprises propagating clustering results of a first iteration to all related data objects of the multi-type data objects, at least two of the related data objects being of heterogeneous data type, the propagating being used to enhance clustering of respective ones of the multi-type data objects in a second iteration of reinforced clustering operations.
8. The method of claim 1 , wherein the iteratively clustering comprises determining a similarity between individual ones of the multi-type data objects, the similarity being a function of at least one of inter-object and intra-object content similarity and similarities between the inter-layer relationships and the intra-layer relationships.
9. The method of claim 1 , wherein the iteratively clustering comprises merging related ones of the multi-type data objects to reduce feature space dimensionality of the related ones.
10. The method of claim 1 , wherein the method further comprises mutually reinforcing an importance of individual ones of the multi-type data objects within an object type and between different object types.
11. The method of claim 1 , further comprising:
comparing the bid term with a feature space of objects in the reinforced clusters to identify the suggested search terms.
12. A computer-readable storage medium comprising computer-executable instructions executable by a processor for:
identifying at least one of intra-layer and inter-layer relationships among multi-type data objects, wherein the multi-type data objects comprise at least one object of a first type and at least one object of a second type different from the first type;
iteratively clustering the multi-type data objects by at least one of the relationships to generate reinforced clusters;
generating a list of suggested search terms associated with a bid term using the reinforced clusters, the suggested search terms generated in response to receiving the bid term from a user; and
mutually reinforcing an importance of individual ones of the multi-type data objects within an object type and between different object types based on the following:
{
a
(
X
)
=
β
L
X
T
h
(
X
)
+
(
1
-
β
)
L
XY
i
(
Y
)
h
(
X
)
=
β
L
X
a
(
X
)
+
(
1
-
β
)
L
XY
i
(
Y
)
i
(
X
)
=
a
(
X
)
+
h
(
X
)
a
(
Y
)
=
γ
L
Y
T
h
(
Y
)
+
(
1
-
γ
)
L
YX
i
(
X
)
h
(
Y
)
=
γ
L
Y
a
(
Y
)
+
(
1
-
γ
)
L
YX
i
(
X
)
i
(
Y
)
=
a
(
Y
)
+
h
(
Y
)
wherein X={x 1 , x 2 , . . . x m } and Y={y 1 , y 2 , . . . y n } represent respective object sets of heterogeneous object type with relationships R X , R Y , R XY and R YX if directionality is considered, L X and L Y represent adjacent matrixes of links identifying relationships within set X and Y respectively, L XY and L YX represent adjacent matrixes of links identifying relationships from objects in X to objects in Y, a(X) and h(X) are an authority score and a hub score of nodes within X respectively, a(Y) and h(Y) respectively represent authority scores and hub scores of nodes in Y, i(X) and i(Y) respectively represent an importance of the nodes in X and Y, and β and γ are weight parameters to adjust influence of links derived from different relationships.
13. The computer-readable storage medium of claim 12 , wherein the inter-layer relationships comprise at least one of content related information, user interest in an associated topic, and user interest in an associated Web page.
14. The computer-readable storage medium of claim 12 , wherein the intra-layer relationships comprise at least one of query refinement, recommended Web page, and relationship between respective users.
15. The computer-readable storage medium of claim 12 , wherein each of the multi-type data objects are related to at least one of a search query data object type, a selected Web page type, and a user information type.
16. The computer-readable storage medium of claim 12 , wherein The at least one of the identified relationships are weighted to indicate an importance to associated objects of the multi-type data objects.
17. The computer-readable storage medium of claim 12 , wherein the identifying and the iteratively clustering are performed for the suggested search term.
18. The computer-readable storage medium of claim 12 , wherein the iteratively clustering comprises propagating clustering results of a first iteration to all related data objects of the multi-type data objects, at least two of the related data objects being of heterogeneous data type, the propagating being used to enhance clustering of respective ones of the multi-type data objects in a second iteration of reinforced clustering operations.
19. The computer-readable storage medium of claim 12 , wherein the iteratively clustering comprises determining a similarity between individual ones of the multi-type data objects, the similarity being a function of at least on of object content similarity and similarities between at least one of the identified relationships.
20. The computer-readable storage medium of claim 12 , wherein the iteratively clustering comprises merging related ones of the multi-type data objects to reduce feature space dimensionality of the related ones.
21. The computer-readable storage medium of claim 12 , wherein the instructions further comprise instructions for mutually reinforcing an importance of individual ones of the multi-type data objects within an object type and between different object types.
22. The computer-readable storage medium of claim 12 , wherein the instructions further comprise:
comparing the bid term with a feature space of objects in the reinforced clusters to identify the suggested search terms.