Systems and methods for capture of relationships within information
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.
1. A system comprising:
at least one processor;
memory including executable instructions to configure the at least one processor to:
receive a multidimensional dataset, each data point in the multidimensional dataset having multiple dimensions;
receive a set of landmarks from the data points of the multidimensional dataset, the set of landmarks being a subset of the multidimensional dataset;
map each of the set of landmarks into a finite metric space based on values of the dimensions of each landmark;
compute, for each landmark, a plurality 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;
identify at least one pair of landmarks that are nearest neighbors to each other relative to the other pairs of landmarks;
add 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:
determine distances of each of the data points that is not the member of the set of landmarks to the finite metric space to at least one of the landmarks points, 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 wherein the at least one processor is further configured by the executable instructions to apply one or more metric functions to the received multidimensional dataset to generate the finite metric space.
3. The system of claim 1 wherein the at least one processor is further configured by the executable instructions 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 wherein the at least one processor is further configured by the executable instructions 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 wherein the at least one processor is further configured by the executable instructions 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 at least one processor is further configured by the executable instructions to identify components in the reference space, each component including a subset of landmarks wherein the subset of landmarks from one component do not share any paths with a subset of landmarks of another component.
7. The system of claim 6 wherein the at least one processor is further configured by the executable instructions to compute a component strength between a first and second component of the identified component, 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.
8. The system of claim 7 wherein the at least one processor is further configured by the executable instructions to generate one or more edges between landmarks of components associated with the highest component pair score as compared to other components associated with lower component pair scores.
9. The system of claim 7 wherein the at least one processor is further configured by the executable instructions 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 at least one value of the dimensions of each landmark is null.
11. The system of claim 1 wherein the at least one processor is further configured by the executable instructions to choose the set of landmarks randomly from the data points.
12. A non-transitory computer readable medium, the nontransitive 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;
receiving a set of landmarks from the data points, the set of landmarks being a subset of the multidimensional dataset;
mapping each of the set of landmarks into a finite metric space based on values of the dimensions of each landmark;
computing, for each landmark, a plurality 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 the 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 the member of the set of landmarks to the finite metric space to at least one of the landmarks points, 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 non-transitory computer readable medium of claim 12 wherein the method further comprises applying one or more metric functions to the received multidimensional dataset to generate the finite metric space.
14. The non-transitory computer readable medium of claim 12 wherein the method further comprises 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 non-transitory computer readable medium 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 non-transitory computer readable medium of claim 12 wherein the method further comprises 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 non-transitory computer readable medium of claim 16 wherein the method further comprises identifying components in the reference space, each component including a subset of landmarks wherein the subset of landmarks from one component do not share any paths with a subset of landmarks of another component.
18. The non-transitory computer readable medium of claim 17 wherein the method further comprises computing a component strength between a first and second component of the identified component, 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 non-transitory computer readable medium of claim 18 wherein the method further comprises generating one or more edges between landmarks of components associated with the highest component pair score as compared to other components associated with lower component pair scores.
20. The non-transitory computer readable medium of claim 18 wherein the method further comprises 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 nontransitive 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;
receiving a set of landmarks from the data points, the set of landmarks being a subset of the multidimensional dataset;
mapping each of the set of landmarks into a finite metric space based on values of the dimensions of each landmark;
computing, for each landmark, a plurality 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 the 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 the member of the set of landmarks to the finite metric space to at least one of the landmarks points, 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.