System and Method for Creating Labels for Clusters

• US 20150006531A1
• Filed: 02/25/2014
• Published: 01/01/2015
• Est. Priority Date: 07/01/2013
• Status: Active Grant

• Current Assignee: TATA Consultancy Services Limited (Tata Sons Pvt Ltd.)
• Original Assignee: TATA Consultancy Services Limited (Tata Sons Pvt Ltd.)
• Inventors: Deshpande, Shailesh Shankar, Palshikar, Girish Keshav, G, Athiappan
• Granted Patent: US 10,210,251 B2
• Time in Patent Office: Days
• US Class Current: 707/737
• CPC Class Codes: G06F 16/783 using metadata automatically derived from the content

Abstract

Disclosed is a method and system for creating labels for cluster in computing environment. The system comprises receiving module, candidate items selector, combination array generator, coverage value analyzer, candidate pair selector, unique word filter and cluster label selector. Receiving module receives input data and candidate items selector selects candidate items occurring repetitively using n-gram technique to generate list of candidate items with frequency of occurrence. Combination array generator selects candidate items to populate two-dimensional array wherein each array element represents pair of n-gram. Coverage value analyzer determines coverage value for each pair of n-gram from array. Candidate pair selector selects pairs of n-gram from two-dimensional array to process and generate list of candidate pairs. The unique word filter determines number of unique words in each candidate pair. Cluster label selector sorts list of candidate pairs using coverage value and number of unique words to select cluster label.

Claims

1. A system for creating at least one label for at least one cluster in a computing environment, the system comprising:

a processor; and

a memory coupled to the processor, wherein the processor is capable of executing a plurality of modules stored in the memory, and wherein the plurality of modules comprise;

a receiving module configured to receive an input data;

a candidate items selector configured to select a plurality of candidate items occurring repetitively in the input data using a n-gram selection technique for a predefined value of n to generate a sorted list of the plurality of candidate items with a frequency of occurrence of the plurality of candidate items based on the input data;

a combination array generator configured to select a predefined number of the plurality of candidate items from the sorted list of the plurality of candidate items to populate a two-dimensional array having a plurality of elements, wherein each element of the plurality of elements of the two-dimensional array represents a pair of the plurality of candidate items;

a coverage value analyzer configured to determine a coverage value for each pair of the plurality of candidate items present in the two-dimensional array to further populate a sorted two-dimensional array;

a candidate pair selector configured to select a predefined number of pairs of the plurality of candidate items from the sorted two-dimensional array to further process and generate a list of the pairs of the plurality of candidate items;

a unique word filter configured to accept the list of the pairs of the plurality of candidate items to determine a number of unique words in each of the pairs of the plurality of candidate items; and

a cluster label selector configured to sort the list of the pairs of the plurality of candidate items using the coverage value and the number of unique words to create a sorted list of the pairs of the plurality of candidate items for selecting a cluster label from the sorted list of the pairs of the plurality of candidate items.

2. The system of claim 1, wherein the input data comprises at least one of:

a set of text documents and a set of text records associated with the at least one cluster, and wherein the plurality of candidate items comprises at least one of;

words and phrases.

3. The system of claim 1, wherein the predefined value of n using the n-gram selection technique ranges from 1 to 5.

4. The system of claim 1, wherein the list of plurality of candidate items is sorted in accordance with a descending order of the frequency of occurrence of the plurality of candidate items, wherein a foremost predefined number of the plurality of candidate items is selected from the sorted list of plurality of candidate items.

5. The system of claim 1, wherein the coverage value for each pair of the plurality of candidate items is determined to ensure a maximum coverage with a minimum overlap and the two-dimensional array is sorted in accordance with a descending order of the coverage value for each pair of the plurality of candidate items.

6. The system of claim 1, wherein the candidate pair selector is further configured to select at least a top two pairs of the plurality of candidate items from the sorted two-dimensional array.

7. The system of claim 1, wherein the cluster label selector sorts the list of the pairs of the plurality of candidate items by using at least one of:

the coverage value in a descending order and the number of unique words in an ascending order, and the coverage value in an the ascending order and the number of unique words in the descending order, to create the sorted list of the pairs of the plurality of candidate items, and wherein the cluster label selector selects at least three pairs of the plurality of candidate items from the sorted list of pairs of the plurality of candidate items to select the cluster labels.

8. The system of claim 1, wherein a unique word of the determined number of unique words further comprises a word appearing in no more than two documents in a single cluster of the at least one cluster.

9. A method for creating at least one label for at least one cluster in a computing environment, the method comprising:

receiving an input data;

selecting a plurality of candidate items occurring repetitively in the input data using a n-gram selection technique for a predefined value of n to generate a sorted list of the plurality of candidate items with a frequency of occurrence of the plurality of candidate items;

