High dimensional to low dimensional data transformation and visualization system

Patent metadata

Field	Value
Publication number	US-10984075-B1
Application number	US-202017069293-A
Country	US
Kind code	B1
Filing date	Oct 13, 2020
Priority date	Jul 1, 2020
Publication date	Apr 20, 2021
Grant date	Apr 20, 2021

Abstract

A computer transforms high-dimensional data into low-dimensional data. A distance is computed between a selected observation vector and each observation vector of a plurality of observation vectors, a nearest neighbors are selected using the computed distances, and a first sigmoid function is applied to compute a distance similarity value between the selected observation vector and each of the selected nearest neighbors where each of the computed distance similarity values is added to a first matrix. The process is repeated with each observation vector of the plurality of observation vectors as the selected observation vector. An optimization method is executed with an initial matrix, the first matrix, and a gradient of a second sigmoid function that computes a second distance similarity value between the selected observation vector and each of the nearest neighbors to transform each observation vector of the plurality of observation vectors into the low-dimensional space.

First claim

What is claimed is:

1. A non-transitory computer-readable medium having stored thereon computer-readable instructions that when executed by a computing device cause the computing device to:
(A) select an observation vector from a plurality of observation vectors, wherein each observation vector of the plurality of observation vectors includes a value for each variable of a plurality of variables, wherein the plurality of variables define a high-dimensional space;
(B) compute a distance between the selected observation vector and each observation vector of the plurality of observation vectors;
(C) select a plurality of nearest neighbors to the selected observation vector using the computed distances, wherein a number of the plurality of nearest neighbors is a predefined number, wherein each nearest neighbor of the plurality of nearest neighbors is one of the plurality of observation vectors that are closest to the selected observation vector;
(D) apply a first sigmoid function to compute a distance similarity value between the selected observation vector and each of the selected plurality of nearest neighbors based on the value of each variable of the plurality of variables of the selected observation vector and on the value of each variable of the plurality of variables of each of the plurality of nearest neighbors;
repeat (A) through (D) with each observation vector of the plurality of observation vectors selected as the observation vector in (A), wherein each of the computed distance similarity values computed in (D) are added to a first matrix;
compute an initial matrix from the plurality of observation vectors, wherein the initial matrix represents a transformation of each observation vector of the plurality of observation vectors into a low-dimensional space defined to include a predefined number of dimensions, wherein the predefined number of dimensions is less than a number of the plurality of variables;
execute an optimization method with the computed initial matrix, the first matrix, and a gradient of a second sigmoid function that computes a second distance similarity value between the selected observation vector and each of the plurality of nearest neighbors in the low-dimensional space, wherein the optimization method determines an optimized matrix that represents a transformation of each observation vector of the plurality of observation vectors into the low-dimensional space; and
output the optimized matrix.

2. The non-transitory computer-readable medium of claim 1 , wherein the computer-readable instructions further cause the computing device to present a visualization of the optimized matrix in a display.

3. The non-transitory computer-readable medium of claim 1 , wherein the computer-readable instructions further cause the computing device to train a clustering model with the optimized matrix to define a plurality of clusters in the low-dimensional space, wherein each observation vector of the plurality of observation vectors is assigned to a single cluster, and to present a visualization of the defined plurality of clusters in a display.

4. The non-transitory computer-readable medium of claim 1 , wherein the predefined number of dimensions is two or three.

5. The non-transitory computer-readable medium of claim 1 , wherein the first sigmoid function is

δ
j

=

1

1
+

max
⁡

(

0
,

dis
j

-
ρ

)

σ

,

j
=
1

,
…
⁢

,
k
,

where δ j is the distance similarity value between a j th nearest neighbor and the selected observation vector, dis j is the distance computed between the j th nearest neighbor and the selected observation vector, σ is a normalizing factor value, ρ is a distance to a closest nearest neighbor of the plurality of nearest neighbors, and k is the number of the plurality of nearest neighbors.

6. The non-transitory computer-readable medium of claim 5 , wherein the distance between the j th nearest neighbor and the selected observation vector is computed using a Euclidean distance function.

7. The non-transitory computer-readable medium of claim 5 , wherein a binary search is used to compute a value for a for the selected observation vector.

8. The non-transitory computer-readable medium of claim 7 , wherein the binary search is based on solving

∑

j
=
1

k

⁢

1

1
+

max
⁡

(

0
,

dis
j

-
ρ

)

σ

=

log
2

⁢

⁢

k
.

9. The non-transitory computer-readable medium of claim 5 , wherein the first matrix is computed using P ij =P j|i +P i|j −P i|j ⊙P j|i , where P j|i =δ j when x j is one of the plurality of nearest neighbors of the selected observation vector indicated as x i , and is zero otherwise, P i|j =δ i when x i is one of the plurality of nearest neighbors of x j , and is zero otherwise, and ⊙ indicates a component wise multiplication.

10. The non-transitory computer-readable medium of claim 1 , wherein the second sigmoid function is

Q
⁡

(

i
,
j

Assignees

• Sas Inst Inc

Inventors

• Liang Yu
• Chaudhuri Arin
• Wang Haoyu

Classifications

• G06F16/55 Primary

  Clustering; Classification · CPC title

• G06V10/76

  based on eigen-space representations, e.g. from pose or different illumination conditions; Shape manifolds · CPC title

• G06V10/7715

  Feature extraction, e.g. by transforming the feature space, e.g. multi-dimensional scaling [MDS]; Mappings, e.g. subspace methods · CPC title

• G06V10/764

  using classification, e.g. of video objects · CPC title

• G06F17/16 Primary

  Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} · CPC title