Landmark point selection

• US 10,002,180 B2
• Filed: 10/15/2015
• Issued: 06/19/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
• Application Number:
  US14/884,511
• Publication Number:
  US 20160034561A1
• Time in Patent Office: 978 Days
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

An exemplary method comprises receiving data points, selecting a first subset of the data points to generate an initial set of landmarks, each data point of the first subset defining a landmark point and for each non-landmark data point: calculating first data point distances between a respective non-landmark data point and each landmark point of the initial set of landmarks, identifying a first shortest data point distance from among the first data point distances between the respective non-landmark data point and each landmark point of the initial set of landmarks, and storing the first shortest data point distance as a first landmark distance for the respective non-landmark data point. The method further comprising identifying a non-landmark data point with a longest first landmark distance in comparison with other first landmark distances and adding the identified non-landmark data point associated as a first landmark point to the initial set of landmarks.

Claims

1. A method comprising:

receiving data points;

selecting a first subset of the data points to generate an initial set of landmarks, each data point of the first subset defining a landmark point;

for each non-landmark data point,

calculating first data point distances between a respective non-landmark data point and each landmark point of the initial set of landmarks;

identifying a first shortest data point distance from among the first data point distances between the respective non-landmark data point and each landmark point of the initial set of landmarks; and

storing the first shortest data point distance as a first landmark distance for the respective non-landmark data point;

identifying a non-landmark data point with a longest first landmark distance in comparison with other first landmark distances of other non-landmark data points; and

adding the non-landmark data point associated with the longest first landmark distance as a first landmark point to the initial set of landmarks to generate an expanded set of landmark points.

2. The method of claim 1, further comprising:

storing a set of longest landmark distances for the non-landmark data points of the expanded set of landmark points;

calculating second data point distances between the non-landmark data points associated with the set of longest landmark distances and each landmark point of the expanded set of landmark points, the expanded set of landmark points including the first landmark point; and

adding the non-landmark data point associated with a longest second landmark distance to the expanded set of landmark points, thereby categorizing the non-landmark data point as a new landmark point.

3. The method of claim 2, further comprising:

determining if the expanded set of landmark points includes a predetermined number of landmark points;

if the expanded set of landmark points includes less than the predetermined number of landmark points;

storing another set of longest second landmark distances for the non-landmark data points of the expanded set of landmark points;

calculating third data point distances between the non-landmark data points associated with the set of longest second landmark distances and each landmark point of the first and second sets of landmark points, the first set and second set of landmark points including the first and second landmark point; and

adding the non-landmark data point associated with the longest second landmark distance as a another landmark point to the set of landmark points; and

if the expanded set of landmark points includes more than the predetermined number of landmark points, generating a visualization of nodes and edges using the expanded set of landmark points instead of the received data points.

4. The method of claim 1, wherein the expanded set of landmark points is an approximation of the received data points.

5. The method of claim 1, further comprising:

before the first subset of the data points are selected to generate an initial set of landmarks;

accessing a data structure containing information;

generating a mathematical reference space; and

mapping a similarity space using the information from the data structure into the mathematical reference space to generate the data points, wherein each data point is defined by the mapping into the mathematical reference space.

6. The method of claim 5, further comprising:

generating a cover for the landmark points of the expanded set of landmark points in the mathematical reference space based on a resolution;

clustering the landmark points of the expanded set of landmark points into subsets using a metric to generate subsets of the landmark points of the expanded set of landmark points to determine each individual node of a plurality of nodes, each of the nodes of the plurality of nodes comprising members representative of at least one subset of the landmark points of the expanded set of landmark points; and

generating an interactive visualization comprising nodes and a plurality of edges wherein each of the edges of the plurality of edges connects nodes with shared members.

7. The method of claim 5, further comprising:

generating a cover for the data points in the mathematical reference space based on a resolution;

clustering the data points into subsets using a metric to generate subsets of the data points to determine each individual node of a plurality of nodes, each of the nodes of the plurality of nodes comprising members representative of at least one subset of the data points, each node defining a data point; and

generating an interactive visualization comprising nodes of landmark points of the expanded set of landmark points and a plurality of edges wherein each of the edges of the plurality of edges connects nodes with shared members.

8. The method of claim 1 wherein selection of the first subset of the data points is random.

9. The method of claim 1, wherein receiving data points comprises storing the data points in a memory system and the initial set of landmarks is stored in a non-transitory storage system.

10. The method of claim 1, wherein identifying the non-landmark data point with the longest first landmark distance in comparison with other first landmark distances of other non-landmark data points comprises identifying a predetermined number of non-landmark data points, each of the predetermined number of non-landmark data points having longer first landmark distances in comparison with the other first landmark distances of the other non-landmark data points.

11. The method of claim 10, wherein adding the non-landmark data point associated with the longest first landmark distance as a first landmark point to the initial set of landmarks comprises adding the predetermined number of non-landmark data points associated with the longer first landmark distances to the initial set of landmarks.

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

