Source: http://www.google.com/patents/US20060242190?dq=5,912,661
Timestamp: 2017-10-22 03:06:45
Document Index: 726241833

Matched Legal Cases: ['§ 119', '§ 119', 'art 100', 'art 100', 'Application No. 60', 'art 300', 'art 300', 'art 500', 'arts 100', 'arts 100']

Patent US20060242190 - Latent semantic taxonomy generation - Google Patents
A method for automatically constructing a taxonomy for a collection of documents. For a given collection of documents, a method in accordance with an embodiment of the present invention creates document clusters, assigns taxons (titles) to the clusters, and organizes the clusters in a hierarchy. The...http://www.google.com/patents/US20060242190?utm_source=gb-gplus-sharePatent US20060242190 - Latent semantic taxonomy generation
Publication number US20060242190 A1
Application number US 11/431,634
Publication number 11431634, 431634, US 2006/0242190 A1, US 2006/242190 A1, US 20060242190 A1, US 20060242190A1, US 2006242190 A1, US 2006242190A1, US-A1-20060242190, US-A1-2006242190, US2006/0242190A1, US2006/242190A1, US20060242190 A1, US20060242190A1, US2006242190 A1, US2006242190A1
Original Assignee Content Analyst Comapny, Llc
Patent Citations (35), Referenced by (106), Classifications (9), Legal Events (1)
US 20060242190 A1
A method for automatically constructing a taxonomy for a collection of documents. For a given collection of documents, a method in accordance with an embodiment of the present invention creates document clusters, assigns taxons (titles) to the clusters, and organizes the clusters in a hierarchy. The clusters in the hierarchy are ordered from general to specific in the depth of the hierarchy, and from most similar to least similar in the breadth of the hierarchy. This method is capable of producing meaningful classifications in a short time.
1. A computer-based method for automatically constructing a taxonomy for a collection of documents, comprising:
(a) generating a representation of each document in the collection of documents in a conceptual representation space;
(b) identifying a set of document clusters in the collection of documents based on a conceptual similarity among the representations of the documents; and
(c) generating a taxon for a document cluster in the set of document clusters based on at least one of (i) a term in a document of at least one of the document clusters, or (ii) a term represented in the conceptual representation space.
generating a latent semantic indexing (LSI) space based on the collection of documents, wherein each document in the collection of documents has a vector representation in the LSI space.
identifying a set of exemplary documents in the collection of documents; and
identifying the set of document clusters based on the set of exemplary documents.
identifying a set of document clusters in the collection of documents based on a conceptual similarity among the representations of the documents, wherein the documents in each document cluster are sorted based on a similarity measurement, and wherein the document clusters are sorted based on a number of documents included in each document cluster.
(c1) identifying candidate terms for a document cluster in the set of document clusters;
(c2) selecting a subset of the candidate terms for the document cluster based on an evaluation scheme; and
(c3) generating a taxon for the document cluster based on the subset of candidate terms.
6. The method of claim 5, wherein step (c1) comprises:
identifying candidate terms for a document cluster in the set of document clusters based on a frequency of occurrence of distinct terms contained in at least one document of the document cluster.
7. The method of claim 5, wherein step (c1) comprises:
generating a representation for a document cluster in the set of document clusters in the conceptual representation space;
computing a similarity measure between the representation of the document cluster and the representation of each term represented in the conceptual representation space; and
identifying candidate terms for the document cluster based on the similarity measure.
8. The method of claim 5, wherein each document cluster includes distinct terms, and wherein step (c2) comprises:
selecting a candidate term as a member of the subset of the candidate terms of the document cluster if a similarity measure between a representation of the document cluster and a representation of the candidate term is above a similarity-threshold.
9. The method of claim 5, wherein step (c2) comprises:
selecting a subset of the candidate terms of the document cluster based on a number of generalized entities in the candidate terms of the document cluster.
10. The method of claim 5, wherein step (c2) comprises:
selecting a subset of the candidate terms for the document cluster based on a comparison of the frequency of occurrence of a candidate term in the document cluster to the frequency of occurrence of the candidate term in the other document clusters in the set of document clusters.
11. The method of claim 5, wherein step (c3) comprises:
generating a taxon for the document cluster based on an overlap between the candidate terms in the subset of candidate terms.
12. A computer program product comprising a computer usable medium having computer readable program code stored therein that causes an application program for automatically constructing a taxonomy for a collection of documents to execute on an operating system of a computer, the computer readable program code comprising:
computer readable first program code that causes the computer to generate a representation of each document in the collection of documents in a conceptual representation space;
computer readable second program code that causes the computer to identify a set of document clusters in the collection of documents based on a conceptual similarity among the representations of the documents; and
computer readable third program code that causes the computer to generate a taxon for a document cluster in the set of document clusters based on at least one of (i) a term in a document of at least one of the document clusters, or (ii) a term represented in the conceptual representation space.
13. The computer program product of claim 12, wherein the computer readable first program code comprises:
code that causes the computer to generate a latent semantic indexing (LSI) space based on the collection of documents, wherein each document in the collection of documents has a vector representation in the LSI space.
14. The computer program product of claim 12, wherein the computer readable second program code comprises:
code that causes the computer to identify a set of exemplary documents in the collection of documents; and
code that causes the computer to identify the set of document clusters based on the set of exemplary documents.
15. The computer program product of claim 12, wherein the computer readable second program code comprises:
code that causes the computer to identify a set of document clusters in the collection of documents based on a conceptual similarity among the representations of the documents, wherein the documents in each document cluster are sorted based on a similarity measurement, and wherein the document clusters are sorted based on a number of documents included in each document cluster.
16. The computer program product of claim 12, wherein the computer readable third program code comprises:
computer readable fourth program code that causes the computer to identify candidate terms for a document cluster in the set of document clusters;
computer readable fifth program code that causes the computer to select a subset of the candidate terms for the document cluster based on an evaluation scheme; and
computer readable sixth program code that causes the computer to generate a taxon for the document cluster based on the subset of candidate terms.
17. The computer program product of claim 16, wherein the computer readable fourth program code comprises:
code that causes the computer to identify candidate terms for a document cluster in the set of document clusters based on a frequency of occurrence of distinct terms contained in at least one document of the document cluster.
18. The computer program product of claim 16, wherein the computer readable fourth program code comprises:
code that causes the computer to generate a representation for a document cluster in the set of document clusters in the conceptual representation space;
code that causes the computer to compute a similarity measure between the representation of the document cluster and the representation of each term represented in the conceptual representation space; and
code that causes the computer to identify candidate terms for the document cluster based on the similarity measure.
19. The computer program product of claim 16, wherein each document cluster includes distinct terms, and wherein the computer readable fifth program code comprises:
code that causes the computer to select a candidate term as a member of the subset of the candidate terms of the document cluster if a similarity measure between a representation of the document cluster and a representation of the candidate term is above a similarity-threshold.
20. The computer program product of claim 16, wherein the computer readable fifth program code comprises:
code that causes the computer to select a subset of the candidate terms of the document cluster based on a number of generalized entities in the candidate terms of the document cluster.
21. The computer program product of claim 16, wherein the computer readable fifth program code comprises:
code that causes the computer to select a subset of the candidate terms for the document cluster based on a comparison of the frequency of occurrence of a candidate term in the document cluster to the frequency of occurrence of the candidate term in the other document clusters in the set of document clusters.
22. The computer program product of claim 16, wherein the computer readable sixth program code comprises:
code that causes the computer to generate a taxon for the document cluster based on an overlap between the candidate terms in the subset of candidate terms.
This application claims benefit under 35 U.S.C. § 119(e) to U.S. Provisional Patent Application 60/681,945, entitled “Latent Semantic Taxonomy Generation,” to Wnek, filed on May 18, 2005. This application is also a continuation-in-part of U.S. patent application Ser. No. 11/262,735, entitled “Generating Representative Exemplars for Indexing, Clustering, Categorization, and Taxonomy,” to Wnek and filed Nov. 1, 2005, which claims benefit under 35 U.S.C. § 119(e) to U.S. Provisional Patent Application 60/674,706, entitled “Generating Representative Exemplars for Indexing, Clustering, Categorization, and Taxonomy,” to Wnek, filed on Apr. 26, 2005. The entirety of each of the foregoing applications is hereby incorporated by reference as if fully set forth herein.
A taxonomy is a hierarchical classification of objects. At the root of the hierarchy is a single classification of all objects. Nodes below the root provide classifications of subsets of objects. The objects in the subsets are grouped according to some selected object properties. In constructing a taxonomy, these properties allow grouping of similar objects and distinguishing these objects from others. In applying a taxonomy to classify objects, the properties allow identification of proper groups to which the objects belong.
One of the best-known taxonomies is the taxonomy of living things that was originated by Carl Linnaeus in the 18th century. In his taxonomy of plants, Linnaeus focused on the properties of flower parts, which are least prone to changes within the category. This taxonomy enabled his students to place a plant in a particular category effortlessly.
Linnaean taxonomies came into use during a period when the abundance of the world's vegetation was being discovered at a rate that exceeded the regular means of analyzing and organizing the newly found species. In the current age of information, information from a variety of media sources and formats is being generated at a rate that exceeds the current means for investigating, organizing and classifying this information. Content analysis has become critical for both human advancement and security. The rapid identification and classification of threats has become a priority for many agencies and, therefore, new taxonomies of security related information are sought in order to quickly recognize threats and prepare proper responses.
The challenge of analyzing large amounts of information is multiplied by a variety of circumstances, locations and changing identities among the entities involved. It is not feasible to build one classification system capable of meeting all current needs. Constant adaptation is required to accommodate new information as it becomes available. Therefore, what is required is an automated classification system (i.e., a system that learns patterns in an unsupervised fashion and organizes its knowledge in a comprehensive way) for detecting new patterns and providing specific and understandable leads.
According to an embodiment of the present invention there is provided a method and system for automatically constructing a taxonomy for a collection of documents. The method and system provide means for detecting new patterns and providing specific and understandable leads.
The method comprises the following steps. First, a representation for each document in the collection of documents is generated in a conceptual representation space. Second, a set of document clusters is identified based on a conceptual similarity among the representations of the documents. Then, a taxon (title) is generated for a document cluster in the set of document clusters based on at least one of (i) a term in a document of at least one of the document clusters, or (ii) a term represented in the conceptual representation space.
According to another embodiment of the present invention, there is provided a computer program product including a computer usable medium having computer readable program code stored therein that causes an application program for automatically constructing a taxonomy for a collection of documents to execute on an operating system of a computer. The computer readable program code includes computer readable first, second, and third program code. The computer readable first program code causes the computer to generate a representation of each document in the collection of documents in a conceptual representation space. The computer readable second program code causes the computer to identify a set of document clusters in the collection of documents based on a conceptual similarity among the representations of the documents. And, the computer readable third program code causes the computer to generate a taxon for a document cluster in the set of document clusters based on at least one of (i) a term in a document of at least one of the document clusters, or (ii) a term represented in the conceptual representation space.
FIG. 1 depicts a flowchart of a method for automatically generating a taxonomy for a collection of documents in accordance with an embodiment of the present invention.
FIG. 12 depicts a flowchart of a method for generating a taxon (title) for a document cluster in the set of document clusters in accordance with an embodiment of the present invention.
FIG. 13 is a block diagram of a computer system on which an embodiment of the present invention may be executed.
C. Pseudo-Code Representation of an Algorithm in Accordance with an Embodiment of the Present Invention
IV. Example Method for Automatically Clustering Documents Based on a Similarity Measure in Accordance with an Embodiment of the Present Invention
V. Taxon Generation
A. Overview of Taxon Generation
B. Example Method for Automatically Constructing a Taxon in Accordance with an Embodiment of the Present Invention
C. Example of a Taxonomy Generated in Accordance with an Embodiment of the Present Invention
VII. Example Graphical User Interface
VIII. Example Capabilities and Applications
An embodiment of the present invention provides a method for generating a taxonomy for a collection of documents by utilizing representations of the documents in a conceptual representation space, such as an abstract mathematical space. For example, the conceptual representation space can be a Latent Semantic Indexing (LSI) indexing space, as described in U.S. Pat. No. 4,839,853 entitled “Computer Information Retrieval Using Latent Semantic Structure” to Deerwester et al., the entirety of which is incorporated by reference herein. The LSI technique enables representation of textual data in a vector space, facilitates access to all documents and terms by contextual queries, and allows for text comparisons. As is described in more detail herein, in accordance with an embodiment of the present invention, for a given collection of documents, a Taxonomy System creates document clusters, assigns taxons (titles) to the clusters, and organizes the clusters in a hierarchy. As used herein, a “taxon” shall mean the name applied to a taxonomic group. Clusters in the hierarchy are ordered from general to specific in the depth of the hierarchy.
The challenge of analyzing large amounts of information is multiplied by a variety of circumstances, locations and changing identities among the entities involved. It is not feasible to build one classification system capable of meeting all current needs. Constant adaptation is required as soon as new information becomes available. Therefore, classification systems require automation for detecting new patterns and providing specific and understandable leads. Automation in this case means that the system learns patterns in an unsupervised fashion and organizes its knowledge in a comprehensive way. Such is the purpose of an automatic Taxonomy System provided in accordance with an embodiment of the present invention.
The Taxonomy System can employ the above-mentioned LSI information retrieval technique to efficiently index all documents required for analysis. LSI was designed to overcome the problem of mismatching words of queries with words of documents, as evident in Boolean-query type retrieval engines. In fact, LSI can be used to find relevant documents that may not even include any of the search terms in a query. LSI uses a vector space model that transforms the problem of comparing textual data into a problem of comparing algebraic vectors in a multidimensional space. Once the transformation is done, the algebraic operations are used to calculate similarities among the original documents, terms, groups of documents and their combinations.
Although the Taxonomy System is described in the context of an LSI-based sorting technique, it is to be appreciated that this is for illustrative purposes only, and not limitation. For example, a person skilled in the relevant art(s) will appreciate from reading the description contained herein that any technique that utilizes a representation of documents (and/or terms) can be employed in the Taxonomy System. Examples of such techniques can include, but are not limited to, the following: (i) probabilistic LSI (see, e.g., Hoffman, T., “Probabilistic Latent Semantic Indexing,” Proceedings of the 22nd Annual SIGIR Conference, Berkeley, Calif., 1999, pp. 50-57); (ii) latent regression analysis (see, e.g., Marchisio, G., and Liang, J., “Experiments in Trilingual Cross-language Information Retrieval,” Proceedings, 2001 Symposium on Document Image Understanding Technology, Columbia, Md., 2001, pp. 169-178); (iii) LSI using semi-discrete decomposition (see, e.g., Kolda, T., and O.Leary, D., “A Semidiscrete Matrix Decomposition for Latent Semantic Indexing Information Retrieval,” ACM Transactions on Information Systems, Volume 16, Issue 4 (October 1998), pp. 322-346); and (iv) self-organizing maps (see, e.g., Kohonen, T., “Self-Organizing Maps,” 3rd Edition, Springer-Verlag, Berlin, 2001). Each of the foregoing cited references is incorporated by reference in its entirety herein.
Input to the Taxonomy System is in the form of a repository of documents indexed by LSI and a set of high-level parameters. Output is in the form of a hierarchy of clusters (e.g., represented in XML), each cluster in the hierarchy having a representative title (taxon). The hierarchy of clusters can include links to the original documents. A recursive clustering process constructs nodes at the consecutive levels of the hierarchy.
FIG. 1 depicts a flowchart 100 illustrating an overview of a method for automatically constructing a taxonomy for a collection of documents in accordance with an embodiment of the present invention. Flowchart 100 begins at a step 110 in which a representation of each document in a collection of documents is generated in a conceptual representation space. For example, the conceptual representation space may be an LSI space, as described in the aforementioned '853 patent, and the documents and terms used for clustering and taxonomy generation represented as pseudo-objects in that space.
An LSI space represents documents as vectors in an abstract mathematical vector space. To generate an LSI space, a collection of text documents is represented in a term-by-document matrix. Representing the text in the term-by-document matrix may involve several steps. First, a pipeline of filters is applied to a collection of documents. Before indexing, the documents are preprocessed by the pipeline of filters. The pipeline may contain filters for stop-word and stop-phrase removal, HTML/XML tagging removal, word stemming, and a pre-construction of generalized entities. A generalized entity is a semantic unit of one or more stemmed words extracted from the documents with the exclusion of stop-words. During the preprocessing, words and word pairs (bi-words) are collected and used in indexing a document repository. Then, a vector representation is generated for each document in the collection of documents. In an embodiment, the collection of documents that is used to generate the LSI space is the collection of documents for which a taxonomy is to be generated. In another embodiment, a first collection of documents is used to generate the LSI space, then each document in a second collection of documents is represented in the LSI space and a taxonomy is generated for the second collection of documents. Additionally or alternatively, a combination of these embodiments may be used to generate an LSI space, as would be apparent to a person skilled in the relevant art(s).
Referring again to FIG. 1, in a step 120, a set of document clusters is identified based on a conceptual similarity among the representations of the documents. In an embodiment, the implementation of step 120 may include several steps, as illustrated in FIG. 2. Referring to FIG. 2, in a step 210, representative seed exemplars are identified. Representative seed exemplars are documents about which other documents cluster. An example method for identifying representative seed exemplars is described below in Section II and in commonly-owned U.S. patent application Ser. No. 11/262,735, entitled “Generating Representative Exemplars for Indexing, Clustering, Categorization and Taxonomy,” filed Nov. 1, 2005, the entirety of which is incorporated by reference herein. In a step 220, specific and non-overlapping clusters are constructed. An example method for constructing specific and non-overlapping clusters is described in more detail below in Section III and in commonly-owned U.S. Provisional Patent Application No. 60/680,489, entitled “Latent Semantic Clustering,” filed May 13, 2005, the entirety of which is incorporated by reference herein. In addition, the documents within a document cluster may be sorted based on a similarity measurement as described in more detail below in Section IV. For example, the similarity measurement may compare the similarity of each document in a document cluster to a representative document of that document cluster. Furthermore, the document clusters may be sorted according to a sorting scheme. For example, the sorting scheme may sort the document clusters based on a number of documents included in each cluster.
In a step 130, a taxon is generated for a document cluster in the set of document clusters based on terms in at least one document of the document cluster. An example method for generating taxons for the document clusters in accordance with an embodiment of the present invention is described in more detail in Section V.
The Taxonomy System introduced above, and various embodiments thereof, will now be described in more detail.
As mentioned above with respect to step 210 of FIG. 2, an embodiment of the present invention can be used to automatically identify seed exemplars. First, an overview of identifying seed exemplars is given. Second, an example method for identifying seed exemplars is presented. Then, an example application is described.
FIG. 3 illustrates a flowchart 300 of a general method for automatically selecting exemplary documents from a collection of documents in accordance with an embodiment of the present invention. The collection of documents can include a large number of documents, such as 100,000 documents or some other large number of documents. As was mentioned above, and as is described below, the exemplary documents can be used for generating an index, a cluster, a categorization, a taxonomy, or a hierarchy. In addition, selecting exemplary documents can reduce the number of documents needed to represent the conceptual content contained within a collection of documents, which can facilitate the performance of other algorithms, such as an intelligent learning system.
As shown in FIG. 4, an angle {acute over (α)}12 between D1 and D2 is greater than an angle {acute over (α)}23 between D2 and D3. Since angle {acute over (α)}23 is smaller than angle {acute over (α)}12, the cosine of {acute over (α)}23 will be larger than the cosine of {acute over (α)}12. Accordingly, in this example, the document represented by vector D2 is more conceptually similar to the document represented by vector D3 than it is to the document represented by vector D1.
In a step 340, at least one exemplary document is identified for each cluster. In an embodiment, a single exemplary document is identified for each cluster. In an alternative embodiment, more than one exemplary document is identified for each cluster. As mentioned above, the exemplary documents represent exemplary concepts contained within the collection of documents.
To summarize, by setting the clustering threshold relatively high, major concepts contained within the collection of documents will be represented by an exemplary document. From the example above, by setting the clustering threshold to four, the concept of golf would be represented by an exemplary document, but the concept of space travel would not. Alternatively, by setting the clustering threshold relatively low, all concepts contained within the collection of documents would be represented by an exemplary document. From the example above, by setting the clustering threshold to one, each of the concepts of golf and space travel would respectively be represented by an exemplary document.
As mentioned above, the exemplary documents can be used to generate non-intersecting clusters of conceptually similar documents. The clusters identified in step 330 of flowchart 300 are not necessarily non-intersecting. For example, a first cluster of documents can include a subset of documents about golf and a second cluster of documents may also include this same subset of documents about golf. In this example, the exemplary document for the first collection of documents and the exemplary document for the second collection of documents can be used to generate non-intersecting clusters, as described in more detail below in Section III. By generating non-intersecting clusters, only one cluster would include the subset of documents about golf.
The method of flowchart 500 will now be described in detail. As shown in FIG. 5A, the method is initiated at step 502 and immediately proceeds to step 504. At step 504, all documents in a collection of documents D are indexed in accordance with the LSI technique and are assigned a vector representation in the LSI space. The LSI technique is well-known and its application is fully explained in the aforementioned '853 patent. Alternatively, the collection of documents may be indexed using the LSI technique prior to application of the present method. In this case, step 504 may merely involve opening or otherwise accessing the stored collection of documents D. In either case, each document in the collection D is associated with a unique document identifier (ID).
1. open collection (DOCS) of documents to be clustered
2. D
3. uselessSeeds
empty // Docs not creating useful clusters
4. usefulSeeds
empty // Cached seed descriptions
5. clusteredDocs
empty // Processed documents
6. initSIM
7. stopSIM
8. stepSIM
9. for similarity levels (sim) from initSIM to stopSIM decrement by
10. initDISIM
11. stopDISIM
12. stepDISIM
13. for dissimilarity levels (disim) from initDISIM to stopDISIM
increment by stepDISIM
14. for all documents (d) in D: d in rawSeeds and not in
17. if (d in usefulSeeds) then
(Seed) usefulSeeds.get(d)
19. // Is this seed potentially useful at this similarity level
20. if sd.level < sim then continue
23. // Find max similarity (dissimilarity) of d to already created
24. d_clusters
Similarity(clusters, d)
25. // Could d be useful for any acceptable dissimilarity level?
26. if (d_clusters > stopSIM)
27. uselessSeeds.add(d) // Never useful
28. continue
30. if (d_clusters > disim)
31. retry.add(d) // May be useful at less restricted
32. continue
35. // Document d creates cluster that is sufficiently distant from
36. if (sd = null) then
37. vd
vector representation of document d
38. rs
select docid,cosine(vd) from DOCS where cos( )>0.35
new Seed(rs, MIN_CLUSTER)
42. // Evaluate the quality of this seed at the current requirements
43. // 1. Will size of the cluster ever exceed the minimum?
44. if (sd.getCount(stopSIM) < MIN_CLUSTER) then
45. uselessSeeds.add(d)
46. continue
48. usefulSeeds.put(d, sd) // Cache the useful seed
50. // 2. Is the size sufficient for the current similarity level ?
51. if (sd.getCount(sim) < MIN_CLUSTER) then continue
53. // 3. Is this cluster disjoint from other clusters? Any docs
54. if ( overlaps(d, clusters) ) then
55. uselessSeeds.add(d)
56. continue
57. end if
59. // Document d creates sufficiently large cluster for this
similarity (sim) and the cluster does not overlap any previously
created clusters
60. // Add cluster created by document d to the set of clusters, and
61. // assume all documents in the cluster as processed
62. clusters.add(sd.cluster)
63. clusteredDocs.addAll(sd.cluster)
64. end for // all documents in D
66. end for // dissimilarity levels to other clusters
67. end for // similarity of documents in the constructed cluster
The SimSort algorithm assumes that every document has a vector representation and that there exists a measure for determining similarity between document vectors. For example, each document can be represented as a vector in an abstract mathematical vector space (such as an LSI space), and the similarity can be a cosine similarity between the vectors in the abstract mathematical vector space. SimSort constructs a collection of cluster nodes. Each node object contains document identifiers of similar documents. In one pass through all the documents, every document is associated with one of two mappings—a “cluster” map or an “assigned” map. The “cluster” map contains the identifiers of documents for which a most similar document was found and the similarity exceeds a threshold, such as a cosine similarity threshold. The “assigned” map contains the identifiers of documents which were found most similar to the “cluster” documents or to the “assigned” documents.
2. assigned <- empty // Map (assigned) docs to cluster nodes
3. clusters <- empty // Map (seed) docs to cluster nodes
4. other <- empty // Special node with docs not forming
5. for (i=0; i < DOCS.size; i++) do
6. if (i in assigned) then continue;
7. select document di
8. select document dj from DOCS that is most similar to di (but
9. if ( similarity(di, dj) < COS) {// This document does not form
10. other.add(i);
11. assigned.put(i, other);
12. continue; }
13. if(j in assigned) then {
14. node = assigned.get(j);
15. node.add(i); // add doc i to node
16. assigned.put(i, node); // map this node from doc
17. continue; }
18. if (i > j) then { // j in clusters
19. node = clusters.get(j);
20. node.add(i); // add doc i to node
21. assigned.put(i, node); // map this node from doc
22. continue; }
23. // i < j, i.e. j never tested before. Initialize new cluster node
24. create new node;
25. node.add(i); // add doc i to the new node
26. clusters.put(i, node); // map this node from doc i
27. node.add(j); // add doc j to the new node
28. assigned.put(j, node); // map this node from doc j
29. continue for loop;
30. Sort clusters according to their sizes.
31. Optional: trim small clusters, and add documents from trimmed
32. Optional: trim to the maximum number of clusters, and add documents
from trimmed clusters to the ‘other’ node.
33. Optional: classify the ‘other’ documents to clusters.
After processing all the documents in the collection, the clusters are sorted by size in accordance with line 30. In the example from above, the cluster created by document 2 will be sorted higher than the cluster created by document 1 because the cluster created by document 2 includes four documents (namely, documents 2, 3, 5 and 6), whereas the cluster created by document 1 only includes three documents (namely, documents 1, 4 and 8). In addition to sorting the clusters, the optional commands listed in lines 31 through 33 may be implemented. For example, document 7 could be added to the cluster created by document 2 because document 7 is most conceptually similar to a document included in that cluster-namely, document 3.
In another embodiment, the SimSort algorithm may receive a pre-existing taxonomy or hierarchical structure and transform it into a suitable form for incremental enhancement with new documents. This embodiment utilizes the fact that any text can be represented as a pseudo-object in an abstract mathematical space. Due to document normalization, short and long descriptions can be matched with each other. Moreover, groups of documents may be represented by a centroid vector that combines document vectors within a group.
Details of an example method for generating a taxon (title) for a document cluster (referred to in step 130 of FIG. 1) will now be described. First, an example method for automatically constructing a taxon is presented. Then, this method is used to illustrate the generation of a taxon in accordance with an embodiment of the present invention.
FIG. 12 depicts a flowchart of a method 1200 for automatically constructing a taxon for a collection of documents in accordance with an embodiment of the present invention. Method 1200 operates on a collection of document clusters as generated, for example, by an algorithm described above in Sections II, III, and/or IV, or some other document clustering algorithm as would be apparent to a person skilled in the relevant art(s). That is, the input to method 1200 includes: (i) a representation of each document in the collection of documents, the document-representation being generated in an abstract mathematical space having a similarity measure defined thereon (e.g., the abstract mathematical space can be an LSI space and the similarity measure can be a cosine measure); (ii) a representation of each term in a subset of all the terms contained in the collection of documents, the term-representation being generated in the abstract mathematical space; and (iii) a hierarchy of document clusters.
Method 1200 begins at a step 1210 in which, for each cluster, candidate terms are chosen from the terms in the subset of all the terms. There are at least two example manners in which the candidate terms can be chosen. First, the candidate terms can be chosen using the similarity measure defined in the abstract mathematical space. For example, a centroid vector representation can be constructed for a given cluster of documents. Then, the N closest terms to the centroid vector can be chosen as candidate terms, where “closeness” between a given term and the centroid vector is determined by the similarity measure; i.e., the larger the value of the similarity measure between the vector representation of a given term and the centroid vector, the closer the given term is to the centroid vector. Second, a frequency of occurrence of the respective terms in documents belonging to the clusters can be used as an example manner for choosing the candidate terms. The documents can be a random subset of all the documents in the clusters, or the documents can represent a unique subset of documents in the clusters. For example, the unique subset of documents can be those documents that are only contained within a single document cluster.
In a step 1220, for each cluster, the best candidate terms are selected based on an evaluation scheme. There are several evaluation schemes, or combinations thereof, that can be used to select the best candidate terms. As a first example, an intra-cluster filter, which utilizes the similarity measure already defined on the abstract mathematical space, can be used. For instance, the intra-cluster filter can choose only those terms from the N closest terms (mentioned above with respect to step 1210) that have a similarity measure with the centroid vector above a similarity-threshold. As a second example, the selection of the best candidate terms can favor generalized entities in the form of bi-words (i.e., word pairs). That is, if a word and a bi-word occur with the same frequency in a given document or document collection, the bi-word would be selected. As a third example, an inter-cluster filter can be used to select the best candidate terms. For instance, a comparison of the frequency of occurrence of a term in a given cluster to the frequency of occurrence of the term in other clusters can be used as a basis for selecting the term. If the frequency of occurrence of the term in the given cluster is greater than the frequency of occurrence of the term in other clusters, the term is potentially a good candidate term for the given cluster. However, if the term is equally likely to occur in any of the clusters, then the term is common to all the clusters and is not necessarily representative of the given cluster. Hence, it would not be selected as a candidate term.
In a step 1230, for each cluster, a title is constructed from the best candidate terms. The best candidate terms are ordered according to their frequency of occurrence in the respective clusters. The title is constructed based on a generalization of an overlap between the best candidate terms. An example will be used to illustrate this point. Suppose A_B and C_A represent two bi-words that occur in a given document cluster, wherein A, B, and C each represent a word or similar type of language unit. There is an overlap between bi-word A_B and bi-word C_A—namely, both bi-words include the word A. A generalized entity that includes both bi-word A_B and bi-word C_A is formed as the triple C_A_B. As noted above, a bi-word is a better candidate term for a title than a single word. In a similar fashion, a triple is a better candidate term for a title than a bi-word, a quadruple is better than a triple, and so forth. In other words, given that a bi-word A_B and a bi-word C_A both exist in a given cluster, if the generalized entity C_A_B also exists in the given cluster, C_A_B would represent a better candidate title for the cluster than either bi-word A_B or bi-word C_A. So, constructing the title for a given cluster includes finding the largest generalized entity that exists in the cluster.
In addition to finding the largest generalized entity, constructing the title for a given cluster includes restoring all the original letters, prefixes, postfixes, and stop-words that are not included in the vector representation of the terms. As mentioned above with respect to FIG. 1, during preprocessing of the documents, stop-words and stop-phrases are removed, so they are not represented in the abstract mathematical space. For example, in representing the term “George W. Bush” in the abstract mathematical space, the letter “W” will not have a representation, only the bi-word “george_bush” will have a representation in the space. However, in constructing a title from the bi-word “george_bush,” the most common usage of this bi-word among the documents in the cluster is used to construct the title—i.e., “George W. Bush” is used.
This section presents a taxonomy that was generated using an embodiment of the present invention. The taxonomy was generated from a collection of documents called R-9133 collection, which is a subset of Reuters-21578. Reuters-21578 can be found in Lewis, D.D.: Reuters-21578 Text Categorization Test Collection. Distribution 1.0 (1999). The documents in the Reuters-21578 collection are classified into 66 categories, with some documents belonging to more than one category. The subset R-9133 contains 9,133 documents with only a single category assigned.
The Reuters-21578 documents are related to earnings, trade, acquisitions, money exchange and supply, and market indicators. The taxonomy generated using an embodiment of the present invention closely reflects human-generated categories. For example, the largest category, “earnings,” is represented by the top four largest topics emphasizing different aspects of earnings reports: (1) reports of gains and losses in cents in comparable periods; (2) payments of quarterly dividends; (3) expected earnings as reported quarterly; and (4) board decisions for splitting stock.
Besides the grouping offered by a clustering algorithm, the topic titles are indicative of underlying relationships among objects described in the documents. Acronyms are often explained by full names (e.g., “Commodity Credit Corporation, CCC,” “International Coffee Organization, ICO,” “Soviet Union, USSR”). Correlated objects are grouped under one topic title (e.g., “Shipping, Port, Workers,” “GENCORP, Wagner and Brown, AFG Industries,” “General consensus on agriculture trade, GATT, Trade Representative Clayton Yeutter”).
Table 1 shows topic #24 with its subtopics. These subtopics are ordered according to similarity between the represented documents and the topic title. For example, the first subtopic, which consists of 9 documents, is similar to the topic title at 69%. The second subtopic, which consists of 41 documents, is similar to the topic title at 65%.
Subtopics generated for the “Gulf, KUWAIT, Minister” topic.
Human-assigned
Topic Title Doc categories and
# SIM|Subtopic title Cnt document counts
24 Gulf, KUWAIT, Minister 63 crude.32 ship.24
money-fx.4 earn.1
acq.1 pet-chem.1
69 Saudi Arabia and the United 9 money-fx.4 crude.3
Arab Emirates, Gulf Cooperation pet-chem. 1 ship.1
65 Shipping, OIL PLATFORM, 41 ship.22 crude.19
57 Oil Minister Gholamreza 6 crude.6
Aqazadeh, QASSEM AHMED
TAQI, Iranian news agency
54 OPEC, Prices, Oil Minister 10 crude.10
50 Strategic Straits of Hormuz, 4 ship.4
Warships, Patrols
45 Assets of nine community 1 acq.1
papers, Gulf Coast, SCRIPPS
45 GULF STATES UTILITIES, 1 earn.1
Issued a qualified opinion,
Auditor Coopers and Lybrand
17 Decided to renew its one-year 1 crude.1
contract with Abu Dhabi, Supply
of tonnes of Gulf of Suez
Various aspects of the present invention can be implemented by software, firmware, hardware, or a combination thereof. FIG. 13 illustrates an example computer system 1300 in which an embodiment of the present invention, or portions thereof, can be implemented as computer-readable code. For example, the methods illustrated by flowcharts 100, 200, 300, 500, 600, 900, 1100 and/or 1200 can be implemented in system 1300. Various embodiments of the invention are described in terms of this example computer system 1300. After reading this description, it will become apparent to a person skilled in the relevant art how to implement the invention using other computer systems and/or computer architectures.
Computer system 1300 may also include a communications interface 1324. Communications interface 1324 allows software and data to be transferred between computer system 1300 and external devices. Communications interface 1324 may include a modem, a network interface (such as an Ethernet card), a communications port, a PCMCIA slot and card, or the like. Software and data transferred via communications interface 1324 are in the form of signals 1328 which may be electronic, electromagnetic, optical, or other signals capable of being received by communications interface 1324. These signals 1328 are provided to communications interface 1324 via a communications path 1326. Communications path 1326 carries signals 1328 and may be implemented using wire or cable, fiber optics, a phone line, a cellular phone link, an RF link or other communications channels.
In this document, the terms “computer program medium” and “computer usable medium” are used to generally refer to media such as removable storage unit 1318, removable storage unit 1322, a hard disk installed in hard disk drive 1312, and signals 1328. Computer program medium and computer usable medium can also refer to memories, such as main memory 1308 and secondary memory 1310, which can be memory semiconductors (e.g. DRAMs, etc.). These computer program products are means for providing software to computer system 1300.
Computer programs (also called computer control logic) are stored in main memory 1308 and/or secondary memory 1310. Computer programs may also be received via communications interface 1324. Such computer programs, when executed, enable computer system 1300 to implement the present invention as discussed herein. In particular, the computer programs, when executed, enable processor 1304 to implement the processes of the present invention, such as the steps in the methods illustrated by flowcharts 100, 200, 300, 500, 600, 900, 1100 and/or 1200 discussed above. Accordingly, such computer programs represent controllers of the computer system 1300. Where the invention is implemented using software, the software may be stored in a computer program product and loaded into computer system 1300 using removable storage drive 1314, interface 1320, hard drive 1312 or communications interface 1324.
An example computer implementation of the methods described above includes a Graphical User Interface (GUI). The GUI includes several features and functionalities, including:
1. Generality Slider—allows a user to specify how general a cluster should be (i.e., allows a user to specify a similarity-threshold above which two clusters are merged together);
2. Hierarchy Depth—allows a user to specify a number of levels of sub-clusters to create for the hierarchy;
3. Number of Sub-Titles—allows a user to specify the number of taxons (titles) to be assigned to each cluster;
4. Mode of Operation—allows the hierarchy to be generated based on the (i) entire repository of documents, or (ii) a user-specified query of the repository (i.e., a user-specified subset of the entire repository of documents);
5. Topic Title Exclusions—allows a user to indicate topic titles that are to be excluded;
6. View of Taxonomy—allows a user to browse all the documents in a generated taxonomy;
7. Exportation of Taxonomy—allows a user to export a taxonomy so it can be used by a different program (such as, a categorization system for categorizing unknown documents);
8. Pre-Sets—allows a user to select pre-set taxonomy generation parameters to facilitate the creation of a taxonomy;
9. Repository Selector—allows a user to select a repository of indexed documents for constructing a taxonomy;
10. Topic Titles Toggle—allows a user to enable/disable topic title generation, wherein with ‘topic titles’ off, the system produces a hierarchy of clusters;
11. Minimum Retrieval Similarity—allows a user to specify a similarity-threshold for retrieving documents from the selected repository based on the similarity between each document and a query; and
12. Minimum Assimilation Similarity—allows a user to specify a similarity-threshold for adding un-clustered documents to the clusters.
MONITORING CAPABILITIES. Embodiments of the present invention can be used to monitor different media outlets to organize items and/or information of interest. For example, an embodiment of the present invention can be used to automatically construct a taxonomy for the item and/or information. By way of illustration, and not limitation, the item and/or information of interest can include, a particular brand of a good, a competitor's product, a competitor's use of a registered trademark, a technical development, a security issue or issues, and/or other types of items either tangible or intangible that may be of interest. The types of media outlets that can be monitored can include, but are not limited to, email, chat rooms, blogs, web-feeds, websites, magazines, newspapers, and other forms of media in which information is displayed, printed, published, posted and/or periodically updated.
CATEGORIZATION CAPABILITIES. A taxonomy constructed in accordance with an embodiment of the present invention can also be used to generate a categorization of items. Example applications in which embodiments of the present invention can be coupled with categorization capabilities can include, but are not limited to, employee recruitment (for example, by matching resumes to job descriptions), customer relationship management (for example, by characterizing customer inputs and/or monitoring history), call center applications (for example, by working for the IRS to help people find tax publications that answer their questions), opinion research (for example, by categorizing answers to open-ended survey questions), dating services (for example, by matching potential couples according to a set of criteria), and similar categorization-type applications.
OUTPUT, DISPLAY AND/OR DELIVERABLE CAPABILITIES. A taxonomy constructed in accordance with an embodiment of the present invention and/or products that use a taxonomy constructed in accordance with an embodiment of the present invention can be output, displayed and/or delivered in many different manners. Example outputs, displays and/or deliverable capabilities can include, but are not limited to, an alert (which could be emailed to a user), a map (which could be color coordinated), an unordered list, an ordinal list, a cardinal list, cross-lingual outputs, and/or other types of output as would be apparent to a person having ordinary skill in the relevant art(s) from reading the description contained herein.
APPLICATIONS IN TECHNOLOGY, INTELLECTUAL PROPERTY AND PHARMACEUTICALS INDUSTRIES. A method for constructing a taxonomy described herein can be used in several different industries, such as the Technology, Intellectual Property (IP) and Pharmaceuticals industries. Example applications of embodiments of the present invention can include, but are not limited to, prior art searches, patent/application alerting, research management (for example, by identifying patents and/or papers that are most relevant to a research project before investing in research and development), clinical trials data analysis (for example, by analyzing large amount of text generated in clinical trials), and/or similar types of industry applications.
US20030088581 * Oct 29, 2001 May 8, 2003 Maze Gary Robin System and method for the management of distributed personalized information
US8682649 * Nov 12, 2009 Mar 25, 2014 Apple Inc. Sentiment prediction from textual data
US9665616 * Dec 22, 2011 May 30, 2017 Thomson Licensing Method and system for providing media recommendations
US20110295592 * May 28, 2010 Dec 1, 2011 Bank Of America Corporation Survey Analysis and Categorization Assisted by a Knowledgebase
US20130268557 * Dec 22, 2011 Oct 10, 2013 Thomson Licensing Method and system for providing media recommendations
EP2560111A3 * Aug 16, 2012 May 15, 2013 Lockheed Martin Corporation Systems and methods for facilitating the gathering of open source intelligence
U.S. Classification 1/1, 707/E17.099, 707/E17.091, 707/999.102
Cooperative Classification G06F17/3071, G06F17/30734
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:WNEK, JANUSZ;REEL/FRAME:017864/0987