selecting a predefined number of the plurality of candidate items from the sorted list of the plurality of candidate items to populate a two-dimensional array having a plurality of elements, wherein each element of the plurality of elements of the two-dimensional array represents a pair of the plurality of candidate items;

determining a coverage value for each pair of the plurality of candidate items from the two-dimensional array to further populate a sorted two-dimensional array;

selecting a predefined number of pairs of the plurality of candidate items from the sorted two-dimensional array to further process and generate a list of the pairs of the plurality of candidate items;

accepting the list of the pairs of the plurality of candidate items to determine a number of unique words in each of the pairs of the plurality of candidate items; and

sorting the list of the pairs of the plurality of candidate items using the coverage value and the number of unique words to create a sorted list of the pairs of the plurality of candidate items for selecting a cluster label form the sorted list of the pairs of the plurality of candidate items;

wherein the receiving, the selecting the plurality of candidates, the selecting the predefined number of the plurality of candidate items, the determining the coverage value, the selecting the predefined number of pairs, the accepting the list, and the sorting the list are performed by a processor of a computerized device.

10. The method of claim 9, wherein the input data further comprises at least one of:

a set of text documents and a set of text records associated with the at least one cluster, and wherein the plurality of candidate items further comprise at least one of;

words and phrases.

11. The method of claim 9, wherein the predefined value of n using the n-gram selection technique ranges from 1 to 5.

12. The method of claim 9, wherein the list of the plurality of candidate items is sorted in accordance with a descending order of the frequency of occurrence of the plurality of candidate items, wherein a foremost predefined number of the plurality of candidate items is selected from the sorted list of the plurality of candidate items.

13. The method of claim 9, wherein the two-dimensional array is sorted in accordance with a descending order of the coverage value for each pair of the plurality of candidate items and the candidate pair selector selects pairs of the plurality of candidate items occurring foremost, wherein at least a top two pairs of the plurality of candidate items are selected from the sorted two-dimensional array.

14. The method of claim 9, wherein sorting the list of the pairs of the plurality of candidate items is performed by using at least one of:

the coverage value in a descending order and the number of unique words in an ascending order, and the coverage value in the ascending order and the number of unique words in the descending order, to create the sorted list of the pairs of the plurality of candidate items, wherein at least three pairs of the plurality of candidate items are selected from the sorted list of pairs of the plurality of candidate items to select the cluster labels.

15. The method of claim 9, wherein the step of determining the coverage value for each pair of the plurality of candidate items further comprises determining the coverage value for each pair of the plurality of candidate items to ensure a maximum coverage with a minimum overlap.

16. The method of claim 9, wherein a unique word of the determined number of unique words further comprises a word appearing in no more than two documents in a single cluster of the at least one cluster.

17. A computer program product having embodied thereon a computer program for creating at least one label for at least one cluster, the computer program product comprising:

a program code for receiving an input data;

a program code for selecting a plurality of candidate items occurring repetitively in the input data using a n-gram selection technique for a predefined value of n to generate a sorted list of the plurality of candidate items with a frequency of occurrence of the plurality of candidate items;

a program code for selecting a foremost predefined number of the plurality of candidate items from the sorted list of the plurality of candidate items to populate a two-dimensional array having a plurality of elements, wherein each element of the plurality of elements of the two-dimensional array represents a pair of the plurality of candidate items;

a program code for determining a coverage value for each pair of the plurality of candidate items from the two-dimensional array to further sort the two-dimensional array in a descending order of the coverage value for each pair of the plurality of candidate items to populate a sorted two-dimensional array;

a program code for selecting a predefined number of pairs of the plurality of candidate items from the sorted two-dimensional array occurring foremost to further process and generate a list of the pairs of plurality of candidate items;

a program code for accepting the list of the pairs of the plurality of candidate items to determine a number of unique words in each of the pairs of the plurality of candidate items; and

a program code for sorting the list of the pairs of the plurality of candidate items using the coverage value and the number of unique words to create a sorted list of the pairs of the plurality of candidate items for selecting a cluster label form the sorted list of the pairs of the plurality of candidate items.

18. The computer program product of claim 17, wherein the input data comprises at least one of:

a set of text documents and a set of text records associated with the at least one cluster, and wherein the plurality of candidate items comprises at least one of;

words and phrases.

19. The computer program product of claim 17, wherein the predefined value of n using the n-gram selection technique ranges from 1 to 5.

20. The computer program product of claim 17, wherein the list of the plurality of candidate items is sorted in accordance with a descending order of the frequency of occurrence of the plurality of candidate items, wherein the foremost predefined number of the plurality of candidate items is selected from the sorted list of the plurality of candidate items.