Search term clustering

• US 10,198,497 B2
• Filed: 06/09/2014
• Issued: 02/05/2019
• Est. Priority Date: 06/11/2013
• Status: Active Grant

• Current Assignee: [24]7.ai, Inc.
• Original Assignee: [24]7.ai, Inc.
• Inventors: Gangavaram, Viswanath, Hedge, Darshan
• Primary Examiner(s): Saeed, Usmaan
• Application Number:
  US14/300,093
• Publication Number:
  US 20140365494A1
• Time in Patent Office: 1,702 Days
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/285 Clustering or classification

Abstract

When conducting the same or similar search, different users can use different search terms and phrases, resulting in an increase in the quantity of unique search terms and phrases. The intent of the various search terms and phrases is determined based on clustering of the terms and phrases of the various users. User search terms bare clustered using semantic and syntactic distances. Thus, the search engine receives a search query from a user and computes a similarity between and among user search terms. The computation uses syntactic techniques to analyze lexical aspects of linguistic terms, and semantic techniques to consider activity of the user in the particular field of interest. A similarity metric is used to determine the similarity between two search terms by computing their syntactic and semantic distances. A clustering technique is then used to cluster search terms based on their pair-wise distance.

Claims

1. A computer-implemented search method, comprising:

providing a processor executing instructions for;

receiving, from a user, a search request including any of search terms, and phrases;

using syntactic and semantic measures to determine a similarity metric between the any of search terms, and phrases received from the user and any of search terms, and phrases entered by others, wherein said syntactic measures analyze lexical aspects of said any of search terms, and phrases, and said semantic measures consider user activity;

using a clustering technique to cluster said any of search terms, and phrases received from the user within said any of search terms, and phrases entered by others in view of said similarity metric based on a pair-wise distance of said any of search terms, and phrases;

generating a weighted sub-graph of a website based on the similarity metric of said any of search terms, and phrases, said sub-graph assigning weights to Web journey choices based on Web journeys made by others who conduct searches with similar any of search terms, and phrases, wherein a graph is a linkage structure of nodes, wherein in a website, each page is a node in a website graph and an edge is a hyperlink from one page to another page, wherein at least one edge has weight, wherein if the graph has weighted edges, then the graph is a weighted graph, wherein a path is a sequence of nodes in the graph, wherein said weighted sub-graph comprises the weighted graph with sub-structure of a given website, and wherein said weights represent how many times all users visit from one page to another page after searching a particular any of search term, and phrase either internally or externally, on the website;

determining search results, wherein said determination includes determining the cluster associated the search request, and determining a highest weight of the weighted sub-graph weights associated with the any of search terms, and phrases of the cluster associated with the search request; and

generating a list of search results, the list of search results being based on an increased quantity of unique search terms or phrases associated with the cluster generated using the search request, and being ordered by the highest weight of the weighted sub-graph weights; and

displaying the list of search results representing optimized search results in response to the search request.

2. The method of claim 1, further comprising:

using said similarity metric to measure a similarity between two given any of search terms, and phrases (ST1, ST2) by combining their syntactic and semantic distances as follows;

Similarity(ST1, ST2)=a*(Syntactic_Distance(ST1, ST2))+b*(Semantic_Distance(ST1, ST2));

where “

a”

is a variable coefficient representing significance related to usage of syntactic distance between ST1 and ST2, and “

b”

is a variable coefficient representing significance related to usage of semantic distance between ST1 and ST2.

3. The method of claim 1, further comprising:

initially applying said syntactic measures to determine similarity between two given any of search terms, and phrases, expressed in terms of syntactic distance, as;

Similarity(ST1, ST2)=(Syntactic_Distance(ST1, ST2));

applying the clustering technique with a pair-wise distance between the any of search terms, and phrases; and

representing all any of search terms, and phrases in a single cluster with a single search term identifier.

4. The method of claim 3, further comprising:

measuring the similarity between two given any of the search terms, and phrases, expressed in terms of semantic distance, as;

Similarity(ST1, ST2)=Semantic_Distance((ST1, ST2)); and

