Fusion of cluster labeling algorithms by analyzing sub-clusters

According to some embodiments of the present invention there is provided a computerized method for labeling a cluster of text documents. The method comprises receiving a document cluster and producing automatically multiple document sub-clusters determined by randomly changing some documents. The method applies multiple cluster labeling algorithms on the cluster and on each sub-cluster, to generate ordered lists. The method comprises generating a ranked label list for each cluster labeling algorithm by computing automatically label values, one for each cluster label in the lists of the selected algorithm, and re-ranking the ordered list. The method combines the re-ranked label lists using a label fusing algorithm to produce a fused label list.

BACKGROUND

The present invention, in some embodiments thereof, relates to document cluster labeling and, more specifically, but not exclusively, to fusion of multiple labeling algorithms on a cluster of documents.

Standard document clustering algorithms do not provide labels to characterize the clusters chosen. Cluster labeling is provided by cluster labeling algorithms that examine the contents of the documents in the cluster to find a label that best describes the topic(s) of the document cluster and helps distinguish the clusters from each other. For a given cluster of documents, as coherent as possible, a cluster labeling algorithm returns at least a single label that may best describe the cluster's main topic. Labeling clusters of documents is a fundamental and important task in information retrieval, including for applications of multi-document summarization, user profiling, and the like. For example, document cluster labeling algorithms are used for business intelligence and financial performance management. For example, document cluster labeling algorithms are used for enterprise content management. For example, document cluster labeling algorithms are used for business analytics and optimization. For example, document cluster labeling algorithms are used for user profiling in customer and social analysis.

Direct labeling algorithms for cluster labeling extract the label(s) from the cluster documents. For example, direct labeling algorithms include feature selection, most frequent document terms (keywords, phrases, n-grams, and the like), terms most frequent in cluster centroid, anchor text, named entities, cluster hierarchy, and the like. Indirect labeling algorithms extract the label from external relevant label sources. For example, indirect labeling algorithms include using labels extracted from Wikipedia categories, Freebase structured data, Dbpedia structured data, and the like.

SUMMARY

According to some embodiments of the present invention there is provided a computerized method for labeling a cluster of text documents. The method comprises receiving a document cluster comprising two or more text documents. The method comprises producing automatically two or more document sub-clusters, wherein each of the two or more document sub-clusters is determined by randomly changing one or more documents of the two or more text documents from the document cluster. The method comprises applying automatically two or more cluster labeling algorithms on the document cluster and each of the two or more document sub-clusters, to generate two or more ordered lists. The method comprises generating two or more ranked label lists one each for each of the two or more cluster labeling algorithms. The generation of ranked label lists comprises selecting automatically a selected algorithm from one of the two or more cluster labeling algorithms. The generation of ranked label lists comprises computing automatically two or more label values, one for each of the two or more cluster labels in the two or more ordered lists for the selected algorithm. The generation of ranked label lists comprises generating one of the two or more ranked label lists corresponding to the selected algorithm, wherein the one ranked label list is computed from respective the two or more ordered lists and respective the label value for each of respective the two or more cluster labels. The method comprises combining the two or more ranked label lists using a label fusing algorithm to produce a fused label list.

Optionally, the label fusing algorithm is computing using the label value for each of the two or more cluster labels in addition to the two or more ranked label lists.

Optionally, the label fusing algorithm is selected from a group consisting of a CombMNZ fusing algorithm, a CombSUM fusing algorithm, a CombSUM fusing algorithm, a reciprocal rank fusion algorithm, and a Borda-Count fusion algorithm.

Optionally, the label fusing algorithm incorporates the two or more label values in fusing labels from the two or more cluster labeling algorithms.

Optionally, the random changes and the two or more document sub-clusters are determined by a training document cluster, wherein the training document cluster has a true label list determined by manual inspection, and wherein the random changes are determined by a comparing of the fused label list with the true label list.

Optionally, the random changes comprise a removal of at least one of the two or more text document from the document cluster.

Optionally, the random changes are performed on a percentage of the two or more text documents.

Optionally, each of the two or more document sub-clusters comprises an equal number of text documents.

Optionally, each of the two or more document sub-clusters comprises a number of text documents determined randomly according to a Gaussian distribution.

