HIERARCHICAL SEQUENTIAL CLUSTERING

• US 20110078144A1
• Filed: 07/07/2010
• Published: 03/31/2011
• Est. Priority Date: 09/28/2009
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Helfman, Jonathan, Goldberg, Joseph H.
• Granted Patent: US 10,552,710 B2
• Time in Patent Office: Days
• US Class Current: 707/737
• CPC Class Codes: G06F 18/231 Hierarchical techniques, i.e. dividing or merging pattern sets so as to obtain a dendrogram

Abstract

Embodiments of the invention provide systems and methods for analyzing sequential data. Analyzing the sequential data can include grouping or clustering data that are similar in some way, e.g., similar ranges of quantities, similar categories, etc. More specifically, a method for hierarchical clustering of sequential data can comprise creating a dotplot of the sequential data. The dotplot can represent a plurality of sequences within the sequential data. A number of clusters represented by the plurality of sequences can be initialized, e.g., one cluster per sequence. A pair of sequences of the plurality of sequences having a longest sequential match can be identified, e.g., based on a line fitting technique, and merged into a single cluster. Identifying a pair of sequences of the plurality of sequences having a longest sequential match and merging the identified pair of sequences into a single cluster can be repeated until a single cluster remains.

Claims

1. A method for hierarchically clustering sequential data that preserves the sequential information in the data, the method comprising:

identifying pair-wise sequential matches between the plurality of sequences within the sequential data;

initializing a number of clusters represented by the plurality of sequences;

identifying a pair of sequences of the plurality of sequences that are closest to each other according to a distance measure; and

merging the identified pair of sequences into a single cluster.

2. The method of claim 1, further comprising assigning an aggregate sequence to the single cluster, the aggregate sequence representing the sequences merged into the single cluster.

3. The method of claim 1, wherein the pair-wise sequential matches are identified using a dotplot.

4. The method of claim 1, wherein the distance measure is a measure of the length of the longest sequential match as determined by the total count of sequentially-matching tokens.

5. The method of claim 1, wherein the distance measure is a measure of the sum of the weights of the sequentially-matching tokens.

6. The method of claim 1, wherein initializing the number of clusters comprises initializing the number of clusters to one cluster per sequence in the sequential data.

7. The method of claim 1, wherein identifying the closest pair of sequences of the plurality of sequences is based on a technique to determine if points are collinear.

8. The method of claim 7, wherein the line fitting technique comprises a regression technique.

9. The method of claim 1, further comprising repeating identifying a pair of closest sequences of the plurality of sequences and merging the identified pair of sequences into a single cluster until a single cluster remains.

10. The method of claim 9, wherein merging the identified pair of sequences into a single cluster comprises:

assigning a unique identifier to the single cluster;

copying a closest distance and reference to a pair-wise sequential match to the single cluster; and

associating a sequence to the single cluster.

11. The method of claim 10, wherein the associated sequence is the sequence associated with the child cluster that sequentially matches the most other sequences in the dataset.

12. The method of claim 1, wherein the sequential data comprises eye tracking data.

13. The method of claim 12, wherein the sequential data further comprises scanpaths including fixation points.

14. A system comprising:

a processor; and

a memory communicatively coupled with and readable by the processor and having stored therein a series of instructions which, when executed by the processor, cause the processor to hierarchically cluster sequential data by identifying pair-wise sequential matches between the plurality of sequences within the sequential data, initializing a number of clusters represented by the plurality of sequences, identifying a pair of sequences of the plurality of sequences that are closest to each other according to a distance measure, merging the identified pair of sequences into a single cluster, assigning an aggregate sequence to the single cluster, the aggregate sequence representing the sequences merged into the single cluster, and repeating identifying a pair of closest sequences of the plurality of sequences, merging the identified pair of sequences into a single cluster, and assigning an aggregate sequence to the cluster until a single cluster remains.

15. The system of claim 14, wherein merging the identified pair of sequences into a single cluster comprises:

assigning a unique identifier to the single cluster;

copying a closest distance and reference to a pair-wise sequential match to the single cluster; and

associating a sequence to the single cluster.

16. A machine-readable medium having stored therein a series of instructions which, when executed by a processor, cause the processor to hierarchically cluster sequential data by:

identifying pair-wise sequential matches between the plurality of sequences within the sequential data;

initializing a number of clusters represented by the plurality of sequences;

identifying a pair of sequences of the plurality of sequences that are closest to each other according to a distance measure; and

merging the identified pair of sequences into a single cluster;

assigning an aggregate sequence to the single cluster, the aggregate sequence representing the sequences merged into the single cluster; and

repeating identifying a pair of closest sequences of the plurality of sequences, merging the identified pair of sequences into a single cluster, and assigning an aggregate sequence to the cluster until a single cluster remains.

17. The machine-readable medium of claim 16, wherein initializing the number of clusters comprises initializing the number of clusters to one cluster per sequence in the sequential data.

18. The machine-readable medium of claim 16, wherein identifying the closest pair of sequences of the plurality of sequences is based on a technique to determine if points are collinear.

19. The machine-readable medium of claim 16, wherein merging the identified pair of sequences into a single cluster comprises:

assigning a unique identifier to the single cluster;

copying a closest distance and reference to a pair-wise sequential match to the single cluster; and

associating a sequence to the single cluster.

20. The machine-readable medium of claim 19, wherein the associated sequence is the sequence associated with the child cluster that sequentially matches the most other sequences in the dataset.