Source: https://patents.google.com/patent/US8332439B2/en
Timestamp: 2019-10-16 11:36:04
Document Index: 580204437

Matched Legal Cases: ['§119', 'Application No. 08165760', 'Application No. 08165783', 'Application No. 10153368', 'Application No. 200810165999', 'Application No. 200810166177']

US8332439B2 - Automatically generating a hierarchy of terms - Google Patents
Automatically generating a hierarchy of terms Download PDF
US8332439B2
US8332439B2 US12/242,965 US24296508A US8332439B2 US 8332439 B2 US8332439 B2 US 8332439B2 US 24296508 A US24296508 A US 24296508A US 8332439 B2 US8332439 B2 US 8332439B2
US12/242,965
US20090094208A1 (en
2007-10-05 Priority to US97784007P priority Critical
2008-10-01 Priority to US12/242,965 priority patent/US8332439B2/en
2008-10-01 Assigned to FUJITSU LIMITED reassignment FUJITSU LIMITED ASSIGNMENT OF ASSIGNORS INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: JAIN, JAWAHAR, STERGIOU, STERGIOS, ADLER, B. THOMAS, GILMAN, ALEX, MARVIT, DAVID L.
2009-04-09 Publication of US20090094208A1 publication Critical patent/US20090094208A1/en
2012-12-11 Publication of US8332439B2 publication Critical patent/US8332439B2/en
206010025323 Lymphomas Diseases 0 description 5
In certain embodiments, generating a hierarchy of terms includes accessing a corpus comprising terms. The following is performed for one or more terms to yield parent-child relationships: one or more parent terms of a term are identified according to directional affinity; and one or more parent-child relationships are established from the parent terms and each term. A hierarchical graph is automatically generated from the parent-child relationships.
This application claims benefit under 35 U.S.C. §119(e) of U.S. Provisional Application Ser. No. 60/977,840, titled “Automatic Generation of a Hierarchy of Terms,” filed Oct. 5, 2007, by David Marvit et al.
The present invention relates generally to lexicographical analysis and, more particularly, to automatically generating a hierarchy of terms.
A corpus of data may hold a large amount of information, yet finding relevant information may be difficult. A hierarchy of terms may be created to facilitate the search for relevant information. In certain situations, however, known techniques for generating a hierarchy of terms are not effective in certain situations.
FIG. 1 illustrates one embodiment of a system that automatically generates hierarchical graphs that represent hierarchies of terms;
FIG. 9 illustrates one embodiment of a hierarchy module that may be used with the system of FIG. 1;
FIG. 10 illustrates an example of a hierarchical graph; and
FIGS. 11A and 11B illustrate nodes from which a redundant parent-child relationship may be removed.
AA(B)=AVERAGE— ×DAff(×, B)
FIG. 1 illustrates one embodiment of a system 10 that automatically generates hierarchical graphs that represent hierarchies of terms. In particular embodiments, system 10 accesses a corpus that includes documents (or pages). System 10 identifies parent terms for terms of the corpus according to directional affinity and establishes parent-child relationships among the terms. System 10 then automatically generates a hierarchical graph from the parent-child relationships.
In the illustrated embodiment, server 22 includes an affinity module 30, a clustering module 31, an ontology feature module 32, and a hierarchy module 37. Affinity module 30 may calculate affinities for word pairs, record the affinities in an affinity matrix, and/or report the affinity matrix. Affinity module 30 may also generate an affinity graph. Affinity module 30 is described in more detail with reference to FIG. 2.
In particular embodiments, hierarchy module 37 automatically generates hierarchical graphs that represent hierarchies of terms. In the embodiments, hierarchy module 37 accesses a corpus that includes documents (or pages). Hierarchy module 37 identifies parent terms for terms of the corpus according to directional affinity and establishes parent-child relationships among the terms. Hierarchy module 37 then automatically generates a hierarchical graph from the parent-child relationships. Hierarchy module 37 is described in more detail with reference to FIG. 9.
FIG. 3 illustrates an example of an affinity matrix 110 that records basic affinities. In the illustrated example, affinity matrix 110 records the pairwise affinities of words w1, . . . w5. According to affinity matrix 110, the affinity between words w0 and w1 is 0.003, between words w0 and w2 is 0.005, and so on.
In the example, cluster S starts with a seed word wq. The current word wx represents a word of cluster S that is being compared with a word from set W at the current iteration. Initially, current word wx is set to seed word wq. During an iteration, current word wx is set to a word of cluster S. Words wi of set W are sorted according to their forward affinity Afffor(wi, wx) with current word wx. Starting at the beginning of the sorted set W, candidate words wc that meet affinity criteria are identified. The affinity criteria may comprise a forward affinity with the current word wx criterion:
Affback(wq , w x)>Th cb
FIG. 9 illustrates one embodiment of hierarchy module 37 that may be used with system 10 of FIG. 1. In particular embodiments, hierarchy module 37 generates hierarchical graphs that represent hierarchies of terms. In the embodiments, hierarchy module 37 accesses a corpus, such as pages 50 (or documents). Hierarchy module 37 identifies parent terms for terms of the corpus according to directional affinity and establishes parent-child relationships. Hierarchy module 37 then automatically generates a hierarchical graph from the parent-child relationships. In the illustrated embodiment, hierarchy module 37 includes a graph engine 320 and a hierarchy application module 322. Graph engine 320 generates hierarchical graphs 350. An example of a hierarchical graph is described with reference to FIG. 10.
FIG. 10 illustrates an example of a hierarchical graph 350. In particular embodiments, hierarchical graph 350 represents a hierarchy of terms. In the embodiments, hierarchical graph 350 includes nodes 354 that represent terms and arcs 358 that represent a parent-child relationship from a parent term to a child term. In particular embodiments, in a parent-child relationship, a parent term and a child term are related by affinity, such as directional affinity. The parent term may be more general than the child term, and conversely the child term may be more specific than the parent term.
In particular embodiments, a relationship between a grandparent term (or great-grandparent term or so on) and a child term may also be referred to as a parent-child relationship. That is, a parent-child relationship may start from a parent term, pass through zero, one, or more parent/child terms (that operate as parent and child terms in the relationship), and end at a child term. In other words, a parent-child relationship may have any suitable number of generations.
Referring back to FIG. 9, in the illustrated embodiment, graph engine 320 includes a parent-child identifier 324 and a graph reducer 328. In particular embodiments, parent-child identifier 324 identifies parent-child relationships among terms, and graph reducer 328 reduces hierarchical graphs 350.
In particular examples, graph engine 320 generates hierarchical graph 350 for a set S of documents of a corpus C. A document may include one or more terms. Pages(X, C) represents a subset of set S that includes documents that have at least one occurrence of term X. Pages(X+Y, C) represents a subset of set S that includes documents that have at least one occurrence of term X and at least one occurrence of term Y. DocFreq(X, C) represents the number of documents that include at least one occurrence of term X, and may be calculated according to:
DocFreq(X, C)=|Pages(X, C)|
As discussed above, directional affinity may be used to measure of how important a given term is to another term. In particular embodiments, given that a document has a first term, the directional affinity indicates the likelihood that the document has a second term. If the likelihood is high, then there is a high directional affinity, and if the likelihood is low, then there is a low directional affinity. For example, lymphoma is a type of cancer. Documents that include “lymphoma” probably also include “cancer.” Accordingly, there is a high directional affinity from lymphoma to cancer. The reverse, however, is not necessarily the case. There are several kinds of cancer, so many documents that include “cancer” probably do not include “lymphoma.” Accordingly, there is a low directional affinity from cancer to lymphoma.
Directional affinity may be expressed in any suitable manner, for example, using the expression presented above. In other embodiments, DAff(X, Y, C) represents the directional affinity of Y given X in corpus C, and may be calculated according to:
DAff(X, Y, C)=DocFreq(X+Y, C)/DocFreq(X, C)
In particular embodiments, parent-child identifier 324 identifies parent-child relationships by determining a set of candidate parent terms Yi for a given term X. In the embodiments, there is a high directional affinity from given term X to a parent term Yi, but parent term Yi appears in more documents without given term X than with term X, indicating that term X is related to, but not indispensable to, parent term Yi.
In particular embodiments, the condition that there is a high directional affinity from given term X to a parent term Yi may be expressed as:
DAff(X, Y i , S)≧Th high
where Thhigh represents a higher directional affinity threshold indicating a higher directional affinity. The higher directional affinity threshold may have any suitable value, such as value in the ranges of 0.5 or greater, 0.6 or greater, or 0.7 or greater.
In particular embodiments, the condition that parent term Yi appears in more documents without given term X than with term X and that term X is related, but not indispensable, to parent term Yi may be expressed as:
DAff(Y i , X, S)≦Th low
DAff(Y i , X, S)≧Th min
where Thlow represents a lower directional affinity threshold indicating a lower directional affinity, and Thmin represents a minimum directional affinity threshold. The lower directional affinity threshold may have any suitable value, such as value in the ranges of 0.5 or lower, 0.4 or lower, or 0.1 or lower. The minimum directional affinity threshold may have any suitable value, such as value in the ranges of 0.1 or lower, 0.01 or lower, or 0.001 or lower. A candidate parent term Yi that satisfies the above conditions for a given term may be regarded as a parent term for the given term, which may be regarded as the child term.
Nodes 354 representing the terms may be organized into hierarchical graph 350 according to the parent-child relationships. In particular embodiments, graph reducer 328 reduces hierarchical graph 350 by removing a redundant parent-child relationship. An example of removal of a redundant parent-child relationship is described with reference to FIGS. 11A and 11B.
FIGS. 11A and 11B illustrate nodes from which a redundant parent-child relationship may be removed. A redundant parent-child relationship may be a parent-child relationship that is redundant with a given parent-child relationship. The redundant parent-child relationship may provide the same or less information than the given parent-child relationship provides. For example, a given parent-child relationship may have a parent term, zero, one or more parent/child terms, and a child term. The redundant parent-child relationship may have the same parent term, a subset of the same parent/child terms, and the same child term, and no other terms. In other words, the child has two parent terms that are linked to each other.
In the illustrated example, the given parent-child relationship has parent term “health,” parent/child term “disease,” and child term “diabetes.” The redundant parent-child relationship has parent term “health” and child term “diabetes.” Graph reducer 328 may remove the redundant parent-child relationship.
Referring back to FIG. 9, in particular embodiments, hierarchy application module 322 applies hierarchical graphs 350. Hierarchy module 37 may generate any suitable hierarchical graph from any suitable corpus, which hierarchy application module 322 may apply in any suitable manner.
In particular embodiments, the corpus comprises documents that include terms, and hierarchical graph 350 serves as a catalog of the documents that may be used to search the documents. In certain examples of the embodiments, hierarchy application module 322 sends parent terms of hierarchical graph 350 to a client. A user may select from the parent terms as search terms. Hierarchy application module 322 receives a selection of a parent term and sends the child terms of the selected parent to the client. A user may select from the terms, and the process may be repeated until the end of hierarchical graph 350 is reached or the user has indicated a final selection.
In other examples of the embodiments, hierarchy application module 322 receives a search query comprising a parent term of the hierarchical graph. Hierarchy application module 322 identifies child terms of the parent term and searches the corpus using the parent term and the child terms. In yet other examples of the embodiments, each graph term of hierarchical graph 350 may be associated with a document that includes the graph term. Hierarchy application module 322 receives a search query comprising a parent term of hierarchical graph 350. Hierarchy application module 322 then retrieves one or more documents associated with the parent term or a child of the parent term.
In particular embodiments, the corpus comprises search results, and hierarchical graph 350 organizes the search results according to the parent-child relationships of the search results. A term of hierarchical graph 350 may represent a topic of a search result or of a cluster in which the search result appears. Hierarchy application module 322 may present hierarchical graph 350 and/or the organized search results to a user.
Certain embodiments of the invention may provide one or more technical advantages. A technical advantage of one embodiment may be that hierarchical graphs that represent hierarchies of terms are automatically generated for a corpus of documents. The hierarchical graphs describe parent-child relationships among the terms and may serve to catalog the documents of the corpus. A technical advantage of another embodiment may be that hierarchical graphs are automatically generated for search results. The hierarchical graphs may serve to organize the search results.
accessing a corpus stored in one or more tangible media, the corpus comprising a plurality of terms;
performing the following for each term of one or more terms of the plurality of terms to yield a plurality of parent-child relationships:
identifying one or more parent terms of the each term according to directional affinity, the plurality of terms comprising the one or more parent terms,
the directional affinity being the number of co-occurrence contexts that include two terms, over the number of co-occurrence contexts that include one term; and
establishing one or more parent-child relationships from the one or more parent terms and the each term; and
automatically generating a hierarchical graph from the plurality of parent-child relationships,
wherein the automatically generating the hierarchical graph from the plurality of parent-child relationships comprises reducing the hierarchical graph by:
identifying a parent-child relationship and a redundant parent-child relationship of the hierarchical graph; and
removing the redundant parent-child relationship from the hierarchical graph.
2. The method of claim 1, the identifying the one or more parent terms of the each term according to directional affinity further comprising:
determining that there is a high directional affinity from the each term to a candidate parent term;
determining that there is a low non-zero directional affinity from the candidate parent term to the each term; and
identifying the candidate parent term as a parent term of the each term.
3. The method of claim 1, the identifying the one or more parent terms of the each term according to directional affinity further comprising:
determining that a directional affinity from the each term to a candidate parent term is greater than 0.6 and less than or equal to one;
determining that a directional affinity from the candidate parent term to the each term is less than 0.4 and greater than 0.1; and
the corpus comprising a plurality of documents, the plurality of documents comprising the plurality of terms; and
the hierarchical graph representing a catalog of the plurality of documents.
the corpus comprising a plurality of search results;
a term of the one or more terms representing a topic of a search result; and
the hierarchical graph describing the plurality of parent-child relationships of the plurality of search results.
the corpus comprising a plurality of search results organized into a plurality of clusters;
a term of the one or more terms representing a topic of a cluster; and
sending a plurality of parent terms of the hierarchical graph to a client;
receiving a selection of a parent term, the selected parent term having a plurality of child terms; and
sending the plurality of child terms to the client.
receiving a search query comprising a parent term of the hierarchical graph;
identifying one or more child terms of the parent term; and
searching the corpus using the parent term and the one or more child terms.
associating each graph term of the hierarchical graph with a document that includes the each graph term;
receiving a search query comprising a parent term; and
retrieving one or more documents associated with a child of the parent term.
access a corpus stored in one or more tangible media, the corpus comprising a plurality of terms;
perform the following for each term of one or more terms of the plurality of terms to yield a plurality of parent-child relationships:
identify one or more parent terms of the each term according to directional affinity, the plurality of terms comprising the one or more parent terms,
establish one or more parent-child relationships from the one or more parent terms and the each term; and
automatically generate a hierarchical graph from the plurality of parent-child relationships,
11. The computer-readable tangible media of claim 10, the software further operable to identify the one or more parent terms of the each term according to directional affinity by:
determining that there is a low directional affinity from the candidate parent term to the each term;
determining that a directional affinity from the candidate parent term to the each term is above a minimum threshold; and
12. The computer-readable tangible media of claim 10, the software further operable to identify the one or more parent terms of the each term according to directional affinity by:
13. The computer-readable tangible media of claim 10:
14. The computer-readable tangible media of claim 10:
15. The computer-readable tangible media of claim 10:
16. The computer-readable tangible media of claim 10, the software further operable to:
send a plurality of parent terms of the hierarchical graph to a client;
receive a selection of a parent term, the selected parent term having a plurality of child terms; and
send the plurality of child terms to the client.
17. The computer-readable tangible media of claim 10, the software further operable to:
receive a search query comprising a parent term of the hierarchical graph;
identify one or more child terms of the parent term; and
search the corpus using the parent term and the one or more child terms.
18. The computer-readable tangible media of claim 10:
the software further operable to:
associate each graph term of the hierarchical graph with a document that includes the each graph term;
receive a search query comprising a parent term; and
retrieve one or more documents associated with a child of the parent term.
US12/242,965 2007-10-05 2008-10-01 Automatically generating a hierarchy of terms Active 2031-03-07 US8332439B2 (en)
US97784007P true 2007-10-05 2007-10-05
US12/242,965 US8332439B2 (en) 2007-10-05 2008-10-01 Automatically generating a hierarchy of terms
EP08165783A EP2045734A3 (en) 2007-10-05 2008-10-02 Automatically generating a hierarchy of terms
JP2008259632A JP5332477B2 (en) 2007-10-05 2008-10-06 Automatic generation of term hierarchy
CN 200810166177 CN101404015B (en) 2007-10-05 2008-10-06 Automatically generating a hierarchy of terms
US20090094208A1 US20090094208A1 (en) 2009-04-09
US8332439B2 true US8332439B2 (en) 2012-12-11
ID=40524152
US12/242,965 Active 2031-03-07 US8332439B2 (en) 2007-10-05 2008-10-01 Automatically generating a hierarchy of terms
US (1) US8332439B2 (en)
EP (1) EP2045734A3 (en)
JP (1) JP5332477B2 (en)
CN (1) CN101404015B (en)
TWI456412B (en) * 2011-10-11 2014-10-11 Univ Ming Chuan Method for generating a knowledge map
CN102779143B (en) * 2012-01-31 2014-08-27 中国科学院自动化研究所 Visualizing method for knowledge genealogy
CN103236074B (en) * 2013-03-25 2015-12-23 深圳超多维光电子有限公司 One kind of 2d / 3d image processing method and apparatus
US9355163B2 (en) 2013-06-07 2016-05-31 Vmware, Inc. Using a graph database of a virtualization infrastructure
CN105869056A (en) * 2016-03-31 2016-08-17 比美特医护在线（北京）科技有限公司 Information processing method and apparatus
JP2008152324A (en) * 2006-12-14 2008-07-03 National Institute Of Information & Communication Technology Vocabulary hierarchical structure extraction method, device, and program
2008-10-01 US US12/242,965 patent/US8332439B2/en active Active
2008-10-02 EP EP08165783A patent/EP2045734A3/en not_active Ceased
2008-10-06 CN CN 200810166177 patent/CN101404015B/en active IP Right Grant
2008-10-06 JP JP2008259632A patent/JP5332477B2/en active Active
Brace, Karl S., et al., "Efficient Implementation of a BDD Package", Proceedings of the 27th ACM/IEEE Design Automation Conference, Paper 3.1, © 1990 IEEE, pp. 40-45, Jun. 24, 1990.
Communication from the European Patent Office, European Search Report for European Patent Application No. 08165760.3-1527, 7 pages, Jan. 26, 2009.
European Patent Office Communication, European Search Report and Annex to the European Search Report; Application No. 08165783.5-1527/2045734; Ref. P111732EP00/CLH; 5 pages, Jul. 14, 2009.
European Patent Office, Communication, European Search Report Application No. 10153368.5-2201, Ref. P113501EP00/FWW, 6 pages, Jun. 15, 2010.
Gonzalo Navarro, Modern Information Retrieval, Chapter 8: Indexing and Searching, ACM Press, New York, XP 002457291, ISBN 9780201398298, pp. 191-228, Jan. 1, 1999.
Raymie Stata, et al., "The Term Vector Database: fast access to indexing terms for Web pages", Computer Networks 33, Elsevier Science Publishers B.V., pp. 247-254, Jun. 1, 2000.
Saleem et al., Large Scale Automatic Semantic Integration, 2007, HAL-CCSD, pp. 1-29. *
Saleem et al.: "New Challenges: Large Scale Automatic Semantic Integration", (Hereinafter "Saleem"). *
The State Intellectual Property Office of China, First Notification of Office Action, Patent Application No. 200810165999.X, Chinese Office Action and English translation, 13 pages, May 27, 2010.
The State Intellectual Property Office of China, First Notification of Office Action, Patent Application No. 200810166177.3, Chinese Office Action and English translation, forwarded by foreign associate to Baker Botts on Jan. 14, 2011, 9 pages.
U.S. Appl. No. 12/242,950, by inventors David L. Marvit et al., entitled "Automatic Generation of Ontologies Using Word Affinities," 38 pages, filed Oct. 1, 2008.
Wang et al. "Using Term Clustering and Supervised Term Affinity Construction to Boost Text Classification," Springer-Verlag Gerlin Heidelberg, 2005.
US20090094208A1 (en) 2009-04-09
CN101404015B (en) 2012-03-21
JP5332477B2 (en) 2013-11-06
JP2009093652A (en) 2009-04-30
EP2045734A2 (en) 2009-04-08
CN101404015A (en) 2009-04-08
EP2045734A3 (en) 2009-08-12
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:MARVIT, DAVID L.;JAIN, JAWAHAR;STERGIOU, STERGIOS;AND OTHERS;REEL/FRAME:021613/0149;SIGNING DATES FROM 20080917 TO 20080922
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:MARVIT, DAVID L.;JAIN, JAWAHAR;STERGIOU, STERGIOS;AND OTHERS;SIGNING DATES FROM 20080917 TO 20080922;REEL/FRAME:021613/0149