# US 2012/0059777 A1 · Characterizing datasets using sampling, weighting, and approximation of an eigendecomposition

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0059777 A1
- Document ID: US20120059777A1
- Status: Published application
- Kind: A1
- Application number: 12/875,330
- Filed: 2010-09-03
- Published: 2012-03-08
- Earliest claimed: 2010-09-03
- Assignees: University of Utah Research Foundation
- Inventors: Antonio Rafael da Costa Paiva; Tolga Tasdizen
- Web page: https://patentgrep.com/patent/US20120059777A1

## CPC

- G06N 20/00: Machine learning
- G06F 18/21355: {nonlinear criteria, e.g. embedding a manifold in a Euclidean space}
- G06N 20/10: using kernel methods, e.g. support vector machines [SVM]
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method, a system, and a computer-readable medium are provided for characterizing a dataset. A representative dataset is defined from a dataset by a computing device. The representative dataset includes a first plurality of data points and the dataset includes a second plurality of data points. The number of the first plurality of data points is less than the number of the second plurality of data points. The data point is added to the representative dataset if a minimum distance between the data point and each data point of the representative dataset is greater than a sampling parameter. The data point is added to a refinement dataset if the minimum distance between the data point and each data point of the representative dataset is less than the sampling parameter and greater than half the sampling parameter. A weighting matrix is defined by the computing device that includes a weight value calculated for each of the first plurality of data points based on a determined number of the second plurality of data points associated with a respective data point of the first plurality of data points. The weight value for a closest data point of the representative dataset is updated if the minimum distance between the data point and each data point of the representative dataset is less than half the sampling parameter. A machine learning algorithm is executed by the computing device using the defined representative dataset and the defined weighting matrix applied in an approximation for a computation of a full kernel matrix of the dataset to generate a parameter characterizing the dataset.

## Claims

### Claim 1

A system comprising:
a processor; and
a computer-readable medium operably coupled to the processor, the computer-readable medium having computer-readable instructions stored thereon that, when executed by the processor, cause the system to
define a representative dataset from a dataset by adding a data point of the dataset to the representative dataset if a minimum distance between the data point and each data point of the representative dataset is greater than a sampling parameter and adding the data point of the dataset to a refinement dataset if the minimum distance between the data point and each data point of the representative dataset is less than the sampling parameter and greater than half the sampling parameter, wherein the representative dataset includes a first plurality of data points and the dataset includes a second plurality of data points, and the number of the first plurality of data points is less than the number of the second plurality of data points;
define a weighting matrix, wherein the weighting matrix includes a weight value calculated for each of the first plurality of data points based on a determined number of the second plurality of data points associated with a respective data point of the first plurality of data points, and further wherein the weight value for a closest data point of the representative dataset is updated if the minimum distance between the data point and each data point of the representative dataset is less than half the sampling parameter; and
execute a machine learning algorithm using the defined representative dataset and the defined weighting matrix applied in an approximation for computation of a full kernel matrix of the dataset to generate a parameter characterizing the dataset.

### Claim 2 (depends on 1)

The system of claim 1, wherein the sampling parameter is defined based on a kernel size.

### Claim 3 (depends on 2)

The system of claim 2, wherein the sampling parameter is defined in a range of [σ/2,σ] where σ is the kernel size.

### Claim 4 (depends on 1)

The system of claim 1, wherein defining the representative dataset further comprises, after processing each of the second plurality of data points to define the refinement dataset,
calculating a second minimum distance between a data point of the refinement dataset and each data point of the representative dataset; and
updating the weight value for the closest data point of the representative dataset determined based on the calculated second minimum distance.

### Claim 5 (depends on 1)

The system of claim 1, wherein the machine learning algorithm performs kernel principle component analysis and the approximation for the M largest eigenvalues and corresponding eigenvectors of the eigendecomposition of the full kernel matrix of the dataset is defined by a diagonal matrix of eigenvalues Ũ and a matrix of corresponding eigenvectors EW−1/2{tilde over (V)}, where Ũ is a diagonal matrix of eigenvalues and {tilde over (V)} is a matrix of corresponding eigenvectors for the eigendecomposition of W1/2{tilde over (K)}RW1/2, E is an N×M matrix with the (i,m) entry equal to one if the i-th data point of the dataset has been assigned to the m-th data point of the representative dataset, and zero otherwise, W is the weighting matrix,
K
~
R
=
(
I
M
-
1
N

1
M
×
M

W
)

K
R