Optionally, for each of the two or more cluster labeling algorithms a different set of the two or more document sub-clusters is produced, and wherein each of the different set comprises different the random changes.

Optionally, a single set of the two or more document sub-clusters is produced, and wherein the single set is used for each of the two or more cluster labeling algorithms.

Optionally, the method is offered as a service.

Optionally, the true label list determined by manual inspection is determined incrementally until the comparing produces a statistical confidence above a confidence threshold and a statistical power above a power threshold.

According to some embodiments of the present invention there is provided a computer readable medium comprising computer executable instructions adapted to perform the method described herein.

According to some embodiments of the present invention there is provided a computer program product for labeling a cluster of text documents. The computer program product comprises a computer readable storage medium. Stored on the computer readable storage medium are first program instructions executable by a processor to cause the device to receive a document cluster comprising two or more text documents. Stored on the computer readable storage medium are second program instructions executable by the device to cause the device to produce automatically two or more document sub-clusters, wherein each of the two or more document sub-clusters is determined by randomly changing one or more documents of the two or more text documents from the document cluster. Stored on the computer readable storage medium are third program instructions executable by the device to cause the device to apply automatically two or more cluster labeling algorithms on the document cluster and each of the two or more document sub-clusters, to generate two or more ordered lists. Stored on the computer readable storage medium are fourth program instructions executable by the device to cause the device to generate two or more ranked label lists one for each of the two or more cluster labeling algorithms. Generating a ranked label list comprises selecting automatically a selected algorithm from one of the two or more cluster labeling algorithms. Generating a ranked label list comprises computing automatically two or more label values, one for each of the two or more cluster labels in the two or more ordered lists for the selected algorithm. Generating a ranked label list comprises generating one of the two or more ranked label lists corresponding to the selected algorithm, wherein the one ranked label list is computed from respective the two or more ordered lists and respective the label value for each of respective the two or more cluster labels. Stored on the computer readable storage medium are fifth program instructions executable by the device to cause the device to combine the two or more ranked label lists using a label fusing algorithm to produce a fused label list.

According to some embodiments of the present invention there is provided a computerized system for labeling a cluster of text documents. The computerized system comprises a user interface, for controlling and monitoring the computerized system. The computerized system comprises a data interface, for receiving a document cluster. The computerized system comprises one or more processing units. The processing unit comprises a cluster randomizing module configured to receive a document cluster and produce automatically two or more randomized sub-clusters, where each of the two or more randomized sub-clusters is created from the document cluster after one or more changes to one or more text documents of the document cluster. The processing unit comprises a label ranking module configured to receive the two or more randomized sub-clusters, apply two or more cluster labeling algorithms to each of the two or more randomized sub-clusters to produce two or more label lists, determine a label value for each label of the two or more cluster labeling algorithms, and re-rank each of the two or more label lists for each of the two or more cluster labeling algorithms according to the label value. The processing unit comprises a label fusion module configured to receive re-ranked the two or more label lists, fuse the two or more label lists together to a single list for the document cluster, and send the single list.

DETAILED DESCRIPTION

In many cases, existing cluster labeling algorithms such as the Jensen-Shannon Divergence (JSD) and Score Prorogation (SP) labeling algorithms as described by Carmel et al in “Enhancing Cluster Labeling using Wikipedia” published in Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval (pages 139-146) are inconclusive. No dominant cluster labeling algorithm can be found for any given dataset and quality measure, such as quality measures Mean Reciprocal Rank (MRR@K), match-at-k (Match@K), and the like. For example, match-at-k is defined as the relative number of clusters for which at least one of the top-k labels is correct. Therefore, a combination of several cluster labeling algorithms is expected to produce a better cluster labeling choice. However, no such combination method exists that is fully tailored for the cluster labeling task.

According to some embodiments of the present invention there is provided a method and a system, for fusing multiple cluster labeling algorithms using sub-cluster analysis.

