Methods for filtering data and filling in missing data using nonlinear inference

• US 20070214133A1
• Filed: 03/07/2007
• Published: 09/13/2007
• Est. Priority Date: 06/23/2004
• Status: Abandoned Application

• Current Assignee: Edo Liberty, Frank Geshwind, Mauro Maggioni, Ronald Coifman, Steven Zucker, Yosi Keller
• Original Assignee: Edo Liberty, Frank Geshwind, Mauro Maggioni, Ronald Coifman, Steven Zucker, Yosi Keller
• Inventors: Geshwind, Frank, Zucker, Steven, Liberty, Edo, Coifman, Ronald, Keller, Yosi, Maggioni, Mauro
• Application Number:
  US11/715,863
• Publication Number:
  US 20070214133A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9538 Presentation of query results

Abstract

The present invention is directed to a method for inferring/estimating missing values in a data matrix d(q, r) having a plurality of rows and columns comprises the steps of: organizing the columns of the data matrix d(q, r) into affinity folders of columns with similar data profile, organizing the rows of the data matrix d(q, r) into affinity folders of rows with similar data profile, forming a graph Q of augmented rows and a graph R of augmented columns by similarity or correlation of common entries; and expanding the data matrix d(q, r) in terms of an orthogonal basis of a graph Q×R to infer/estimate the missing values in said data matrix d(q, r) on the diffusion geometry coordinates.

Claims

1. A method for inferring/estimating missing values in a data matrix d(q, r) having a plurality of rows and columns, comprising the steps of:

organizing said columns of said data matrix d(q, r) into affinity folders of columns with similar data profile;

organizing said rows of said data matrix d(q, r) into affinity folders of rows with similar data profile;

forming a graph Q of augmented rows and a graph R of augmented columns by similarity or correlation of common entries; and

expanding said data matrix d(q, r) in terms of an orthogonal basis of a graph Q×

R to infer/estimate said missing values in said data matrix d(q, r).

2. The method of claim 1, wherein said data matrix d(q, r) comprises questionnaire data;

and further comprising the step of filling in an unknown response to a questionnaire, to infer/estimate missing values in said data matrix d(q, r).

3. The method of claim 1, wherein the step of expanding comprises the step of expanding said data matrix d(q, r) in terms of a tensor product of wavelet bases for graphs Q and R.

4. The method of claim 3, wherein the step of expanding comprises the steps of, for each tensor wavelet in basis, computing a wavelet coefficient by averaging on the support of said tensor wavelet and retaining said coefficient in the expansion only if validated by a randomized average.

5. The method of claim 1, wherein at least one of the steps of organizing comprises the steps of constructing diffusion wavelets and taking supports of the resulting diffusion wavelets at a fixed scale on said columns of said graph R.

6. The method of claim 1, wherein said data matrix d(q, r) comprises initial customer preference data;

and further comprising the step of predicting additional customer preferences from said data matrix d(q, r).

7. The method of claim 1, wherein said data matrix d(q, r) comprises measured values of an empirical function f(q, r);

and further comprising the step of nonlinear regression modeling of said empirical function f(q, r).

8. The method of claim 1, wherein said data matrix d(q, r) is a questionnaire d(q, r);

and further comprising the steps of determining whether a response (q₀, r₀) to said questionnaire d(q, r) is an anomalous response.

9. The method of claim 8, wherein the step of determining further comprises the steps of:

generating a dataset d1(q, r) comprising responses to said questionnaire d(q, r);

omitting said response (q₀, r₀) from said dataset d1(q, r);

reconstructing said missing response (q₀, r₀) from said dataset d1(q, r) to provide a reconstructed value;

comparing said reconstructed value to said response (q₀, r₀); and

determining said response (q₀, r₀) to be anomalous when a distance between said reconstructed value and said response (q₀, r₀) is larger than a pre-determined threshold.

10. The method of claim 9, wherein said data matrix d(q, r) comprises data relevant to fraud or deception;

and further comprising the step of detecting fraud or deception from said data matrix d(q, r).

11. A computer readable medium comprising code for inferring/estimating missing values in a data matrix d(q, r) having a plurality of rows and columns, said code comprising instructions for:

organizing said columns of said data matrix d(q, r) into affinity folders of columns with similar data profile;

organizing said rows of said data matrix d(q, r) into affinity folders of rows with similar data profile;

forming a graph Q of augmented rows and a graph R of augmented columns by similarity or correlation of common entries; and

expanding said data matrix d(q, r) in terms of an orthogonal basis of a graph Q×

R to infer/estimate said missing values in said data matrix d(q, r).

12. The computer readable medium of claim 11, wherein said data matrix d(q, r) comprises questionnaire data;

and wherein said code further comprises instructions for filling in an unknown response to a questionnaire, to infer/estimate missing values in said data matrix d(q, r).

13. The computer readable medium of claim 11, wherein said code further comprises instructions for expanding said data matrix d(q, r) in terms of a tensor product of wavelet bases for graphs Q and R.

14. The computer readable medium of claim 13, wherein, for each tensor wavelet in basis, said code further comprises instructions for computing a wavelet coefficient by averaging on the support of said tensor wavelet and retaining said coefficient in the expansion only if validated by a randomized average.

15. The computer readable medium of claim 11, wherein said code for organizing either said rows or said column further comprises instructions for constructing diffusion wavelets and taking supports of the resulting diffusion wavelets at a fixed scale on said columns of said graph R.

16. The computer readable medium of claim 11, wherein said data matrix d(q, r) comprises initial customer preference data;

and wherein said code further comprises instructions for predicting additional customer preferences from said data matrix d(q, r).

17. The computer readable medium of claim 11, wherein said data matrix d(q, r) comprises measured values of an empirical function f(q, r);

and wherein said code further comprises instructions for nonlinear regression modeling of said empirical function f(q, r).

18. The computer readable medium of claim 11, wherein said data matrix d(q, r) is a questionnaire d(q, r);

and wherein said code further comprises instructions for determining whether a response (q₀, r₀) to said questionnaire d(q, r) is an anomalous response.

19. The computer readable medium of claim 18, wherein said code further comprises instructions for:

generating a dataset d1(q, r) comprising responses to said questionnaire d(q, r);

omitting said response (q₀, r₀) from said dataset d1(q, r);

reconstructing said missing response (q₀, r₀) from said dataset d1(q, r) to provide a reconstructed value;

comparing said reconstructed value to said response (q₀, r₀); and

determining said response (q₀, r₀) to be anomalous when a distance between said reconstructed value and said response (q₀, r₀) is larger than a pre-determined threshold.

20. The computer readable medium of claim 19, wherein said data matrix d(q, r) comprises data relevant to fraud or deception;

and wherein said code further comprises instructions for detecting fraud or deception from said data matrix d(q, r).