(
I
M
-
1
N

W


1
M
×
M
)
,
M is the number of the first plurality of data points, N is the number of the second plurality of data points, IM is an identity matrix, 1M×M is the M×M matrix of all ones, and KR is the kernel matrix of the representative dataset.

### Claim 6 (depends on 1)

The system of claim 1, wherein the machine learning algorithm performs spectral clustering and the approximation for the M largest eigenvalues and corresponding eigenvectors of the eigendecomposition of the full kernel matrix of the dataset is defined by a diagonal matrix of eigenvalues {hacek over (U)} and a matrix of corresponding eigenvectors EW−1/2{hacek over (V)}, where {hacek over (U)} is a diagonal matrix of eigenvalues and {hacek over (V)} is a matrix of corresponding eigenvectors for the eigendecomposition of W1/2DR−1/2KRDR−1/2W1/2, E is an N×M matrix with the (i,m) entry equal to one if the i-th data point of the dataset has been assigned to the m-th data point of the representative dataset, and zero otherwise, W is the weighting matrix, M is the number of the first plurality of data points, N is the number of the second plurality of data points, DR is an M×M diagonal matrix with the i-th diagonal entry given by, where wj is the weight associated with the j-th element of the representative dataset, κ is a kernel function, and KR is the kernel matrix of the representative dataset.

### Claim 7

A computer-readable medium having stored thereon computer-readable instructions that when executed by a computing device cause the computing device to:
define a representative dataset from a dataset by adding a data point of the dataset to the representative dataset if a minimum distance between the data point and each data point of the representative dataset is greater than a sampling parameter and adding the data point of the dataset to a refinement dataset if the minimum distance between the data point and each data point of the representative dataset is less than the sampling parameter and greater than half the sampling parameter, wherein the representative dataset includes a first plurality of data points and the dataset includes a second plurality of data points, and the number of the first plurality of data points is less than the number of the second plurality of data points;
define a weighting matrix, wherein the weighting matrix includes a weight value calculated for each of the first plurality of data points based on a determined number of the second plurality of data points associated with a respective data point of the first plurality of data points, and further wherein the weight value for a closest data point of the representative dataset is updated if the minimum distance between the data point and each data point of the representative dataset is less than half the sampling parameter; and
execute a machine learning algorithm using the defined representative dataset and the defined weighting matrix applied in an approximation for a computation of a full kernel matrix of the dataset to generate a parameter characterizing the dataset.

### Claim 8 (depends on 7)

The computer-readable medium of claim 7, wherein the sampling parameter is defined based on a kernel size.

### Claim 9 (depends on 8)

The computer-readable medium of claim 8, wherein the sampling parameter is defined in a range of [σ/2,σ] where σ is the kernel size.

### Claim 10 (depends on 7)

The computer-readable medium of claim 7, wherein defining the representative dataset further comprises, after processing each of the second plurality of data points to define the refinement dataset,
calculating a second minimum distance between a data point of the refinement dataset and each data point of the representative dataset; and
updating the weight value for the closest data point of the representative dataset determined based on the calculated second minimum distance.

### Claim 11 (depends on 7)

The computer-readable medium of claim 7, wherein the machine learning algorithm performs kernel principle component analysis and the approximation for the M largest eigenvalues and corresponding eigenvectors of the eigendecomposition of the full kernel matrix of the dataset is defined by a diagonal matrix of eigenvalues Ũ and a matrix of corresponding eigenvectors EW−1/2{tilde over (V)}, where Ũ is a diagonal matrix of eigenvalues and {tilde over (V)} is a matrix of corresponding eigenvectors for the eigendecomposition of W1/2{tilde over (K)}RW1/2, E is an N×M matrix with the (i,m) entry equal to one if the i-th data point of the dataset has been assigned to the m-th data point of the representative dataset, and zero otherwise, W is the weighting matrix,
K
~
R
=
(
I
M
-
1
N

1
M
×
M

W
)

K
R

(
I
M
-
1
N

W


1
M
×
M
)
,
M is the number of the first plurality of data points, N is the number of the second plurality of data points, IM is an identity matrix, 1M×M is the M×M matrix of all ones, and KR is the kernel matrix of the representative dataset.

### Claim 12 (depends on 7)

