System, method, and computer program product for representing proximity data in a multi-dimensional space

• US 6,453,246 B1
• Filed: 05/07/1998
• Issued: 09/17/2002
• Est. Priority Date: 11/04/1996
• Status: Expired due to Term

• Current Assignee: 3-Dimensional Pharmaceuticals, Inc. (Johnson & Johnson)
• Original Assignee: 3-Dimensional Pharmaceuticals, Inc. (Johnson & Johnson)
• Inventors: Labanov, Victor S., Salemme, Francis R., Agrafiotis, Dimitris K.
• Primary Examiner(s): WACHSMAN, HAL D
• Application Number:
  US09/073,845
• Time in Patent Office: 1,594 Days
• Field of Search: 702/22, 702/27, 702/28, 702/30-32, 702/155, 702/159, 702/179, 702/181, 702/FOR.105, 702/FOR.104, 702/FOR.131, 702/FOR-115, 702/FOR.132, 702/FOR.134, 702/FOR.139, 702/FOR.145, 702/FOR.170, 702/FOR.171, 706/15, 706/20, 706/21, 707/6, 707/102, 703/12, 703/2, 700/266, 700/268, 345/149, 382/113, 382/155-160, 382/224, 382/226-228, 382/225
• US Class Current: 702/27
• CPC Class Codes: B01J 2219/00689 using computers
• CPC Class Codes: B01J 2219/007 Simulation or vitual synthesis
• CPC Class Codes: C40B 40/00 Libraries per se, e.g. arrays, mixtures
• CPC Class Codes: G06F 18/2137 based on criteria of topology preservation, e.g. multidimensional scaling or self-organising maps
• CPC Class Codes: G06T 7/62 of area, perimeter, diameter or volume
• CPC Class Codes: G16C 20/70 Machine learning, data mining or chemometrics
• CPC Class Codes: G16C 20/80 Data visualisation

Abstract

A system, method and computer program product for representing precise or imprecise measurements of similarity/dissimilarity (relationships) between objects as distances between points in a multi-dimensional space that represents the objects. Self-organizing principles are used to iteratively refine an initial (random or partially ordered) configuration of points using stochastic relationship/distance errors. The data can be complete or incomplete (i.e. some relationships between objects may not be known), exact or inexact (i.e. some or all of the relationships may be given in terms of allowed ranges or limits), symmetric or asymmetric (i.e. the relationship of object A to object B may not be the same as the relationship of B to A) and may contain systematic or stochastic errors. The relationships between objects may be derived directly from observation, measurement, a priori knowledge, or intuition, or may be determined indirectly using any suitable technique for deriving proximity (relationship) data.

Claims

1. A computerized method for generating mapping coordinates, wherein one or more pairs of objects are related by associated pair-wise relationships with bounded uncertainties, the method comprising the steps of:

(1) placing a set of objects on a display map;

(2) selecting a sub-set of objects from the set of objects, wherein the sub-set of objects includes at least one associated relationship between the objects in the sub-set;

(3) revising at least one distance between the objects on the display map based on the at least one associated relationship and the at least one distance, only when the at least one distance falls outside a set of allowable ranges of relationship values;

(4) repeating steps (2) and (3) for additional sub-sets of objects from the set of objects; and

(5) generating mapping coordinates for the set of objects.

2. The method according to claim 1, wherein step (2) comprises the step of:

selecting a pair of objects having an associated pair-wise relationship.

3. The method according to claim 1, wherein the associated pair-wise relationships between one or more pairs of objects are unknown, the method further comprising the steps of:

performing steps (2) through (4) only for pairs of objects for which an associated pair-wise relationship is known; and

allowing distances between objects on the display map for which associated pair-wise relationships are not known to adapt during performance of steps (2) through (4).

4. The method according to claim 1, wherein step (3) comprises the step of:

revising the at least one distance based on a learning rate.

5. The method according to claim 1, wherein step (3) comprises the step of:

revising the at least one distance based on a fixed learning rate.

6. The method according to claim 1, wherein step (3) comprises the step of:

revising the at least one distance based on a variable learning rate.

7. The method according to claim 1, wherein step (3) comprises the step of:

