Systems and methods for metric data smoothing

• US 10,114,823 B2
• Filed: 11/04/2014
• Issued: 10/30/2018
• Est. Priority Date: 11/04/2013
• Status: Active Grant

• Current Assignee: SymphonyAI Sensa LLC (Fortive Corp.)
• Original Assignee: Ayasdi, Inc. (Fortive Corp.)
• Inventors: Carlsson, Gunnar, Bak, Anthony, Kloke, Jennifer, Mann, Benjamin, Sexton, Harlan
• Primary Examiner(s): Coby, Frantz
• Application Number:
  US14/533,058
• Publication Number:
  US 20150127650A1
• Time in Patent Office: 1,456 Days
• Field of Search: 707737, 707742, 707727-731
• CPC Class Codes: G06F 16/3334 Selection or weighting of terms from queries, including natural language queries
• CPC Class Codes: G06F 16/93 Document management systems

Abstract

An exemplary method may comprise receiving a matrix for a set of documents, each cell of the matrix including a frequency value indicating a number of instances of a corresponding text segment in a corresponding document, receiving an indication of a relationship between two text segments, each of the two text segments associated with a first column and a second column, respectively, of the matrix, adjusting, for each document, a frequency value of the second column based on the frequency value of the first column, projecting each frequency value into a reference space to generate a set of projection values, identifying a plurality of subsets of the reference space, clustering, for each subset of the plurality of subsets, at least some documents that correspond to projection values, and generating a graph of nodes, each of the nodes identifying one or more of the documents corresponding to each cluster.

Claims

1. A computer implemented method comprising:

a processing device storing executable instructions for receiving a matrix for a set of documents, each row of the matrix corresponding to each document of the set of documents and each column of the matrix corresponding to a text segment that is in at least one document of the set of documents, each cell of the matrix including a frequency value indicating a number of instances of a corresponding text segment in a corresponding document;

receiving an indication of a relationship between two text segments, each of the two text segments associated with a first column and a second column, respectively, of the matrix;

adjusting, for each document, a frequency value of the second column based on a frequency value of the first column;

projecting each frequency value of the matrix into a reference space to generate a set of projection values in the reference space;

identifying a plurality of subsets of the reference space, at least some of the plurality of subsets including at least some of the projection values of the set of projection values in the reference space;

clustering, for each subset of the plurality of subsets, at least some documents of the set of documents that correspond to a subset of the set of projection values to generate clusters of one or more documents; and

generating a graph of nodes, each of the nodes identifying one or more of the documents corresponding to each cluster.

2. The method of claim 1, wherein clustering, for each subset of the plurality of subsets, at least some documents of the set of documents comprises:

determining a distance between at least two documents of the set of documents corresponding to at least two projection values in a first subset of the plurality of subsets;

comparing the distance to a threshold value; and

clustering each of the at least two documents in two different clusters or one cluster based on the comparison.

3. The method of claim 1, wherein generating the graph of nodes comprises generating a graphical representation of the graph of nodes.

4. The method of claim 1, further comprising generating a link between at least two nodes of the graph of nodes, each node corresponding to different clusters, a first document of the set of documents being a member of the different clusters.

5. The method of claim 4, wherein generating the graph of nodes comprises generating a graphical representation of the graph of nodes and generating the link comprises generating an edge between the at least two nodes.

6. The method of claim 1, wherein the plurality of subsets of the reference space have a non-empty intersection.

7. The method of claim 1, wherein adjusting, for each document, the frequency value comprises generating a third column of the matrix, each cell of the third column containing the adjusted frequency value for the corresponding document and the second column of frequency values remaining unchanged.

8. The method of claim 1, wherein projecting each frequency value comprises projecting each frequency value, including each of the adjusted frequency values, into the reference space to generate the set of projection values in the reference space.

9. The method of claim 8, wherein the second column remains unchanged.

10. The method of claim 1, wherein the text segments are from at least one dictionary of text segments.

11. The method of claim 1, wherein one or more of the text segments are words.