applying the clustering technique with the pair-wise distance between the any of search terms, and phrases to obtain clusters of the any of search terms, and phrases.

5. The method of claim 1, further comprising:

semantically representing each any of search terms, and phrases by top k nodes, paths, and edges in a particular weighted sub-graph.

6. The method of claim 5, further comprising:

using a Jacquard coefficient of the top k nodes, paths, and the edges to obtain similarity between any of search terms, and phrases.

7. The method of claim 6, further comprising:

calculating top k nodes for the any of search term, and phrase (ST1) as follows;

from a weighted sub-graph of any of search term, and phrase ST1, listing all the edges with their weights;

listing all nodes in the listed edges with weights;

sorting all nodes in said list in descending order of their weights; and

returning top k nodes from the above sorted list;

calculating top k edges for ST1 as follows;

from said weighted sub-graph of any of search term, and phrase ST1, listing all edges with their weights;

sorting all listed edges in descending order of their edges;

returning top k edges; and

calculating top k paths for the any of search term, and phrase ST1 as follows;

from said weighted sub-graph of any of search term, and phrase ST1, listing all edges with their weights;

in said weighted sub-graph, inversing all of the weights;

for each combination of nodes in said weighted sub-graph, calculating a shortest path;

sorting all calculated shortest paths in descending order of their total weight; and

returning the top k paths.

8. The method of claim 1, further comprising:

using Levenshtein distance to calculate the similarity between any of search terms, and phrases.

9. The method of claim 1, further comprising:

pre-processing said any of search terms, and phrases in a two-step process in which any of search term, and phrase normalization is followed by finger-keying.

10. The method of claim 9, wherein said any of search term, and phrase normalization further comprises:

lower casing the any of search terms and phrases; and

removing all punctuation marks except spaces.

11. A computer-implemented search method, comprising:

providing a processor executing instructions for;

receiving, from a user, a search request including any of the search terms, and phrases;

pre-processing the any of search terms and phrases, in a two-step process in which any of search terms, and phrases normalization is followed by finger-keying, wherein said finger-keying comprises;

taking each of the any of search terms, and phrases, and splitting it by space to obtain search words;

lemmatizing each of the any of search terms, and phrases for each search word to obtain a list of lemmatized search words;

sorting the above list in alphabetic order;

clubbing the search words separated by space to obtain finger key form; and

taking a Levenshtein distance between finger-keys of the any of search terms, and phrases to get a pair-wise distance between the any of search terms, and phrases;

using syntactic measures, and semantic measures to determine a similarity metric between the any of search terms, and phrases, received from the user and the any of search terms, and phrases entered by others, wherein said syntactic measures analyze lexical aspects of the any of search terms, and phrases, and said semantic measures consider user activity;

using a clustering technique to cluster said any of search terms, and phrases received from the user within the any of search terms, and phrases entered by others in view of the Levenshtein distance and the similarity metric based on the pair-wise distance of said any of search terms, and phrases;

determining a search result, wherein said determination includes determining the cluster associated the search request;

generating a list of search results, the list of search results being based on an increased quantity of unique search terms or phrases associated with the cluster generated using the search request, and representing an ordered list of search results in response to the search request; and

displaying the search results representing optimized search results in response to the search request.

17. The method of claim 11, wherein said any of search term and phrase normalization further comprises:

lower casing the any of search term and phrase; and

removing all punctuation marks except spaces.

12. A search apparatus, comprising:

a processor executing instructions for;

receiving, from a user, a search request including any of search terms, and phrases;

using syntactic and semantic measures to determine a similarity metric between the any of search terms, and phrases received from the user and the any of search terms, and phrases entered by others, wherein said syntactic measures analyze lexical aspects of said any of search terms, and phrases, and said semantic measures consider user activity;

using a clustering technique to cluster said any of search terms, and phrases received from the user within the any of search terms, and phrases entered by others in view of said similarity metric based on a pair-wise distance of said any of search terms, and phrases;

