Incremental clustering classifier and predictor

• US 7,213,023 B2
• Filed: 05/14/2001
• Issued: 05/01/2007
• Est. Priority Date: 10/16/2000
• Status: Expired due to Fees

• Current Assignee: University of North Carolina At Charlotte (University of North Carolina System)
• Original Assignee: University of North Carolina At Charlotte (University of North Carolina System)
• Inventors: Hadzikadic, Mirsad, Eichelberger, Christopher N., Bohren, Benjamin F.
• Primary Examiner(s): ROBINSON, GRETA LEE
• Application Number:
  US09/855,220
• Publication Number:
  US 20020059202A1
• Time in Patent Office: 2,178 Days
• Field of Search: 707/100, 707/103.R, 707/103.X, 707/103.Y, 707/103.Z, 707/104.1
• US Class Current: 1/1
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

The present invention provides mathematical model-based incremental clustering methods for classifying sets of data and predicting new data values, based upon the concepts of similarity and cohesion. In order to increase processing efficiency, these methods employ weighted attribute relevance in building unbiased classification trees and sum pairing to reduce the number of nodes visited when performing classification or prediction operations. In order to increase prediction accuracy, these methods employ weighted voting over each value of target attributes to calculate a prediction profile. The present invention also allows an operator to determine the importance of attributes and reconstitute classification trees without those attributes deemed unimportant to further increase classification structure node processing efficiency.

Claims

1. A computer-implemented method of classifying an instance comprising the steps of:

receiving an instance to be classified, the instance to be classified comprising at least one attribute and corresponding relevance value;

determining a best host for the instance to be classified;

inserting the instance to be classified into a location relative to at least one child of the best host within a classification structure, the classification structure comprising at least one node, and the node comprising at least one attribute and corresponding relevance value; and

displaying the classification structure;

determining at least one distinguishing feature of the instance to be classified; and

visually contrasting the instance to be classified vice nodes within the classification structure, based upon the value of the at least one distinguishing feature.

2. The method of claim 1, wherein determining the best host for the instance to be classified comprises:

processing class concept nodes of the classification structure, comprising the steps of;

receiving a class concept node of the classification structure;

calculating a delta cohesiveness measurement (Δ

CM) value between the instance to be classified and the class concept node; and

storing the largest Δ

CM value and the corresponding class concept node at each level of the classification structure;

determining the largest Δ

CM value over all levels of the classification structure; and

storing the class concept node corresponding to the largest Δ

CM value over all levels of the classification structure.

3. The method of claim 2, wherein determining the best host for the instance to be classified is performed recursively.

4. The method of claim 3, wherein inserting the instance to be classified into a location relative to at least one child of the best host within a classification structure comprises:

selecting at least one best host child node;

calculating a Δ

CM value between the instance to be classified and the at least one best host child;

storing the Δ

CM value associated with each at least one best host child;

storing a count of the total number of the at least one best host child;

storing a count of the total number of stored Δ

CM values associated with each at least one best host child that are greater than 0.0; and

adding the instance to be classified to the classification structure as a sibling or child of the at least one best host child, based upon the Δ

CM value associated with each at least one best host child, the count of the total number of the at least one best host child, and the count of the total number of stored Δ

CM values associated with each at least one best host child that are greater than 0.0.

5. The method of claim 1, wherein the at least one distinguishing feature comprises at least one of an attribute value, a context value and a relationship value.