Systems and methods for capture of relationships within information

• US 10,042,959 B2
• Filed: 03/05/2015
• Issued: 08/07/2018
• Est. Priority Date: 03/05/2014
• Status: Active Grant

• Current Assignee: SymphonyAI Sensa LLC (Fortive Corp.)
• Original Assignee: Ayasdi, Inc. (Fortive Corp.)
• Inventors: Sexton, Harlan, Kloke, Jennifer
• Primary Examiner(s): VO, TRUONG V
• Application Number:
  US14/639,954
• Publication Number:
  US 20150254370A1
• Time in Patent Office: 1,251 Days
• CPC Class Codes: G06F 16/26 Visual data mining; Browsing structured data
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs
• CPC Class Codes: G16H 50/70 for mining of medical data, e.g. analysing previous cases of other patients
• CPC Class Codes: G16Z 99/00 Subject matter not provided for in other main groups of this subclass

Abstract

Exemplary systems and methods to improve capture of relationships within information are provided. In various embodiments, a system comprises a landmark module configured to choose a set of landmarks from data in a finite metric space, the set of landmarks being a subset of points in the finite metric space, a nearest neighbor module configured to compute, for each landmark, a predetermined number of nearest neighbor landmarks in the set of landmarks, a graph construction module configured to identify at least one pair of landmarks that are nearest neighbors to each other, an edge generator module configured to add an edge between the at least one pair of landmarks, and a non-landmark projection module configured to project non-landmark points based on the landmarks and one or more edges thereby enabling at least one shape to indicate relationships in the data.

Claims

1. A system comprising:

memory;

at least one processor;

an input module configured to control the at least one processor to receive a multidimensional dataset, each data point in the multidimensional dataset having multiple dimensions, each dimension having a value;

a landmark module configured to control the at least one processor to choose a set of landmarks from the data points, the set of landmarks being a subset of the multidimensional dataset;

an analysis module configured to control the at least one processor to map each landmark of the set of landmarks into a finite metric space based on the values of the dimensions of each landmark;

a nearest neighbor module configured to control the at least one processor to compute, for each landmark, a predetermined number of nearest neighbor landmarks in the set of landmarks, distance between every two landmarks being based on dimensions of each of the two landmarks and the finite metric space;

a graph construction module configured to control the at least one processor to identify at least one pair of landmarks that are nearest neighbors to each other relative to other pairs of landmarks;

an edge generator module configured to control the at least one processor to add an edge between the at least one pair of landmarks; and

a non-landmark projection module configured to control the at least one processor to, for each data point in the multidimensional dataset that is not a member of the set of landmarks, determine distances of each of the data points that is not a member of the set of landmarks to the finite metric space to at least one of the landmarks and project each data point that is not a member of the set of landmarks to the finite metric space based on the determined distances, thereby enabling at least one shape to indicate relationships in the data.

2. The system of claim 1 further comprising a filter module configured to control the at least one processor to apply one or more metric functions to the received multidimensional dataset to generate the finite metric space.

3. The system of claim 1 further comprising a visualization module configured to control the at least one processor to generate a visualization of the landmarks, one or more edges, and each data point in the multidimensional dataset that is not a member of the set of landmarks.

4. The system of claim 1 whereby the landmarks, one or more edges, and each data point in the multidimensional dataset that is not a member of the set of landmarks characterize a reference space and the system further comprises a resolution module configured to cluster at least some of the multidimensional dataset based on groupings in the reference space, the groupings being generated by a cover function on the reference space.

5. The system of claim 4 further comprising a visualization module configured to control the at least one processor to generate a visualization depicting nodes, each node associated with a subset of the received multidimensional dataset based on a grouping of the data from the cover function on the reference space, and edges for connecting nodes that share at least some of the same received data.

6. The system of claim 5 wherein the edge generator module is further configured to identify components in the reference space, each component including a subset of landmarks wherein the subset of landmarks of one component do not share any paths with a subset of landmarks of another component.

7. The system of claim 6 wherein the edge generator module is further configured to compute a component strength between a first and second component of the identified components, the strength being based, at least in part, on scoring a number of nearest neighbors of each landmark in the first component, the nearest neighbors residing in the second component, and generate a component pair score using the scoring of the number of nearest neighbors of each landmark in the first component that reside in the second component.