The computer-readable medium of claim 7, wherein the machine learning algorithm performs spectral clustering and the approximation for the M largest eigenvalues and corresponding eigenvectors of the eigendecomposition of the full kernel matrix of the dataset is defined by a diagonal matrix of eigenvalues {hacek over (U)} and a matrix of corresponding eigenvectors EW−1/2{hacek over (V)}, where {hacek over (U)} is a diagonal matrix of eigenvalues and {hacek over (V)} is a matrix of corresponding eigenvectors for the eigendecomposition of Wl/2DR−1/2KRDR−1/2W1/2, E is an N×M matrix with the (i,m) entry equal to one if the i-th data point of the dataset has been assigned to the m-th data point of the representative dataset, and zero otherwise, W is the weighting matrix, M is the number of the first plurality of data points, N is the number of the second plurality of data points, DR is an M×M diagonal matrix with the i-th diagonal entry given by, where wj is the weight associated with the j-th element of the representative dataset, κ is a kernel function, and KR is the kernel matrix of the representative dataset.

### Claim 13

A method of characterizing a dataset, the method comprising:
defining, by a computing device, a representative dataset from a dataset by adding a data point of the dataset to the representative dataset if a minimum distance between the data point and each data point of the representative dataset is greater than a sampling parameter and adding the data point of the dataset to a refinement dataset if the minimum distance between the data point and each data point of the representative dataset is less than the sampling parameter and greater than half the sampling parameter, wherein the representative dataset includes a first plurality of data points and the dataset includes a second plurality of data points, and the number of the first plurality of data points is less than the number of the second plurality of data points;
defining, by the computing device, a weighting matrix, wherein the weighting matrix includes a weight value calculated for each of the first plurality of data points based on a determined number of the second plurality of data points associated with a respective data point of the first plurality of data points, and further wherein the weight value for a closest data point of the representative dataset is updated if the minimum distance between the data point and each data point of the representative dataset is less than half the sampling parameter; and
executing, by the computing device, a machine learning algorithm using the defined representative dataset and the defined weighting matrix applied in a approximation for a computation of a full kernel matrix of the dataset to generate a parameter characterizing the dataset.

### Claim 14 (depends on 13)

The method of claim 13, wherein the sampling parameter is defined based on a kernel size.

### Claim 15 (depends on 14)

The method of claim 14, wherein the sampling parameter is defined in a range of [σ/2,σ] where σ is the kernel size.

### Claim 16 (depends on 13)

The method of claim 13, wherein defining the representative dataset further comprises, after processing each of the second plurality of data points to define the refinement dataset,
calculating a second minimum distance between a data point of the refinement dataset and each data point of the representative dataset; and
updating the weight value for the closest data point of the representative dataset determined based on the calculated second minimum distance.

### Claim 17 (depends on 13)

The method of claim 13, wherein the machine learning algorithm performs kernel principle component analysis and the approximation for the M largest eigenvalues and corresponding eigenvectors of the eigendecomposition of the full kernel matrix of the dataset is defined by a diagonal matrix of eigenvalues Ũ and a matrix of corresponding eigenvectors EW−1/2{tilde over (V)}, where Ũ is a diagonal matrix of eigenvalues and {tilde over (V)} is a matrix of corresponding eigenvectors for the eigendecomposition of W1/2{tilde over (K)}RW1/2, E is an N×M matrix with the (i,m) entry equal to one if the i-th data point of the dataset has been assigned to the m-th data point of the representative dataset, and zero otherwise, W is the weighting matrix,
K
~
R
=
(
I
M
-
1
N

1
M
×
M

W
)

K
R

(
I
M
-
1
N

W


1
M
×
M
)
,
M is the number of the first plurality of data points, N is the number of the second plurality of data points, IM is an identity matrix, 1M×M is the M×M matrix of all ones, and KR is the kernel matrix of the representative dataset.

### Claim 18 (depends on 13)

The method of claim 13, wherein the machine learning algorithm performs spectral clustering and the approximation for the M largest eigenvalues and corresponding eigenvectors of the eigendecomposition of the full kernel matrix of the dataset is defined by a diagonal matrix of eigenvalues {hacek over (U)} and a matrix of corresponding eigenvectors EW−1/2{hacek over (V)}, where {hacek over (U)} is a diagonal matrix of eigenvalues and {hacek over (V)} is a matrix of corresponding eigenvectors for the eigendecomposition of W1/2DR1/2KRDR−1/2W1/2, E is an N×M matrix with the (i,m) entry equal to one if the i-th data point of the dataset has been assigned to the m-th data point of the representative dataset, and zero otherwise, W is the weighting matrix, M is the number of the first plurality of data points, N is the number of the second plurality of data points, DR is an M×M diagonal matrix with the i-th diagonal entry given by, where wj is the weight associated with the j-th element of the representative dataset, κ is a kernel function, and KR is the kernel matrix of the representative dataset.