12. The method of claim 1, wherein one or more of the text segments are n-grams.

13. The method of claim 1, wherein each frequency value is a term frequency-inverse document frequency for the corresponding text segment and the corresponding document.

14. A system comprising:

a processing device storing;

an input module configured to receive a matrix for a set of documents, each row of the matrix corresponding to each document of the set of documents and each column of the matrix corresponding to a text segment that is in at least one document of the set of documents, each cell of the matrix including a frequency value indicating a number of instances of a corresponding text segment in a corresponding document;

a smoothing module configured to receive an indication of a relationship between two text segments, each of the two text segments associated with a first column and a second column, respectively, of the matrix and to adjust, for each document, a frequency value of the second column based on a frequency value of the first column; and

an analysis module configured to project each frequency value of the matrix into a reference space to generate a set of projection values in the reference space, to identify a plurality of subsets of the reference space, at least some of the plurality of subsets including at least some of the projection values of the set of projection values in the reference space, to cluster, for each subset of the plurality of subsets, at least some documents of the set of documents that correspond to a subset of the set of projection values to generate clusters of one or more documents, and to generate a graph of nodes, each of the nodes identifying one or more of the documents corresponding to each cluster.

15. The system of claim 14, wherein the analysis module configured to cluster, for each subset of the plurality of subsets, at least some documents of the set of documents comprises the analysis module configured to:

determine a distance between at least two documents of the set of documents corresponding to at least two projection values in a first subset of the plurality of subsets;

compare the distance to a threshold value; and

cluster each of the at least two documents in two different clusters or one cluster based on the comparison.

16. The system of claim 14, further comprising a visualization module configured to generate a graphical representation of the graph of nodes.

17. The system of claim 14, wherein the analysis module is further configured to generate a link between at least two nodes of the graph of nodes, each node corresponding to different clusters, a first document of the set of documents being a member of the different clusters.

18. The system of claim 17, further comprising a visualization module configured to generate an edge between the at least two nodes.

19. The system of claim 14, wherein the plurality of subsets of the reference space have a non-empty intersection.

20. The system of claim 14, wherein the smoothing module configured to adjust, for each document, the frequency value comprises the smoothing module configured to generate a third column of the matrix, each cell of the third column containing the adjusted frequency value for the corresponding document and the second column of frequency values remaining unchanged.

21. The system of claim 14, wherein the analysis module configured to project each frequency value comprises the analysis module configured to project each frequency value, including each of the adjusted frequency values, into the reference space to generate the set of projection values in the reference space.

22. The system of claim 21, wherein the second column remains unchanged.

23. The system of claim 14, wherein the text segments are from at least one dictionary of text segments.

24. The system of claim 14, wherein one or more of the text segments are words.

25. The system of claim 14, wherein one or more of the text segments are n-grams.

26. The system of claim 14, wherein each frequency value is a term frequency-inverse document frequency for the corresponding text segment and the corresponding document.

27. A non-transitory computer readable medium comprising instructions, the instructions being executable by a processing device to perform a method, the method comprising:

receiving a matrix for a set of documents, each row of the matrix corresponding to each document of the set of documents and each column of the matrix corresponding to a text segment that is in at least one document of the set of documents, each cell of the matrix including a frequency value indicating a number of instances of a corresponding text segment in a corresponding document;

receiving an indication of a relationship between two text segments, each of the two text segments associated with a first column and a second column, respectively, of the matrix;

adjusting, for each document, a frequency value of the second column based on a frequency value of the first column;

projecting each frequency value of the matrix into a reference space to generate a set of projection values in the reference space;

identifying a plurality of subsets of the reference space, at least some of the plurality of subsets including at least some of the projection values of the set of projection values in the reference space;

clustering, for each subset of the plurality of subsets, at least some documents of the set of documents that correspond to a subset of the set of projection values to generate clusters of one or more documents; and

generating a graph of nodes, each of the nodes identifying one or more of the documents corresponding to each cluster.