Given a document cluster, the method produces two or more sub-clusters by randomly changing one or more documents of the original cluster, computes a two or more label lists using two or more cluster labeling algorithms applied to each sub-cluster, re-ranks the label list produced by each algorithm according to a mathematical agreement computed by a decisiveness value of the rank of the labels in the label lists, and fuses the re-ranked lists from different labeling algorithms by weighing the labels with the a respective decisiveness value. A decisiveness value is determined for each label by applying the labeling algorithm to two or more document sub-clusters derived from the given document cluster, and computing a mathematical agreement of the resulting label lists. As used herein, the term decisiveness value is defined for a cluster label as the average pair-wise mathematical agreement between the rankings of the label in multiple label lists produced by labeling algorithms applied to all pairs of sub-clusters, and will be defined computationally by an equation herein. The sub-clusters are derived from the given document cluster by modifying at least one document from the document cluster. As used herein, the term sub-cluster is defined as any group of documents derived from the document cluster that has at least one document changed in deriving that sub-cluster. For example, a sub-cluster is derived when one or more documents are removed and/or added from the document cluster. For example, a sub-cluster is derived when the text of one or more documents is modified. Each label of the labeling algorithm results receives a decisiveness value by comparing the relative rank of the label in the labeling results computed by the labeling algorithm on multiple, changed sub-clusters. By re-ranking each labeling algorithm's labeling results according to their decisiveness values, the results may be a better representation of the labels for that document cluster given that labeling algorithm. Multiple labeling algorithm labeling results are then fused together to produce a single list of labels for the given document cluster.

Optionally, multiple labeling algorithm's re-ranked label list results are fused using a CombMNZ fusion algorithm.

Optionally, multiple labeling algorithm's re-ranked label list results are fused using a CombSUM fusion algorithm.

Optionally, multiple labeling algorithm's re-ranked label list results are fused using the decisiveness values for each label of each list.

Reference is now made toFIG. 1, which is a system100for label fusion of a document cluster using multiple labeling algorithms, according to some embodiments of the invention. The system comprises a user interface111for control of a label fusing method. The system further comprises a data interface112for receiving a document cluster. For example, the data interface112is a network interface, a universal serial bus interface, a bus interface, a Serial Advanced Technology Attachment, or the like. The system comprises a processing unit102for receiving the document cluster and producing a list of fused labels from multiple cluster labeling algorithms. The processing unit102is configured with software modules to implement embodiments of the invention. For example, the modules are stored in computer memory, on attached non-volatile storage, and the like. The processing unit102includes a Cluster Randomizing Module103to receive a document cluster and produce a group of randomized sub-clusters, where each sub-cluster is created from the received cluster after one or more changes to the documents of the cluster. The processing unit102includes a Label Ranking Module104receives the group of sub-clusters, applies two or more cluster labeling algorithms to each sub-cluster, determines a decisiveness value for each label of each labeling algorithm, and re-ranks the labels of each labeling algorithm according to the decisiveness value for that labeling algorithm's labels. The processing unit102includes a Label Fusion Module105receives the re-ranked label list for each labeling algorithm, fuses the lists together to produce a single list of fused labels for the document cluster, and sends the fused label list to the user interface111and/or data interface112.

Reference is now made toFIG. 2, which is a flowchart for label fusion of a document cluster using multiple labeling algorithms, according to some embodiments of the invention. The method actions start200with receiving201a document cluster to a computerized processing unit102through a data interface112. Multiple cluster labeling algorithms are used to compute label lists203A for the document cluster, one each for each algorithm. An action of creating202a group of random sub-clusters is performed by a Cluster Randomizing Module103. Multiple labeling algorithms are used to compute label lists203B for each sub-cluster, where for each labeling algorithm204, decisiveness values of cluster labels are computed205and the document cluster label list produced at step203A from each labeling algorithm is re-ranked206according to their decisiveness values by a Label Ranking Module104. When all cluster labeling algorithm results have been re-ranked, the labeling results are fused207together by the Label Fusion Module105, and the fused label list is sent to the data interface112for downstream utilization.

Embodiments of the current invention are based on the premise that results of a cluster labeling algorithm for a given input document cluster should remain stable when documents of the cluster are slightly changed. Labels determined by a labeling algorithm are re-ranked according to the decisiveness value with respect to each of its suggested labels.