generating a weighted sub-graph of a website based on the similarity of said any of search terms, and phrases, said sub-graph assigning weights to Web journey choices based on Web journeys made by others who conduct searches with similar any of search terms, and phrases, wherein a graph is a linkage structure of nodes, wherein in a website, each page is a node in a website graph and an edge is a hyperlink from one page to another page, wherein at least one edge has weight, wherein if the graph has weighted edges, then the graph is a weighted graph, wherein a path is a sequence of nodes in the graph, wherein said weighted sub-graph comprises the weighted graph with sub-structure of a given website, wherein said weights represent how many times all users visit from one page to another page after searching a particular any of search terms, and phrases either internally or externally, on the website;

determining search results, wherein said determination includes determining the cluster associated the search request, and determining a highest weight of the weighted sub-graph weights associated with the any of search terms, and phrases of the cluster associated with the search request;

generating a list of search results, the list of search results being based on an increased quantity of unique search terms or phrases associated with the cluster generated using the search request, and being ordered by the highest weight of the weighted sub-graph weights; and

displaying the list of search results representing optimized search results in response to the search request.

14. The search apparatus of claim 12, further comprising:

semantically representing each of said any of search term, and phrases by top k nodes, paths, and edges in a particular weighted sub-graph.

15. The search apparatus of claim 14, further comprising:

using a Jacquard coefficient of the top k nodes, paths, and the edges to obtain similarity between any of search terms and phrases.

16. The search apparatus of claim 15 further comprising:

calculating top k nodes for the search term (ST1) as follows;

from a weighted sub-graph of any of search term, and phrase ST1, listing all the edges with their weights;

listing all nodes in the above listed edges with weights;

sorting all nodes in said list in descending order of their weights; and

returning the top k nodes from the above sorted list;

calculating top k edges for ST1 as follows;

from said weighted sub-graph of any of search term, and phrase ST1, listing all edges with their weights;

sorting all listed edges in descending order of their edges;

returning the top k edges; and

calculating top k paths for the any of search term, and phrase ST1 as follows;

from said weighted sub-graph of any of search term, and phrase ST1, listing all edges with their weights;

in said weighted sub-graph, inversing all of the weights;

for each combination of nodes in said weighted sub-graph, calculating a shortest path;

sorting all calculated shortest paths in descending order of their total weight; and

returning the top k paths.

18. The search apparatus of claim 12, further comprising:

pre-processing said search terms in a two-step process in which any of search terms, and phrases normalization is followed by finger-keying; and

wherein said search term normalization further comprises lower casing the any of search terms and phase and removing all punctuation marks except spaces.

13. A search apparatus, comprising:

a processor executing instructions for;

receiving, from a user, a search request including any of search terms, and phrases;

pre-processing said any of search terms and phrases in a two-step process in which any of search term and phrase normalization is followed by finger-keying, wherein said finger-keying comprises;

taking each any of search terms and phrases, and splitting it by space to obtain search words;

lemmatizing each of any of search terms, and phrase for each search word to obtain a list of lemmatized search words;

sorting the above list in alphabetic order;

clubbing the search words separated by space to obtain finger key form; and

taking a Levenshtein distance between finger-keys of any of the search terms and phrases to get a pair-wise distance between the any of the search terms and phrases;

using syntactic measures, and semantic measures to determine a similarity metric between the any of search terms, and phrases received from the user and the any of the search terms, and phrases entered by others, wherein said syntactic measures analyze lexical aspects of said search terms, and phrases, and said semantic measures consider user activity;

using a clustering technique to cluster the any of search terms, and phrases received from the user within the any of search terms, and phrases entered by others in view of the Levenshtein distance and the similarity metric based on the pair-wise distance of said any of search terms, and phrases;

determining a search result, wherein said determination includes determining the cluster associated the search request;

generating a list of search results, the list of search results being based on an increased quantity of unique search terms or phrases associated with the cluster generated using the search request, and results representing an ordered list of search results in response to the search request; and

displaying the search results representing optimized search results in response to the search request.

19. The search apparatus of claim 13, wherein said any of search terms, and phrases normalization further comprises:

lower casing the any of search terms and phrases; and

removing all punctuation marks except spaces.