Method for fast large scale data mining using logistic regression

• US 7,636,715 B2
• Filed: 03/23/2007
• Issued: 12/22/2009
• Est. Priority Date: 03/23/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kalleh, Omid Rouhani
• Primary Examiner(s): Ali; Mohammad
• Assistant Examiner(s): Shanmugasundaram; Kannan
• Application Number:
  US11/690,328
• Publication Number:
  US 20080235208A1
• Time in Patent Office: 1,005 Days
• Field of Search: 707 1- 5, 707/7, 707/101, 707/100
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A classifier using a logistic regression technique permits previously acquired search results to be used to perform a new search. A user inputs search terms and queries a database of previous search results. A logistical regression calculation is performed using sets of data such that the time execution performance is at least a factor of 10 improvement over a conventional technique. In our experiments where real world data was used, the execution time was reduced up to 353 times as compared to the conventional technique. The Iteratively Reweighted Least Squares (IRLS) method is used for the logistical regression method and beta vector values are calculated from the database data set. A vector of the user input terms is multiplied by the beta vector values to produce an ordered list of documents satisfying the user search terms.

Claims

1. A computer-implemented method of using previously acquired search results to perform a new search using a computer, the method comprising:

accessing a database of search terms and user selection clicks on retrieved documents;

calculating a matrix X, wherein matrix X is defined as a matrix having rows corresponding to rows of the database and columns corresponding to search terms in the database row;

calculating a vector Y, wherein Y is defined as a representation of a document chosen by a user corresponding to a row of the database;

calculating B vector values using the X matrix, the Y vector, and an iteratively reweighted least squares (IRLS) method, where the IRLS method executes in a time proportional to a time complexity function of O(d*k*k+i_max*a²), where k is the average number of nonzero elements per row in X, d is the number of data point rows in X, a is the number of columns in X and i_max is a constant;

storing the B vectors;

receiving a new set of search terms and generating a corresponding search vector z;

calculating the dot product of B and z to produce weighted scalar values of relevant documents in the database; and

ordering the relevant documents in the database using the weighted scalar values; and

displaying, on a computer monitor, an ordered list of the relevant documents corresponding to the new set of search terms;

wherein the X matrix is a binary matrix wherein a value of 1 represents that a particular keyword was used; and

wherein the Y vector comprises a binary vector wherein a 1 value represents that a particular document was selected by a user.

2. The method of claim 1, wherein one Y vector is calculated for every row represented in the database.

3. The method of claim 2, wherein calculating the B vector further comprises calculating one B vector for every Y vector that is calculated.

4. The method of claim 1, wherein the calculation of the B vector executes at least one order of magnitude in time faster than a standard base algorithm.

5. The method of claim 1, wherein storing the B vectors represents pre-calculating the B vectors so that the B Vectors are available for access after a user enters keywords to perform a search.

6. The method of claim 1, wherein the display is one of an electronically driven display and a printed display.

7. The method of claim 1, further comprising providing the ordered list of the relevant documents to a subsequent process.

8. In a system comprising a database of keywords and corresponding related documents and computer that uses a logistic regression algorithm to search the database using user keywords, the improvement comprising:

a processor for calculating B vector values using an X matrix, a Y vector, and an iteratively reweighted least squares (IRLS) algorithm, wherein the X matrix is defined as a matrix having rows corresponding to rows of the database and columns corresponding to search terms in the database rows, wherein the Y vector is defined as a representation of a document chosen by a user corresponding to a row of the database, and where the IRLS method executes in a time proportional to a time complexity function of O(d*k*k+i_max*a²), where k is the average number of nonzero elements per row in X, d is the number of data point rows in X, a is the number of columns in X and i_max is a constant;

storage means for storing the B vectors for use in association with a new user query;

an input interface for receiving a new set of search terms and generating a corresponding search vector z;

the processor also calculating weighted scalar values of relevant documents in the database in response to the query; and

ordering the relevant documents in the database using the weighted scalar values for display to the user; and

wherein the X matrix is a binary matrix wherein a value of 1 represents that a particular keyword was used, and wherein the Y vector comprises a binary vector wherein a 1 value represents that a particular document was selected by a user.

9. The system of claim 8, wherein calculating the B vectors further comprises calculating one B vector for every Y vector that is calculated.

10. The system of claim 8, wherein calculating B vectors is performed in a manner that executes at least one order of magnitude in time faster than using a standard base algorithm for B vector calculation.

11. The system of claim 8, further comprising a display device for displaying the weighted scalar values to the user.

12. A computer-readable storage medium having computer-executable instructions for performing a search of a database of keywords and relevant documents, the computer -executable instructions comprising:

calculating a matrix X, wherein matrix X is defined as a matrix having rows corresponding to rows of the database and columns corresponding to search terms in the database row;

calculating a vector Y, wherein Y is defined as a representation of a document chosen by a user corresponding to a row of the database;

calculating and storing B vector values using the X matrix, the Y vector, and an iteratively reweighted least squares (IRLS) algorithm, where the IRLS method executes in a time proportional to a time complexity function of O(d*k*k+i_max*a²), where k is the average number of nonzero elements per row in X, d is the number of data point rows in X, a is the number of columns in X and i_max is a constant;

receiving a new set of search terms and generating a corresponding search vector z;

multiplying B and z to produce weighted scalar values of relevant documents in the database; and

arranging the relevant documents in the database in an order using the weighted scalar values;

wherein the instructions further comprise assigning a value of 1 to represent that a particular keyword was used in the X matrix and assigning a value of 1 to represent that a particular document was selected by a user in the Y vector.

13. The computer-readable medium of claim 12, wherein the instructions further comprise driving a display to present to the user the weighted scalar values of the relevant documents.

14. The computer-readable medium of claim 12, further comprising an instruction to calculate one Y vector for every row represented in the database.

15. The computer-readable medium of claim 14, further comprising an instruction to calculate one B vector for every Y vector that is calculated.

16. The computer-readable medium of claim 12, wherein instructions for calculating B vector values execute at least one order of magnitude faster in time than instructions for calculating b vector values using a standard base algorithm.