Reference is now made toFIG. 3, which is a schematic illustration comparing labeling of sub-clusters with atomic fission, according to some embodiments of the invention. Embodiments300of the current invention applied to a document cluster301received by a processing unit102via a data interface112, produce sub-clusters, as at302and303, where each sub-cluster is based on the document cluster with one or more changes to one or more documents of the cluster, such as removing307one or more of the documents from cluster. The changes to the document cluster are performed in the processing unit by a Cluster Randomizing Module103. When a labeling algorithm is used by a Label Ranking Module104to compute a label list for a document cluster, a list of labels304is produced, illustrated as the electron orbit circles surrounding the cluster301. In the comparison with atomic fission, the atom nucleus is the document cluster301with documents as its nuclear subatomic particles (protons and neutrons). Labels304suggested by a labeling algorithm for that cluster are illustrated as electrons positioned at orbits that reflect the position of each label in the label list produced by the labeling algorithm. The cluster labeling algorithm's “decisiveness” (stability) with respect to its label suggestions (electron orbital configurations) may be estimated by a process of “cluster fission”. By introducing some “energy”300in the form of cluster noise which excludes (a small) fraction of the cluster's documents307, the cluster may be “split” into sub-clusters (“fission nuclei”302and303). When the labeling algorithm is used by a Label Ranking Module104to compute a list of labels for the sub-clusters, as at302and303, sub-cluster label lists as at302and306respectively are generated, shown as the respective electron orbit circles. By comparing the label lists as at304,305and306, a value for the consistency, or “decisiveness”, of the labeling algorithm can be determined by a Label Ranking Module104for each label, and the labels re-ranked according to the performance of the labeling algorithm on the cluster and sub-clusters.

Reference is now made toFIG. 4, which is a graphic illustration of cluster label fusion using label decisiveness values, according to some embodiments of the invention. An input document cluster210received by the processing unit102via a data interface112can be labeled by a Label Ranking Module104using multiple cluster labeling algorithms211,212, and213to a list of cluster labels214,215, and216, one for each algorithm. Each list of top-k cluster labels214,215, and216is also re-ranked by the Label Ranking Module104, according to a decisiveness value for each label as at217,218, and219, respectively, producing a re-ranked list of labels for each algorithm as at220. The top-k labels are the first k labels in each label list. The re-ranked label lists are fused221by a Label Fusion Module105given a fusion algorithm223, such as CombMNZ, CombSUM, CombMAX and the like, producing a fused label list222. For example, the details of computing decisiveness values for re-ranking of a labeling algorithm's results216is illustrated as at231for labeling algorithm213. The Cluster Randomizing Module103receives an input document cluster210and modifies232the cluster to N number of “noisy” sub-clusters234,235, and236, each containing a “noise level” given as a percentage of documents changed233. The Label Ranking Module104applies a labeling algorithm213to each of the sub-clusters234,235, and236producing sub-cluster label lists as at237. For each label239in the lists, a decisiveness values is computed238by the Label Ranking Module104using an equation for the general pair-wise cluster label list agreement240and an equation for the pair-wise cluster label list agreement on position of label239as ranked in each list241. The decisiveness value equation244is computed by the Label Ranking Module104to each label239on the label algorithm result lists237and the labels from all lists are combined and ranked according to the decisiveness value.

The application will now give a mathematical example of computing decisiveness values for cluster labels, according to some embodiments of the invention. Let C denote a cluster of documents, received by a processing unit102. For a given cluster C, a cluster labeling algorithm L suggests one or more labels that best represent the cluster's main topic. In general, two main types of cluster labeling algorithms may be employed, namely direct and indirect labeling algorithms. Cluster labels may be directly extracted from the content of the cluster's documents. For example, cluster labels can be extracted using feature selection labeling algorithms, choosing the most frequent terms (keywords, n-grams, phrases, and the like) in the cluster or the top weighted cluster centroid's terms, using document anchor text, named entities, utilizing the cluster's hierarchy, and the like. Cluster labels may be extracted indirectly using external relevant label sources, such as using Wikipedia's categories, Dbpedia's graph, Freebase's concepts, and the like.

A set of cluster labeling algorithms={L1, . . . , Lm} is used to compute lists of cluster labels by the processing unit102from a document cluster C received via the data interface112. Each labeling algorithm L∈takes a document cluster and/or sub-cluster C as an input and produces a list of nLdistinct candidate cluster labels L(C)=l1, l2, . . . , ln). Each candidate label l∈L(C) is scored by labeling algorithm L according to how well label1represents the main topic of cluster C.