receiving data points;

selecting a first subset of the data points to generate an initial set of landmarks, each data point of the first subset defining a landmark point;

for each non-landmark data point,

calculating first data point distances between a respective non-landmark data point and each landmark point of the initial set of landmarks;

identifying a first shortest data point distance from among the first data point distances between the respective non-landmark data point and each landmark point of the initial set of landmarks; and

storing the first shortest data point distance as a first landmark distance for the respective non-landmark data point;

identifying a non-landmark data point with a longest first landmark distance in comparison with other first landmark distances of other non-landmark data points; and

adding the non-landmark data point associated with the longest first landmark distance as a first landmark point to the initial set of landmarks to generate an expanded set of landmark points.

13. The non-transitory computer readable medium of claim 12, the method further comprising:

storing a set of longest landmark distances for the non-landmark data points of the expanded set of landmark points;

calculating second data point distances between the non-landmark data points associated with the set of longest landmark distances and each landmark point of the expanded set of landmark points, the expanded set of landmark points including the first landmark point; and

adding the non-landmark data point associated with a longest second landmark distance to the expanded set of landmark points, thereby categorizing the non-landmark data point as a new landmark point.

14. The non-transitory computer readable medium of claim 13, the method further comprising:

determining if the expanded set of landmark points includes a predetermined number of landmark points;

if the expanded set of landmark points includes less than the predetermined number of landmark points;

storing another set of longest second landmark distances for the non-landmark data points of the expanded set of landmark points;

calculating third data point distances between the non-landmark data points associated with the set of longest second landmark distances and each landmark point of the first and second sets of landmark points, the first set and second set of landmark points including the first and second landmark point; and

adding the non-landmark data point associated with the longest second landmark distance as a another landmark point to the set of landmark points; and

if the expanded set of landmark points includes more than the predetermined number of landmark points, generating a visualization of nodes and edges using the expanded set of landmark points instead of the received data points.

15. The non-transitory computer readable medium of claim 12, the method further comprising:

before the first subset of the data points are selected to generate an initial set of landmarks;

accessing a data structure containing information;

generating a mathematical reference space; and

mapping a similarity space using the information from the data structure into the mathematical reference space to generate the data points, wherein each data point is defined by the mapping into the mathematical reference space.

16. The non-transitory computer readable medium of claim 15, the method further comprising:

generating a cover for the landmark points of the expanded set of landmark points in the mathematical reference space based on a resolution;

clustering the landmark points of the expanded set of landmark points into subsets using a metric to generate subsets of the landmark points of the expanded set of landmark points to determine each individual node of a plurality of nodes, each of the nodes of the plurality of nodes comprising members representative of at least one subset of the landmark points of the expanded set of landmark points; and

generating an interactive visualization comprising nodes and a plurality of edges wherein each of the edges of the plurality of edges connects nodes with shared members.

17. The non-transitory computer readable medium of claim 15, the method further comprising:

generating a cover for the data points in the mathematical reference space based on a resolution;

clustering the data points into subsets using a metric to generate subsets of the data points to determine each individual node of a plurality of nodes, each of the nodes of the plurality of nodes comprising members representative of at least one subset of the data points, each node defining a data point; and

generating an interactive visualization comprising nodes of landmark points of the expanded set of landmark points and a plurality of edges wherein each of the edges of the plurality of edges connects nodes with shared members.

18. The non-transitory computer readable medium of claim 12, wherein identifying the non-landmark data point with the longest first landmark distance in comparison with other first landmark distances of other non-landmark data points comprises identifying a predetermined number of non-landmark data points, each of the predetermined number of non-landmark data points having longer first landmark distances in comparison with the other first landmark distances of the other non-landmark data points.

19. The non-transitory computer readable medium of claim 18, wherein adding the non-landmark data point associated with the longest first landmark distance as a first landmark point to the initial set of landmarks comprises adding the predetermined number of non-landmark data points associated with the longer first landmark distances to the initial set of landmarks.

20. A system comprising:

an input module configured to receive data points;

a random landmark selection module configured to select a first subset of the data points to generate an initial set of landmarks, each data point of the first subset defining a landmark point;

a distance calculation module configured to, for each non-landmark data point,

calculate first data point distances between a respective non-landmark data point and each landmark point of the initial set of landmarks;

identify a first shortest data point distance from among the first data point distances between the respective non-landmark data point and each landmark point of the initial set of landmarks; and

store the first shortest data point distance as a first landmark distance for the respective non-landmark data point;

a landmark distance comparison module configured to identify a non-landmark data point with a longest first landmark distance in comparison with other first landmark distances of other non-landmark data points; and

a landmark assignment module configured to add the non-landmark data point associated with the longest first landmark distance as a first landmark point to the initial set of landmarks to generate an expanded set of landmark points.