revising the at least one distance based on a learning rate that is a function of the associated pair-wise relationship between the pair of objects.

8. The method according to claim 1, wherein step (3) comprises the step of:

revising the at least one distance based on a learning rate that is a function of at least one object of the pair of objects.

9. The method according to claim 1, wherein step (3) comprises the step of:

revising the at least one distance based on a learning rate that is a function of the selected pair of objects.

10. The method according to claim 1, wherein step (3) comprises the step of:

revising the at least one distance using a conventional multi-dimensional scaling technique.

11. The method according to claim 1, wherein step (3) comprises the step of:

revising the at least one distance using a conventional non-linear mapping technique.

12. The method according to claim 1, wherein step (3) comprises the steps of:

computing an error function value using a conventional technique; and

revising the at least one distance using a gradient descent procedure.

13. The method according to claim 1, wherein that the objects do not represent chemical objects.

14. A computerized method for generating mapping coordinates, wherein one or more pairs of objects are related by associated pair-wise relationships with bounded uncertainties, the method comprising the steps of:

(1) placing a set of objects on a display map;

(2) selecting a sub-set of objects from the set of objects, wherein the sub-set of objects includes at least one associated relationship between the objects in the sub-set;

(3) revising at least one distance between the objects on the display map based on the at least one associated relationship and the at least one distance, only when the at least one distance falls above an upper limit of allowable relationship values;

(4) repeating steps (2) and (3) for additional sub-sets of objects from the set of objects; and

(5) generating mapping coordinates for the set of objects.

15. The method according to claim 14, wherein step (2) comprises the step of:

selecting a pair of objects having an associated pair-wise relationship.

16. The method according to claim 14, wherein the associated pair-wise relationships between one or more pairs of objects are unknown, the method further comprising the steps of:

performing steps (2) through (4) only for pairs of objects for which an associated pair-wise relationship is known; and

allowing distances between objects on the display map for which associated pair-wise relationships are not known to adapt during performance of steps (2) through (4).

17. The method according to claim 14, wherein step (3) comprises the step of:

revising the at least one distance based on a learning rate.

18. The method according to claim 14, wherein step (3) comprises the step of:

revising the at least one distance based on a fixed learning rate.

19. The method according to claim 14, wherein step (3) comprises the step of:

revising the at least one distance based on a variable learning rate.

20. The method according to claim 14, wherein step (3) comprises the step of:

revising the at least one distance based on a learning rate that is a function of the associated pair-wise relationship between the pair of objects.

21. The method according to claim 14, wherein step (3) comprises the step of:

revising the at least one distance based on a learning rate that is a function of at least one object of the pair of objects.

22. The method according to claim 14, wherein step (3) comprises the step of:

revising the at least one distance based on a learning rate that is a function of the selected pair of objects.

23. The method according to claim 14, wherein step (3) comprises the step of:

revising the at least one distance using a conventional multi-dimensional scaling technique.

24. The method according to claim 14, wherein step (3) comprises the step of:

revising the at least one distance using a conventional non-linear mapping technique.

25. The method according to claim 14, wherein step (3) comprises the steps of:

computing an error function value using a conventional technique; and

revising the at least one distance using a gradient descent procedure.

26. The method according to claim 14, wherein that the objects do not represent chemical objects.

27. A computerized method for generating mapping coordinates, wherein one or more pairs of objects are related by associated pair-wise relationships with bounded uncertainties, the method comprising the steps of:

(1) placing a set of objects on a display map;

(2) selecting a sub-set of objects from the set of objects, wherein the sub-set of objects includes at least one associated relationship between the objects in the sub-set;

(3) revising at least one distance between the objects on the display map based on the at least one associated relationship and the at least one distance, only when the at least one distance falls below a lower limit of allowable relationship values;

(4) repeating steps (2) and (3) for additional sub-sets of objects from the set of objects; and

(5) generating mapping coordinates for the set of objects.

28. The method according to claim 27, wherein step (2) comprises the step of:

selecting a pair of objects having an associated pair-wise relationship.

29. The method according to claim 27, wherein the associated pair-wise relationships between one or more pairs of objects are unknown, the method further comprising the steps of:

performing steps (2) through (4) only for pairs of objects for which an associated pair-wise relationship is known; and

allowing distances between objects on the display map for which associated pair-wise relationships are not known to adapt during performance of steps (2) through (4).

30. The method according to claim 27, wherein step (3) comprises the step of:

revising the at least one distance based on a learning rate.

31. The method according to claim 27, wherein step (3) comprises the step of:

revising the at least one distance based on a fixed learning rate.

32. The method according to claim 27, wherein step (3) comprises the step of:

revising the at least one distance based on a variable learning rate.

33. The method according to claim 27, wherein step (3) comprises the step of:

revising the at least one distance based on a learning rate that is a function of the associated pair-wise relationship between the pair of objects.

34. The method according to claim 27, wherein step (3) comprises the step of:

revising the at least one distance based on a learning rate that is a function of at least one object of the pair of objects.

35. The method according to claim 27, wherein step (3) comprises the step of:

revising the at least one distance based on a learning rate that is a function of the selected pair of objects.

36. The method according to claim 27, wherein step (3) comprises the step of:

revising the at least one distance using a conventional multi-dimensional scaling technique.

37. The method according to claim 27, wherein step (3) comprises the step of:

revising the at least one distance using a conventional non-linear mapping technique.

38. The method according to claim 27, wherein step (3) comprises the steps of:

computing an error function value using a conventional technique; and

revising the at least one distance using a gradient descent procedure.

39. The method according to claim 27, wherein that the objects do not represent chemical objects.

40. A computerized method for generating mapping coordinates, wherein one or more pairs of objects are related by associated pair-wise relationships with unbounded uncertainties, the method comprising the steps of:

(1) placing a set of objects on a display map;

(2) identifying at least one pair of objects for which an associated pair-wise relationship contains an unbounded uncertainty;

(3) removing the associated pair-wise relationships with the unbounded uncertainties identified in step (2);

(4) selecting a sub-set of objects from the set of objects, wherein the sub-set of objects includes at least one associated relationship between the objects in the sub-set;

(5) revising at least one distance between the objects on the display map based on the at least one associated relationship and the at least one distance;

(6) repeating steps (4) and (5) for additional sub-sets of objects from the set of objects;

(7) allowing distances between the objects for which the associated pair-wise relationships have been removed to adapt during performance of steps (4) through (6); and

(8) generating mapping coordinates for the set of objects.

41. The method according to claim 40, wherein step (4) comprises the step of:

selecting a pair of objects having an associated pair-wise relationship.

42. The method according to claim 40, wherein the associated pair-wise relationships between one or more pairs of objects are unknown, the method further comprising the steps of:

performing steps (4) through (6) only for pairs of objects for which an associated pair-wise relationship is known; and

allowing distances between objects on the display map for which associated pair-wise relationships are not known to adapt during performance of steps (4) through (6).

43. The method according to claim 40, wherein step (5) comprises the step of:

revising the at least one distance based on a learning rate.

44. The method according to claim 40, wherein step (5) comprises the step of:

revising the at least one distance based on a fixed learning rate.

45. The method according to claim 40, wherein step (5) comprises the step of:

revising the at least one distance based on a variable learning rate.

46. The method according to claim 40, wherein step (5) comprises the step of:

revising the at least one distance based on a learning rate that is a function of the associated pair-wise relationship between the pair of objects.

47. The method according to claim 40, wherein step (5) comprises the step of:

revising the at least one distance based on a learning rate that is a function of at least one object of the pair of objects.

48. The method according to claim 40, wherein step (5) comprises the step of:

revising the at least one distance based on a learning rate that is a function of the selected pair of objects.

49. The method according to claim 40, wherein step (5) comprises the step of:

revising the at least one distance using a conventional multi-dimensional scaling technique.

50. The method according to claim 40, wherein step (5) comprises the step of:

revising the at least one distance using a conventional non-linear mapping technique.

51. The method according to claim 40, wherein step (5) comprises the steps of:

computing an error function value using a conventional technique; and

revising the at least one distance using a gradient descent procedure.

52. The method according to claim 40, wherein that the objects do not represent chemical objects.