Let SL(l|C) denote the score assigned to label l∈L(C) by labeling algorithm L∈and let L[k](C) denote the list of top-k scored labels. In addition, let rank(l|L(C)) denote the rank of label l∈L(C) according to its relative score SL(l|C).

For a given cluster labeling algorithm L∈and a label l∈L[k](C) suggested by L and ranked at position 1≤rank(l|L(C))≤k, the decisiveness value of labeling algorithm L with respect to that specific label at that specific ranked position is computed by the Label Ranking Module104.

The decisiveness value is derived by measuring the effect of changes to the input cluster C on the labeling algorithm L's labeling decisions. For example, changed versions of a given cluster C are produced by the Cluster Randomizing Module103by sampling several sub-clusters, each containing a subset of the documents of the original cluster C. In this example, for a given noise level, θ∈[0,1], a sub-cluster Ci⊂C is sampled by the Cluster Randomizing Module103by randomly choosing (1−θ)×|C| of the input cluster's (C) documents, where |C| denotes the number of documents in cluster C. The random noise θ may be selected such that the sub-cluster C1may be coherent with the original cluster C, such as avoiding the risk of a topic drift. Overall, N random sub-clusters cθ={C1, C2, . . . , CN} are sampled by the Cluster Randomizing Module103.

For a given sub-cluster C∈Cθ, let L[k](Ci) be the corresponding list of top-k labels suggested by labeling algorithm L for that sub-cluster. The labeling algorithm L's decisiveness value with respect to a given label l∈L[k](C) choice is defined as the labeling algorithm's self-label-agreement, derived by comparing label l's relative positions in the top-k label lists L[k](Ci) with its original position in L[k](C). The higher the agreement, the more labeling algorithm L is “decisive” with respect to its original choice of l as the label of cluster C.

The amount of local agreement is measured by the Label Ranking Module104by averaging the pair-wise agreement between N(N−1)/2 possible pairs of the sampled sub-clusters' top-k label lists L[k](Ci). For example, the Label Ranking Module104measures how many of the sub-clusters (pair-wise) agree with each other about label l's relative position. For a given pair of sub-clusters Ci, Cj∈cθ(drawn from the original cluster C by the Cluster Randomizing Module103) and label l∈L[k](C) ranked by the Label Ranking Module104using the labeling algorithm L at some position q (1≤q≤k), the pair-wise agreement between the two corresponding top-k sub-cluster label lists is confirmed by checking that: (1) label l is also included in both top-k label lists L[k](Ci) and L[k](Cj) (2) label l is further positioned at least at position q in both lists (i.e., rank(l|L[k](Ci))≤q and rank(l|L[k](Cj))≤q). Hence, each such confirmation may suggest that even in the presence of a (slightly) incomplete cluster data produced by the Cluster Randomizing Module103, label l's relative position remains stable, implying that labeling algorithm L may be more decisive with respect to that label choice.

The decisiveness value measures the “local” agreement between the two lists by measuring the intersection size between any pair of label lists L[k](Ci) and L[k](Cj). Such intersection follows a hypergeometric distribution and the expected agreement is derived according to the (normalized) difference between the expected and the observed intersection size. For a given label position 1≤q≤k, let L[q]Ci,j=L[q](Ci)∩L[q](Ci) denote the intersection between the a pair of (ranked) label lists, considering only those labels that are positioned at least at position 1≤q′≤q. Let{l∈LCi,j[q]} be an indicator, receiving the value of one if and only if label l is included in the intersection L[q]Ci,j(i.e., when positioned in both lists at position q or better), otherwise zero. For any pair of sub-clusters Ci, Cj∈cθlabeled by labeling algorithm L, the corresponding expected (global) agreement between their corresponding top-k label lists L[k](Ci) and L[k](Cj) is given by:

φi,jL⁡(k)⁢=def⁢L[k]⁡(Ci,j)·nL-k2k·(nL-k)EQN.⁢1
Note that in the case of a full agreement (i.e., |L[q]Ci,j|=k) we have φi,jL(k)=1, while in the case of no agreement we have

The cluster labeling algorithm L's decisiveness value with respect to a given label choice l∈L[k](C) (denoted wL(l)) is computed by the Label Ranking Module104using an equation for the average pair-wise list agreement:

