Fast clustering with sparse data

Claim 2

A computer-implemented method that facilitates fast clustering of a data set defined for a plurality of attributes, comprising: inputting the data set, the data set having a plurality of records each having a value for each attribute, wherein the value for each attribute is selected from a plurality of possible values, one value from the plurality of possible values is designated a default value for the attribute; storing a sparse representation of each record, including storing the value of the attribute of the record only upon determining that the attribute of the record has a value varying from the default value; clustering each record using the sparse representation of the record; generating a data model of the data set, utilizing the sparse representation of each record; and, outputting the data model.

Claim 3

The method of claim 1 , wherein at least one record has a plurality of attributes, each attribute having a default value.

Claim 4

The method of claim 1 , wherein generating a data model of the data set comprises: updating a plurality of sufficient statistics for each record; updating parameters regarding the data model; and, assigning cluster membership to each record.

Claim 5

The method of claim 3 , wherein updating sufficient statistics for each record comprises: determining a posterior probability; incrementing a first sufficient statistics of the plurality of sufficient statistics by the posterior probability; and, incrementing a second sufficient statistics of the plurality of sufficient statistics by the posterior probability.

Claim 6

The method of claim 4 , wherein the first sufficient statistics relates to a joint probability distribution over a set of attributes including the attribute of each record.

Claim 7

The method of claim 4 , wherein the second sufficient statistics relates to a joint probability distribution over the cluster membership.

Claim 8

The method of claim 4 , wherein determining a posterior probability comprises: initially generating a joint probability based on the default value of the attribute of the record; determining the posterior probability based on the joint probability; and, correcting the posterior probability upon determining that the value of the attribute of the record varies from the default value.

Claim 9

The method of claim 4 , wherein incrementing a second sufficient statistics of the plurality of sufficient statistics comprises incrementing the second sufficient statistics of the plurality of sufficient statistics only upon determining that the value of the attribute of the record varies from the default value of the attribute.

Claim 10

The method of claim 3 , wherein generating a data model further initially comprises initializing the parameters regarding the data model in accordance with a predetermined manner.

Claim 11

A machine-readable medium having processor instructions stored thereon for execution by a processor to case performance of a method that facilitates fast clustering of a data set defined for a plurality of attributes, comprising: inputting the data set, the data set having a plurality of records each having a value for each attribute, wherein the value assigned to each attribute is selected from a plurality of possible values, one value from the plurality of possible values is designated a default value; storing a sparse representation of each record, including storing the value of the attribute of the record only upon determining that the attribute of the record has a value varying from the default value; clustering each record using the sparse representation of the record; generating a data model of the data set, utilizing the sparse representation of each record; and, outputting the data model.

Claim 12

A machine-readable medium having processor instructions stored thereon for execution by a processor to case performance of a method that facilitates fast clustering of a data set defined for a plurality of attributes, comprising: inputting the data set, the data set having a plurality of records each having a value for each attribute, wherein the value assigned to each attribute is selected from a plurality of possible values, one value from the plurality of possible values is designated a default value; storing a sparse representation of each record, including storing the value of the attribute of the record only upon determining that the attribute of the record has a value varying from the default value; clustering each record using the sparse representation of the record; generating a data model of the data set, utilizing the sparse representation of each record; and, outputting the data model.

Claim 13

The medium of claim 10 , wherein at least one record has a plurality of attributes, each attribute having a default value.

Claim 14

The medium of claim 10 , wherein generating a data model of the data set comprises: updating a plurality of sufficient statistics for each record; updating parameters regarding the data model; and, assigning cluster membership to each record.

Claim 15

The medium of claim 12 , wherein updating sufficient statistics for each record comprises: determining a posterior probability; incrementing a first sufficient statistics of the plurality of sufficient statistics by the posterior probability; and, incrementing a second sufficient statistics of the plurality of sufficient statistics by the posterior probability.

Claim 16

The medium of claim 13 , wherein the first sufficient statistics relates to a joint probability distribution over a set of attributes including the attribute of each record.

Claim 17

The medium of claim 13 , wherein the second sufficient statistics relates to a joint probability distribution over the cluster membership.

Claim 18

The medium of claim 13 , wherein determining a posterior probability comprises: initially generating a joint probability based on the default value of the attribute of the record; determining the posterior probability based on the joint probability; and, correcting the posterior probability upon determining that the value of the attribute of the record varies from the default value.

Claim 19

The medium of claim 13 , wherein incrementing a second sufficient statistics of the plurality of sufficient statistics comprises incrementing the second sufficient statistics of the plurality of sufficient statistics only upon determining that the value of the attribute of the record varies from the default value of the attribute.

Claim 20

The medium of claim 12 , wherein generating a data model further initially comprises initializing the parameters regarding the data model in accordance with a predetermined manner.

Claim 21

A computerized system comprising: a sparse representation of each record of a plurality of records of a data set, each record having a plurality of attributes, each record having a value for each attribute, wherein the value for each attribute is selected from a plurality of possible values, one value from the plurality of possible values is designated a default value, such that the sparse representation includes the value of the attribute of the record only upon the attribute of the record having a value varying from the default value; a data model of the data set, based on clusters of each record using the sparse representation of each record; and, a model generator to generate the data model from the clustered sparse representation.

Claim 22

A computerized system comprising: a sparse representation of each record of a plurality of records of a data set, each record having a plurality of attributes, each record having a value for each attribute, wherein the value for each attribute is selected from a plurality of possible values, one value from the plurality of possible values is designated a default value, such that the sparse representation includes the value of the attribute of the record only upon the attribute of the record having a value varying from the default value; a data model of the data set, based on clusters of each record using the sparse representation of each record; and, a model generator to generate the data model from the clustered sparse representation.

Claim 23

The system of claim 19 , wherein the model generator comprises a computer program.

Claim 24

The system of claim 19 , wherein the model generator performs a method comprising: updating a plurality of statistics for each record; updating parameters regarding the data model; and, assigning cluster membership to reach record.

Claim 25

The system of claim 21 , wherein updating sufficient statistics for each record comprises: determining a posterior probability; incrementing a first sufficient statistics of the plurality of sufficient statistics by the posterior probability; and, incrementing a second sufficient statistics of the plurality of sufficient statistics by the posterior probability.

Claim 26

The system of claim 22 , wherein the first sufficient statistics relates to a joint probability distribution over a set of attributes including the attribute of each record.

Claim 27

The system of claim 22 , wherein the second sufficient statistics relates to a joint probability distribution over the cluster membership.

Claim 28

The system of claim 22 , wherein determining a posterior probability comprises: initially generating a joint probability based on the default value of the attribute of the record; determining the posterior probability based on the joint probability; and, correcting the posterior probability upon determining that the value of the attribute of the record varies from the default value.

Claim 29

The system of claim 22 , wherein incrementing a second sufficient statistics of the plurality of sufficient statistics comprises incrementing the second sufficient statistics of the plurality of sufficient statistics only upon determining that the value of the attribute of the record varies from the default value of the attribute.

Claim 30

The system of claim 21 , wherein generating a data model further initially comprises initializing the parameters regarding the data model in accordance with a predetermined manner.