8. The system of claim 7 wherein the edge generator module generates one or more edges between landmarks of components associated with a highest component pair score as compared to other components associated with lower component pair scores.

9. The system of claim 7 wherein the edge generator module is further configured to compute the component strength between the first and second component based, at least in part, on scoring a number of nearest neighbors of each landmark in the second component that reside in the first component, wherein the component pair score is based, at least in part, on the scoring of the number of nearest neighbors of each landmark in the second component that reside in the first component.

10. The system of claim 1 wherein the value is null.

11. The system of claim 1 wherein the landmark module chooses the set of landmarks randomly from the data points.

12. A method comprising:

receiving a multidimensional dataset, each data point in the multidimensional dataset having multiple dimensions, each dimension having a value;

selecting a set of landmarks from the data points, the set of landmarks being a subset of the multidimensional dataset;

mapping each landmark of the set of landmarks into a finite metric space based on the values of the dimensions of each landmark;

computing, for each landmark, a predetermined number of nearest neighbor landmarks in the set of landmarks, distance between every two landmarks being based on dimensions of each of the two landmarks and the finite metric space;

identifying at least one pair of landmarks that are nearest neighbors to each other relative to other pairs of landmarks;

adding an edge between the at least one pair of landmarks; and

for each data point in the multidimensional dataset that is not a member of the set of landmarks;

determining distances of each of the data points that is not a member of the set of landmarks to the finite metric space to at least one of the landmarks, and

projecting each data point that is not a member of the set of landmarks to the finite metric space based on the determined distances, thereby enabling at least one shape to indicate relationships in the data.

13. The method of claim 12 further comprising applying one or more metric functions to the received multidimensional dataset to generate the finite metric space.

14. The method of claim 12 further comprising generating a visualization of the landmarks, one or more edges, and each data point in the multidimensional dataset that is not a member of the set of landmarks.

15. The method of claim 12 whereby the landmarks, one or more edges, and each data point in the multidimensional dataset that is not a member of the set of landmarks characterize a reference space and the method further comprises clustering at least some of the multidimensional dataset based on groupings in the reference space, the groupings being generated by a cover function on the reference space.

16. The method of claim 15 further comprising generating a visualization depicting nodes, each node associated with a subset of the received multidimensional dataset based on a grouping of the data from the cover function on the reference space, and edges for connecting nodes that share at least some of the same received data.

17. The method of claim 16 further comprising identifying components in the reference space, each component including a subset of landmarks wherein the subset of landmarks of one component do not share any paths with a subset of landmarks of another component.

18. The method of claim 17 further comprising computing a component strength between a first and second component of the identified components, the strength being based, at least in part, on scoring a number of nearest neighbors of each landmark in the first component, the nearest neighbors residing in the second component, and generating a component pair score using the scoring of the number of nearest neighbors of each landmark in the first component that reside in the second component.

19. The method of claim 18 further comprising generating one or more edges between landmarks of components associated with a highest component pair score as compared to other components associated with lower component pair scores.

20. The method of claim 18 further comprising computing the component strength between the first and second component based, at least in part, on scoring a number of nearest neighbors of each landmark in the second component that reside in the first component, wherein the component pair score is based, at least in part, on the scoring of the number of nearest neighbors of each landmark in the second component that reside in the first component.

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

receiving a multidimensional dataset, each data point in the multidimensional dataset having multiple dimensions, each dimension having a value;

selecting a set of landmarks from the data points in a finite metric space, the set of landmarks being a subset of the multidimensional dataset points in the finite metric space;

mapping each landmark of the set of landmarks into a finite metric space based on the values of the dimensions of each landmark;

computing, for each landmark, a predetermined number of nearest neighbor landmarks in the set of landmarks, distance between every two landmarks being based on dimensions of each of the two landmarks and the finite metric space;

identifying at least one pair of landmarks that are nearest neighbors to each other relative to other pairs of landmarks;

adding an edge between the at least one pair of landmarks; and

for each data point in the multidimensional dataset that is not a member of the set of landmarks;

determining distances of each of the data points that is not a member of the set of landmarks to the finite metric space to at least one of the landmarks, and

projecting each data point that is not a member of the set of landmarks to the finite metric space based on the determined distances, thereby enabling at least one shape to indicate relationships in the data.