Probabilistic data clustering

• US 6,460,035 B1
• Filed: 01/08/1999
• Issued: 10/01/2002
• Est. Priority Date: 01/10/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Siegwart, David Kevin
• Primary Examiner(s): Alam, Hosain T.
• Assistant Examiner(s): Ly, Anh
• Application Number:
  US09/227,253
• Time in Patent Office: 1,362 Days
• Field of Search: 707/1, 707/5, 707/6, 707/7, 707/10, 707/102, 707/104, 709/241, 340/995, 434/362, 704/236, 704/256, 702/181, 706/12
• US Class Current: 707/737
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06F 18/2321 using statistics or function optimisation, e.g. modelling of probability density functions
• CPC Class Codes: G06F 18/2433 Single-class perspective, e.g. one-against-all classification; Novelty detection; Outlier detection
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A component of a data clusterer is used to determine a conditional probability density of an object (data point) lying in a cluster. The object has a discrete ordinal attribute value within a finite range of attribute values. The conditional probability density for the discrete ordinal attribute is a function of an integral of a conditional probability function across a sub-range of the discrete ordinal attribute range of values, the sub-range comprising an upper bound and a lower bound bounding the discrete ordinal attribute value.

Claims

1. A data mining system adapted to generate a cluster model from a data set comprising a plurality of objects, each object including a plurality of attributes, said attributes including a set of discrete ordinal attributes, said system including an iterative cluster definition means, the or each cluster having a distribution attribute associated with each of said set of discrete ordinal attributes, said cluster definition means including:

means for determining, for each cluster, a conditional probability density (p_j(x,z,q)) of an object lying in a cluster;

means for determining, for each cluster and for each object, a posterior probability (h_ij) of an object lying in a cluster, said posterior probability being a function of said conditional probability density of the cluster (p_j(x,z,q)), a mixing fraction for said cluster (α

_j) and an unconditional probability density (p(x,z,q)); and

means for determining, for each object attribute and for each cluster, a next cluster distribution attribute (μ

_jk,V_jk;

ν

_jk,W_jk;

π

_jk,c_jk), said distribution attribute being a function of said posterior probability, said object attribute value and a sum of said posterior probabilities;

wherein said means for determining the conditional probability density of an object lying in a cluster is characterised by means for determining the conditional probability density of an object having a discrete ordinal attribute value within a finite range of attribute values lying in a cluster, said conditional probability density for said discrete ordinal attribute being a function of an integral of a conditional probability function across a sub-range of said discrete ordinal attribute range of values, said sub-range comprising an upper bound and a lower bound bounding said discrete ordinal attribute value.

2. A data mining system as claimed in claim 1 wherein said object attributes further comprise a set of continuous attributes and a set of categorical attributes, and the or each cluster has a distribution attribute associated with each of said set of continuous attributes and a distribution attribute associated with each of said set of categorical attributes, said conditional probability density further comprising a continuous component and a categorical component.

3. A data mining system as claimed in claim 2 said cluster distribution attributes for said continuous attributes comprise respective Gaussian distributions having respective means and variances.

4. A data mining system as claimed in claim 1 wherein said cluster distribution attributes for said discrete ordinal attributes comprise respective Gaussian distributions having respective means and variances.

5. A data mining system as claimed in claim 2 wherein said cluster distribution attributes for said categorical attributes comprise respective distributions having respective modal values and conditional probabilities of said categorical object attribute not being said modal value for said attribute.

6. A data mining system as claimed in claim 1 wherein said sum of said posterior probabilities and said posterior probability are functions of observed object attribute values.