wL⁡(l❘C)⁢=def⁢12⁢N⁡(N-1)⁢∑i,j⁢⁢[φi,jL⁡(k)+1]2×ℐ⁢{l∈L[q]⁡(Ci,j)}EQN.⁢2
Therefore, a label1that has a high consensus about its specific position in L[k](C) by highly agreeable lists L[k](Cj) is estimated to be a more “reliable” label for cluster C based on labeling algorithm L's labeling decisions.

Following is described how the decisiveness values computed by the Label Ranking Module104may be used by the Label Fusion Module105to combine several cluster labeling algorithms for improving cluster labeling results. Let[k](C)=∪L∈L[k](C) denote the overall label pool based on the union of all top-k label lists suggested by each labeling algorithm L∈. The goal is to find a combined cluster labeling (fusion) score, such that the top-k labels returned by scoring labels l∈[k](C) according to that score may result in an improved cluster label suggestion by the Label Fusion Module105.

Following are the definitions of two reference data fusion algorithms, frequently used in various information retrieval tasks, namely the CombSUM and CombMNZ fusion algorithms.

Given a label l's score SL(l|C), let SLnorm(l|C) denote its normalized score. The CombSUM fusion algorithm sums over the normalized label scores given by the various labeling algorithms in L:

The CombMNZ algorithm boosts labels based on the number of top-k label lists that include each label:

The cluster labeling algorithm's decisiveness value is integrated by the Label Fusion Module105within the fusion score by simply replacing each original (normalized) label score SLnorm(l|C) with the respective boosted score, computed as:
SLOLD(l|C)wL(l|C)×SLnorm(l|C)   EQN. 5

Optionally, a label decisiveness value is used with Reciprocal Rank Fusion (RRF) by the Label Fusion Module105to produce a list of cluster labels, computed as:

RRFCLD⁡(l❘ℒ[k]⁡(C))=∑L∈ℒ⁢1rl⁡(L⁡(C))*wLnorm⁡(l❘C)+rmean⁡(L⁡(C))*(1-wLnorm⁡(l❘C))
where wLnorm(l|C) denotes the normalized decisiveness value estimate and rmean(L(C)) denotes the mean label rank position (i.e., k/2).

An embodiment of the proposed cluster labeling fusion method is evaluated using two sources of clusters data. The first source is based on the 20 News Group (20NG) collection, containing documents that were manually classified with labels into 20 different categories (each category with about 1000 documents). For example, the news groups comp.windows.x, talk.politics.guns, alt.atheism, soc.religion.christian, and the like were used to collect documents. The second source is a data collection that was gathered using the Open Directory Project (ODP), creating document clusters by random sampling of documents from 150 different ODP categories (each category with about 30-100 documents) and retrieving their contents from the world wide web. Gathered ODP clusters (categories) have diverse topics, including among others topics related to arts, technology, business, science, and the like. For example, the ODP categories are Recreation/Outdoors/Hunting, Health/Conditions_and_Diseases/Cancer, Sports/Water_Sports/Surfing, Recreation/Pets/Dogs, and the like.

The Match@k and MRR@k (Mean Reciprocal Rank) label quality measures were used for the evaluation some embodiments of the invention. The two measures evaluate a given labeling algorithm labeling algorithm's capability of providing a single correct label for a given cluster, which best describes the cluster's main topic. The Match@k measure returns1if and only if at least one correct label is located among the top-k labels proposed by the labeling algorithm. The MRR@k measure, on the other hand, returns the inverse of the rank of the first correct label in the top-k list. Otherwise, both measures return zero value.

To evaluate the relative performance of the various cluster labeling fusion algorithms that were described herein to embodiment of the present invention, two reference cluster labeling algorithms are used. The first is a direct cluster labeling algorithm, termed hereinafter as the JSD algorithm, and is based on the query difficulty model as described by Carmel et al in “What makes query difficult?” published in Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval (pages 390-397). Cluster terms are ranked by the JSD algorithm according to their relative contribution to the Jensen-Shannon divergence between the cluster and the whole collection. The distribution of terms within the cluster/collection is computed by:

P⁡(w❘Cl)=λ⁢nw∑w′∈Cl⁢nw′+(1-λ)⁢PC⁡(w)
and the JSD distance between two distributions is computed using the equations:

DJS(P⁢Q)=∑w⁢⁢P⁡(w)⁢log⁡(P⁡(w)M⁡(w))+∑w⁢⁢Q⁡(w)⁢log⁡(Q⁡(w)M⁡(w)),and⁢(M⁡(w)=12⁢(P⁡(w)+Q⁡(w)))
The top-k scored terms are then suggested as the cluster's labels.

The second, termed hereinafter the Score Prorogation (SP) algorithm, is an indirect cluster labeling algorithm, which utilizes Wikipedia categories for cluster labeling. The SP algorithm maps important terms that were extracted by a given direct labeling algorithm (e.g., JSD terms) to Wikipedia categories that may better capture the cluster's main topic. Such mapping is done by submitting the list of top-k important cluster terms as a query to an inverted index of Wikipedia documents. Then, using a voting approach, cluster labels are chosen by picking those categories that obtained the highest votes, relatively to the scores prorogated from relevant Wikipedia documents to their associated categories. The SP labeling algorithm propagates document scores to the related labels, labels scores are propagated to the related keywords, and keywords scores are propagated back to their labels. The computations to perform the SP scoring algorithm are:

The top-k labels suggested by each labeling algorithm (i.e., JSD and SP algorithms) are combined using several fusion algorithms described herein. For example, the fusion algorithms CombMNZ, CombSUM, CombMAX and Borda-Count fusion algorithms were compared with fusion methods using the cluster label's decisiveness values computed by the Label Ranking Module104, according to some embodiments of the invention.

Optionally, a training cluster of text documents is used to determine the number of sub-clusters to use and the amount of noise to introduce to each sub-cluster. For example, the training cluster has a true, known label list determined by manual inspection. For example, the manual inspection is performed incrementally for each text document in the training cluster, and after each text document receives a true list of labels, embodiments of the method are performed in the background to compare statistically the current incremental true label lists with the fused label list. When the statistical confidence and power computed between the true labels and the fused label list is above an acceptable threshold, the computerized system100may send a notification to the user performing the manual labeling of the text documents, and the fused label list presented.

In this example comparison, the 20NG collection was used to determine optimum values for θ and the number of sub-clusters (N) to use in determining each label's decisiveness value, while the large ODP collection (with 150 clusters) was used for the comparison with other algorithms. The best parameter configuration found by analysis of the 20NG collection was θ=0.05 and N=20.

The resulting analysis concludes that embodiments of the cluster labeling fusion method provided herein that consider the label's decisiveness value produce better labeling performance than considering a single labeling algorithm or fusion of labeling algorithms without the decisiveness value. Reference is now made toFIG. 5A, which is a graph of example label fusion algorithm results evaluated by MRR@K, according to some embodiments of the invention. The graph401shows the performance of several labeling algorithms, reference fusion algorithms, and embodiments of the current invention. Labeling algorithms Jensen-Shannon Divergence (JSD)416and Score Prorogation (SP)415were computed from an example cluster of documents, and combined with standard label fusion algorithms CombMNZ412, CombSUM414, CombMAX417, and Borda-Count418. The embodiments of the current invention using cluster label decisiveness (CLD) illustrated are CombMNZ(CLD)411and CombSUM(CLD)412. The graph401shows that the CLD-based fusion methods401produced consistently higher MRR@K scores than the other algorithms, as at403and404. For each k, the values reported for the CLD-based fusion methods are statistically significant (paired t-test, p-value <0.05).

Reference is now made toFIG. 5B, which is a graph of example label fusion algorithm results evaluated by Match@K, according to some embodiments of the invention. In this graph405it can be seen that the CLD-based methods406again performed consistently better using the Match@K metric than the other algorithms407.

The methods as described above are used in the fabrication of integrated circuit chips.

It is expected that during the life of a patent maturing from this application many relevant document clustering labeling algorithms will be developed and the scope of the term clustering labeling algorithm is intended to include all such new technologies a priori.

It is expected that during the life of a patent maturing from this application many relevant label fusing algorithms will be developed and the scope of the term label fusing algorithm is intended to include all such new technologies a priori.

As used herein the term “about” refers to ±10%.