Reinforced clustering of multi-type data objects for search term suggestion

• US 20050234972A1
• Filed: 04/15/2004
• Published: 10/20/2005
• Est. Priority Date: 04/15/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ma, Wei-Ying, Chen, Zheng, Najm, Tarek, Li, Li, Zhang, Benyu, Li, Ying, Zeng, Hua-Jun
• Granted Patent: US 7,689,585 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9532 Query formulation
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

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.

Claims

1. A method comprising:

identifying relationships among respective ones of two or more multi-type data objects, wherein the respective ones comprise at least one object of a first type and at least one object of a second type different from the first type; and

iteratively clustering the multi-type data objects in view of respective ones of the relationships to generate reinforced clusters.

2. A method as recited in claim 1, wherein the relationships comprise inter-layer relationships including one or more of content related information, user interest in an associated topic, and user interest in an associated Web page.

3. A method as recited in claim 1, wherein the relationships comprise intra-layer relationships including one or more of query refinement(s), recommended Web page(s), and relationship(s) between respective users.

4. A method as recited in claim 1, wherein each of the multi-type data objects are related to one or more of a search query data object type, a selected Web page type, and a user information type.

5. A method as recited in claim 1, wherein respective ones of the relationships are weighted to indicate importance to associated objects of the multi-type data objects.

6. A method as recited in claim 1, wherein identifying and iteratively clustering are performed for search term suggestion.

7. A method as recited in claim 1, wherein iteratively clustering further 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. A method as recited in claim 1, wherein iteratively clustering further comprises determining similarity between individual ones of the multi-type data objects, the similarity being a function of one or more of inter-object and intra-object content similarity and similarities between respective ones of the relationships.

9. A method as recited in claim 1, wherein iteratively clustering further comprises merging related ones of the multi-type data objects to reduce feature space dimensionality of the related ones.

10. A method as recited in claim 1, wherein the method further comprises mutually reinforcing importance of individual ones of the multi-type data objects within an object type and between different object types.

11. A method as recited in claim 10, wherein mutually reinforcing importance of individual ones of the multi-type data objects within an object type and between different object types is based on the following:

$\hspace{1em}<br><br>\{\begin{array}{c}a<br><br>\left(X\right)=\mathrm{\beta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>L_X^T<br><br>h<br><br>\left(X\right)+\left(1-\mathrm{\beta <br><br>}\right)<br><br>L_{\mathrm{XY}}<br><br>i<br><br>\left(Y\right)\\ h<br><br>\left(X\right)=\mathrm{\beta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>L_X<br><br>a<br><br>\left(X\right)+\left(1-\mathrm{\beta <br><br>}\right)<br><br>L_{\mathrm{XY}}<br><br>i<br><br>\left(Y\right)\\ i<br><br>\left(X\right)=a<br><br>\left(X\right)+h<br><br>\left(X\right)\\ \text{\hspace{1em}<br><br>}\\ a<br><br>\left(Y\right)=\mathrm{\gamma <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>L_Y^T<br><br>h<br><br>\left(Y\right)+\left(1-\mathrm{\gamma <br><br>}\right)<br><br>L_{\mathrm{YX}}<br><br>i<br><br>\left(X\right)\\ h<br><br>\left(Y\right)=\mathrm{\gamma <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>L_Y<br><br>a<br><br>\left(Y\right)+\left(1-\mathrm{\gamma <br><br>}\right)<br><br>L_{\mathrm{YX}}<br><br>i<br><br>\left(X\right)\\ i<br><br>\left(Y\right)=a<br><br>\left(Y\right)+h<br><br>\left(Y\right)\end{array}$

wherein X={χ

₁, χ

₂, . . . χ

_m} and Y={y₁, y₂, . . . y_n} represent respective object sets of heterogeneous object type, R_X, R_Y, R_XY and R_YX represent relationships between respective objects of the multi-type data objects, L_X and L_Y represent adjacent matrixes of link/relationship structures within set X and Y respectively, L_XY and L_YX represent adjacent matrixes of links/relationships from objects in X to objects in Y, a(X) and h(X) are an authority score and hub score of nodes within X,./respectively, a(Y) and h(Y) stand for the authority and hub score of nodes in Y;

i(X) and i(Y) stand for the importance of the node in X and Y, respectively. β and

γ

are the weight parameters to adjust the influence of links derived from different relationships.

12. A method as recited in claim 1, and further comprising:

responsive to receiving a term from a user, comparing the term with feature space of objects in the reinforced clusters;

responsive to comparing, identifying one or more search term suggestions; and

communicating the search term suggestions to the user.

13. A computing device comprising:

a processor; and

a memory coupled to the processor, the memory comprising computer-program instructions executable by the processor for;

identifying relationships among respective ones of two or more multi-type data objects, wherein the respective ones 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 in view of respective ones of the relationships to generate reinforced clusters; and

wherein respective ones of the relationships are weighted to indicate importance to associated objects of the multi-type data objects.

14. A computing device as recited in claim 13, wherein the relationships comprise inter-layer relationships including one or more of content related information, user interest in an associated topic, and user interest in an associated Web page.

15. A computing device as recited in claim 13, wherein the relationships comprise intra-layer relationships including one or more of query refinement(s), recommended Web page(s), and relationship(s) between respective users.

16. A computing device as recited in claim 13, wherein identifying and iteratively clustering are performed for search term suggestion.

17. A computing device as recited in claim 13, wherein the instructions for iteratively clustering further comprise instructions for aggregating indicated data object relationships to related ones of the multi-type data objects based on content of the reinforced clusters.

18. A computing device as recited in claim 13, wherein the instructions for iteratively clustering further comprise instructions for determining similarity between individual ones of the multi-type data objects, the similarity being a function of one or more of inter-object and intra-object content similarity and similarities between respective ones of the relationships.

19. A computing device as recited in claim 13, wherein the instructions for iteratively clustering further comprise instructions for merging related ones of the multi-type data objects to reduce feature space dimensionality of the related ones.

20. A computing device as recited in claim 13, wherein the instructions for iteratively clustering further comprise instructions for iteratively clustering until all object types represented by the multi-type data objects converge.

21. A computing device as recited in claim 13, and further comprising instructions for:

responsive to receiving a term from a user, comparing the term with feature space of objects in the reinforced clusters;

responsive to comparing, identifying one or more search term suggestions; and

communicating the search term suggestions to the user.

22. A computer-readable medium comprising computer-executable instructions executable by a processor for:

identifying one or more of intra-layer and inter-layer relationships among respective ones of two or more multi-type data objects, wherein the respective ones comprise at least one object of a first type and at least one object of a second type different from the first type; and

iteratively clustering the multi-type data objects in view of respective ones of the relationships to generate reinforced clusters.

23. A computer-readable medium as recited in claim 22, wherein the inter-layer relationships comprise one or more of content related information, user interest in an associated topic, and user interest in an associated Web page.

24. A computer-readable medium as recited in claim 22, wherein the intra-layer relationships comprise at least one of query refinement(s), recommended Web page(s), and relationship(s) between respective users.

25. A computer-readable medium as recited in claim 22, 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.

26. A computer-readable medium as recited in claim 22, wherein respective ones of the relationships are weighted to indicate importance to associated objects of the multi-type data objects.

27. A computer-readable medium as recited in claim 22, wherein identifying and iteratively clustering are performed for search term suggestion.

28. A computer-readable medium as recited in claim 22, wherein iteratively clustering further 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.

29. A computer-readable medium as recited in claim 22, wherein iteratively clustering further comprises determining similarity between individual ones of the multi-type data objects, the similarity being a function of at least one of object content similarity and similarities between respective ones of the relationships.

30. A computer-readable medium as recited in claim 22, wherein iteratively clustering further comprises merging related ones of the multi-type data objects to reduce feature space dimensionality of the related ones.

31. A computer-readable medium as recited in claim 22, wherein the instructions further comprise instructions for mutually reinforcing importance of individual ones of the multi-type data objects within an object type and between different object types.

32. A computer-readable medium as recited in claim 31, wherein mutually reinforcing importance of individual ones of the multi-type data objects within an object type and between different object types is based on the following:

$\hspace{1em}<br><br>\{\begin{array}{c}a<br><br>\left(X\right)=\mathrm{\beta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>L_X^T<br><br>h<br><br>\left(X\right)+\left(1-\mathrm{\beta <br><br>}\right)<br><br>L_{\mathrm{XY}}<br><br>i<br><br>\left(Y\right)\\ h<br><br>\left(X\right)=\mathrm{\beta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>L_X<br><br>a<br><br>\left(X\right)+\left(1-\mathrm{\beta <br><br>}\right)<br><br>L_{\mathrm{XY}}<br><br>i<br><br>\left(Y\right)\\ i<br><br>\left(X\right)=a<br><br>\left(X\right)+h<br><br>\left(X\right)\\ \text{\hspace{1em}<br><br>}\\ a<br><br>\left(Y\right)=\mathrm{\gamma <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>L_Y^T<br><br>h<br><br>\left(Y\right)+\left(1-\mathrm{\gamma <br><br>}\right)<br><br>L_{\mathrm{YX}}<br><br>i<br><br>\left(X\right)\\ h<br><br>\left(Y\right)=\mathrm{\gamma <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>L_Y<br><br>a<br><br>\left(Y\right)+\left(1-\mathrm{\gamma <br><br>}\right)<br><br>L_{\mathrm{YX}}<br><br>i<br><br>\left(X\right)\\ i<br><br>\left(Y\right)=a<br><br>\left(Y\right)+h<br><br>\left(Y\right)\end{array}$

wherein X={χ

₁, χ

₂, . . . χ

_m} and Y={y₁, y₂, . . . y_n} represent respective object sets of heterogeneous object type, R_X, R_Y, R_XY and R_YX represent relationships between respective objects of the multi-type data objects, L_X and L_Y represent adjacent matrixes of link/relationship structures within set X and Y respectively, L_XY and L_YX represent adjacent matrixes of links/relationships from objects in X to objects in Y, a(X) and h(X) are an authority score and hub score of nodes within X,./respectively, a(Y) and h(Y) stand for the authority and hub score of nodes in Y;

i(X) and i(Y) stand for the importance of the node in X and Y respectively. β and

γ

are the weight parameters to adjust the influence of links derived from different relationships.

33. A computer-readable medium as recited in claim 22, and further comprising instructions for:

responsive to receiving a term from a user, comparing the term with feature space of objects in the reinforced clusters;

responsive to comparing, identifying one or more search term suggestions; and

communicating the search term suggestions to the user.

34. A computing device comprising:

identifying means to identify relationships among respective ones of two or more multi-type data objects, wherein the respective ones comprise at least one object of a first type and at least one object of a second type different from the first type; and

iterative clustering means to iteratively cluster the multi-type data objects in view of respective ones of the relationships to generate reinforced clusters.

35. A computing device as recited in claim 34, wherein the computing device further comprises weighting means to weight respective ones of the relationships to indicate importance to associated objects of the multi-type data objects.

36. A computing device as recited in claim 34, wherein the computing device further comprises determining means to locate a search term suggestion from the reinforced clusters responsive to receipt of a bid term, the search term suggestion substantially matching or being related to one or more of the multi-type data objects.

37. A computing device as recited in claim 34, wherein the iterative clustering means further comprise aggregating means to propagate indicated data object relationships to related ones of the multi-type data objects based on content of the reinforced clusters.

38. A computing device as recited in claim 34, wherein the iterative clustering means further comprise determining means to determine similarity between individual ones of the multi-type data objects, the similarity being a function of at least one of object content similarity and similarities between respective ones of the relationships.

39. A computing device as recited in claim 34, wherein the iterative clustering means further comprise merging means to combine related ones of the multi-type data objects to reduce feature space dimensionality of the related ones.

40. A computing device as recited in claim 34, and further comprising:

comparing means, responsive to receiving a term from a user, to compare the term with feature space of objects in the reinforced clusters; and

responsive to comparing, identifying means to identify one or more search term suggestions.