TERM EXTRACTION FROM SERVICE DESCRIPTION DOCUMENTS

• US 20100198839A1
• Filed: 01/30/2009
• Published: 08/05/2010
• Est. Priority Date: 01/30/2009
• Status: Active Grant

• Current Assignee: Micro Focus LLC (Open Text Corporation)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Graupner, Sven, Young, Donald E., Basu, Sujoy, Singhal, Sharad, Ozonat, Mehmet Kivanc
• Granted Patent: US 8,255,405 B2
• Time in Patent Office: Days
• US Class Current: 707/749
• CPC Class Codes: G06F 16/3334 Selection or weighting of terms from queries, including natural language queries
• CPC Class Codes: G06F 16/907 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually

Abstract

Terms are extracted from service description documents describing desired services, and the terms are used to search for candidate service providers operable to provide the desired services. A matrix of terms and documents are determined from the service description documents. Singular value decomposition (SVD) is used to decompose the matrix. Eigen vectors from the SVD decomposition are weighted by top k singular values in a diagonal matrix S of singular values also generated from the decomposition. The weighted eigen vectors are used to rank terms from the matrix X based on relevance of the terms to the requirements for desired services described in the service description documents.

Claims

1. A computer readable medium including code that when executed by a computer system performs a method of selecting most relevant terms from service description documents, the method comprising:

receiving a set of service description documents;

determining a matrix X of terms and documents from the set of service description documents;

decomposing the matrix X using singular value decomposition (SVD) into three matrices T, S, and D^t, wherein S is a diagonal matrix of singular values ordered in descending order, and T and D^t are matrices of eigen vectors;

selecting k singular values from S, where k is an integer greater than or equal to 1;

determining rankings of the terms in the matrix X using the k singular values; and

selecting a set of terms from the matrix X based on the rankings.

2. The computer readable medium of claim 1, wherein the method further comprises:

determining a matrix T_txk containing first k columns of T;

determining a matrix S_kxk containing an intersection of the first k rows and the first k columns of S; and

determining a matrix Y comprised of a product of the matrix T_txk and the matrix S_kxk, wherein the product represents eigen vectors from T weighted by the k singular values in S.

3. The computer readable medium of claim 2, wherein the method further comprises:

determining a maximum absolute value associated with each term in the matrix Y, wherein the maximum absolute value represents a relevance of the corresponding term to a service description in one or more of the service description documents; and

determining rankings of the terms in the matrix X includes using the maximum absolute values to determine the rankings.

4. The computer readable medium of claim 3, wherein selecting a set of terms from the matrix X based on the rankings further comprises:

sorting the terms of the matrix Y based on their maximum absolute values; and

selecting terms having maximum absolute values exceeding a term relevance threshold.

5. The computer readable medium of claim 1, wherein the matrix X is a term-by-document matrix and a dimension of the matrix X is t number of terms by d number of documents.

6. The computer readable medium of claim 1, wherein selecting k singular values from S further comprises:

selecting k singular values from S having values greater than a first threshold.

7. The computer readable medium of claim 1, further comprising:

using the set of terms to identify candidate service providers for one or more services described in the set of service description documents.

8. The computer readable medium of claim 1, wherein multiple documents in the set of service description documents is generated from a single service description document.

9. The computer readable medium of claim 1, wherein the method further comprises:

normalizing the set of service description documents to a single format.

10. A computer readable medium including code that when executed by a computer system performs a method comprising:

receiving a set of service description documents describing requirements for one or more desired services;

determining a term-by-document matrix X from the set of documents, wherein a dimension of the matrix X is t number of terms by d number of documents;

using SVD to determine matrices T, S, and D^t, wherein S is a diagonal matrix of singular values ordered in descending order, and T and D^t are matrices of eigenvectors;

selecting top k singular values from S;

determining eigen vectors from T weighted by the top k singular values in S; and

using the weighted eigen vectors to rank terms from the matrix X based on relevance of the terms to the requirements for one or more desired services in the set of documents.

11. The computer readable medium of claim 10, wherein the method further comprises:

determining a matrix T_txk containing first k columns of T;

determining a matrix S_kxk containing an intersection of the first k rows and the first k columns of S; and

determining a matrix Y comprised of a product of the matrix T_txk and the matrix S_kxk, wherein the product is a matrix of the weighted eigen vectors.

12. The computer readable medium of claim 11, wherein the method further comprises:

determining a maximum absolute value in each row of the matrix Y associated with a term of the matrix X, wherein the maximum absolute value in each row represents a relevance of a corresponding term for the row; and

the ranks of the terms in the matrix X include ranks determined from the maximum absolute values.

13. The computer readable medium of claim 12, wherein the method further comprises:

sorting the rows of the matrix Y based on their maximum absolute values; and

selecting terms for the rows having maximum absolute values exceeding a threshold.

14. The computer readable medium of claim 13, wherein the method further comprises:

using the selected terms to identify candidate service providers for one or more services described in the set of service description documents.

15. The computer readable medium of claim 10, wherein multiple documents in the set of service description documents is generated from a single service description document.

16. The computer readable medium of claim 10, wherein the method further comprises:

normalizing the set of service description documents to a single format.

17. A computer system comprising:

an interface receiving a set of service description documents; and

one or more processors executing code to perform a method including

determining a term-by-document matrix X from the set of service description documents, wherein a dimension of the matrix X is t number of terms by d number of documents;

decomposing the matrix X using singular value decomposition (SVD) into three matrices T, S, and D^t, wherein S is a diagonal matrix of singular values ordered in descending order, and T and D^t are matrices of eigen vectors;

selecting top k singular values in S, where k is less than a total number of non-zero singular values in S;

determining eigen vectors from T weighted by the top k singular values in S; and

using the weighted eigen vectors to rank terms from the matrix X based on relevance of the terms to the requirements for one or more desired services in the set of documents.

18. The computer system of claim 17, wherein the method further comprises:

determining a matrix T_txk containing first k columns of T;

determining a matrix S_kxk containing an intersection of the first k rows and the first k columns of S; and

determining a matrix Y comprised of a product of the matrix T_txk and the matrix S_kxk, wherein the product is a matrix of the weighted eigen vectors.

19. The computer system of claim 18, wherein the method further comprises:

determining a maximum absolute value in each row of the matrix Y associated with a term of the matrix X, wherein the maximum absolute value in each row represents a relevance of a corresponding term for the row; and

the ranks of the terms in the matrix X include ranks determined from the maximum absolute values.

20. The computer system of claim 19, wherein the method further comprises:

sorting the rows of the matrix Y based on their maximum absolute values; and

selecting terms for the rows having maximum absolute values exceeding a threshold.