BACKGROUND OF THE INVENTION

1. Field of the Invention

This invention generally relates to methods and systems for clustering objects and finding prime redescriptors for the clusters.

2. Background Art

In many technologies, enormous amounts of information are available. For example, in biogenetics, huge amounts of data can be collected. It is often useful to group data objects together in categories or clusters. There are many ways to do this. Unfortunately, with many current systems, important information can be lost when the data objects are grouped.

For example, given a body of evidence, such as, a list of n patients and the expression level of m genes and no further evidence, what can be said about the patients? The data is usually given as an nÃ—m array D. One natural task is to find all the groups of sizeâ‰§k and deduce their description. Then the next question is to get all the redescriptions or other alternate ways of defining this group based on the evidence D. For example, a group may be denoted by patients who have genes 1, 2 and 3 expressed at a high level. It is possible that the same group is denoted by high level of expression of gene 1 along with the expression of either genes 4; or 5. These different expressions denote the same group and is an important information to have for a better understanding of the data. It would be desirable to organize and access the data so that important information like this is not lost.

SUMMARY OF THE INVENTION

An object of this invention is to cluster objects and to find prime redescriptors for the clusters.

Another object of the present invention is to provide a method and system for identifying, for defined data sets, the smallest collection of all the essential descriptions that can define every other description in the data set.

These and other objects are attained with a method of and system for clustering objects and finding prime redescriptors for the clusters of objects. The method comprises the step of forming a matrix, including (i) identifying on the matrix, each of a set of given objects, and (ii) for each of said set of objects, identifying on the matrix, by using binary values, whether or not the object has each of a set of given features. The method comprises the further steps of finding all the minimal pure disjunctions on the matrix, adding said minimal pure disjunctions to the matrix to form an augmented matrix, and finding all the maximal pure conjunctions on the augmented matrix. These maximal pure conjunctions are used to identify prime redescriptors for the set of objects.

The preferred embodiment of the invention, described below in detail, utilizes a principal, referred to as prime descriptors, which is the smallest collection of all the essential descriptions that can define every other description in the data set.

Redescriptions, in a setting where the expressions are disjunctions of conjunctions of two (or less) variables, is discussed in â€œTurning cartwheels: An alternating algorithm for mining redescriptionsâ€ In ACM SIGKDD Conference on Knowledge Discovery and Data Mining. ACM Press, August 2004. by N. Ramakrishnan, D. Kumar, B. Mishra, M. Potts, and R. F. Helm (Ramakrishnan, et al.).

Further benefits and advantages of the invention will become apparent from a consideration of the following detailed description, given with reference to the accompanying drawings, which specify and show preferred embodiments of the invention.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 shows a preferred method for practicing the invention.

FIG. 2 shows a part of a graph that illustrates an aspect of this invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

The present invention, generally, provides a method and system for clustering objects and finding prime redescriptors for the clusters. FIG. 1 illustrates a preferred method for carrying out the invention. The method comprises the step 12 of forming a matrix, including (i) identifying on the matrix, each of a set of given objects, and (ii) for each of said set of objects, identifying on the matrix, by using binary values, whether or not the object has each of a set of given features.

The method comprises the further step 14 of finding all the minimal pure disjunctions on the matrix, step 16 of adding said minimal pure disjunctions to the matrix to form an augmented matrix, and step 20 of finding all the maximal pure conjunctions on the augmented matrix. These maximal pure conjunctions are used at step 22 to identify prime redescriptors for the set of objects.

The following examples and definitions will illustrate the preferred embodiment of the invention.

Input: Given o₁, o₂, . . . , o_nobjects, each with or without F₁, F₂, . . . F_mfeatures represented in a binary matrix D where D[i],[J]=0 if feature F_jis absent in object o_iand D[i]L=1 otherwise. Consider the following example from Ramakrishnan, et al:

X₁X₂X₃X₄Y₁Y₂Y₃Y₄o₁00011001o₂10101101o₃11000110o₄01100100o₅00010011

Definition 1 (description e, F(e), S(e), redescription R(e)) Given D,

1. e(V) or e, a boolean expression on the set of variables (features) V is a description. F(e) denotes the set of features used in the description, i.e., F(e)=V. Further,
S(e)={o_i|e is TRUE for D [o_i]}

Two descriptions are e₁(V₁) and e₂(V₂) are distinct (denoted as e₁â‰ e₂), if one of the following holds: (1) V₁â‰ V₂, or (2) there exists some Dâ€² for which S(e₁)â‰ S(e₂). This rules out tautologies. For example, expressions (X₁âˆ’X₂) and (X₁ X₂) are not distinct.

2. eâ€² is a redescription of e, if and only if S(e) =S(eâ€²) holds for the given D. R(e) a collection of all distinct redescriptions of e.

Consider D shown in the example. S (e=(X₁+Y₃))=(o₂, o₃, o₅} and S(e=( X₁ Y₃))=(o₁, o₄} are descriptions (on D). The following property about redescriptions is important: it enables us to divide the description space into non-overlapping sets.

Lemma 1 Redescription is reflexive, symmetric and transitive: it induces a partition on a collection of descriptions on D.

Fact 1 Given D, if (e₂â‰ e₁) Îµ 2 R(e), then (e₁e₂), (e₁+e₂) Îµ R(e).

Clearly there are some redundancies in R(e). The next task is to trim down R(e) to its essentials! Next we discuss the acceptable forms an expression may take.

An important question to address is whether fixing a set of variables (features) on a collection of elements (or rows) in D, can endow a unique (upto tautology) description. We answer in the negative using a simple example.

X₁X₂X₃o₁100o₂011o₃001o₄001

Let e be a description on X₁and X₂and S(e)=(o₁, o₂}. Then given this D, there are at least two distinct descriptions (e₁â‰ e₂) of e: (1) e₁=X₁+X₂, and, (2) e₂=X₁ X₂+ X₁X₂.

Philosophically, description (1) is supported by Occam's Razor Priniciple which advocates the â€œsimplestâ€ form. On the other hand description (2) is more resilient, i.e., even if any one of D[i][j], i=3, 4, j=1, 2 is switched to 1, the description of e with the given S is still valid.

Problem 1 Given an nÃ—m array D and a collection of sets S of the row labels, the problem is to find all the R(e) for each S(e) Îµ S.

Theorem 1 Given an nÃ—m array D and a collection of sets S of the row labels, if every non-empty set of row labels S Îµ S, then for each S(e) S, |R(e)|=1 i.e., each set has a unique description (hence no redescription).

Definition 2 (basis B(e)) B(e)_R(e) is a basis of Rye) satisfying the following: (1) for each e₀Îµ R(e), there is e₁, e₂, . . . e_mÎµ B, mâ‰§1, such that f(e₁, e₂, . . . e_m) Îµ B(e) where f() is a Boolean function, and, (2) no e₀Îµ B(e) can be represented as a Boolean function of any m, e₁, e₂, . . . e_mÎµ B (e_iâ‰ e₀, 1â‰¦i â‰¦m).

A different problem where S is not given can be stated as below: this is perhaps the more tractable version of the problem.

Problem 2 Given an nÃ—m array D, a quorum k, and a specific form of Boolean expression, the problem is to find all the |S(e)|â‰§k and R(e) where e and each eâ€² Îµ R(e) is in the specified form.

Form of Expression. Since expressions involve the features and are a description of a collection of elements, simplicity in their form is desired.

An expression is a pure conjunction if it is a conjunction of atomic elements and a pure disjunction if it is a disjunction of atomic elements. For example, let e₁=(X₁+X₂), e₂=(X₁X₃X₄) and e₃=(X₁+X₂X₃). Then e₁is a pure disjunction, e₂is a pure conjunction and e₃is neither. If e is a pure conjunction then e is a pure disjunction and vice-versa.

Clearly, there are myriads of forms a description can take. Eventually a human-expert will read and interpret the expression. So we have to compromise between expressibility and readability. We choose to use the following form: conjunctions of pure disjunctions (CPD). This form has a powerful expressive capability and yet is understandable in English terms.

Definition 3 (relaxation of e X(e)) Given D and quorum k, let e₁be an expression on the set of variables V₁=F(e₁), then e₂is a relaxation of e₁with V₂=F(e₂), if both of the following hold: (a) V₂âŠ‚ V₁and (b) e₂is obtained from e₁by replacing each variable Ï… Îµ V₁âˆ’V₂by the constant TRUE. The collection of all the relaxations of e is denoted by X(e).

Lemma 2 If e₂is a relaxation of e₁then S(e₂) âŠƒ S(e₁).

Note that a relaxation of e is not necessarily a redescription of e. Consider the example in Section 2. X₁Îµ X ( X₁ Y₃) but X₁âˆ‰ R( X₁ Y₃) since (S( X₁)={o₁, o₄, o₅}) âŠƒ (S( X₁ Y₃)={o₁, o₄}).

Definition 4 (prime descriptors P(e)) Given D, and quorum k, P(e) âŠ‚ R(e) is a set of prime descriptors if (1) for each eâ€² Îµ P(e), there is no eâ€²₁, eâ€²₂, . . . , eâ€²_mâŠ‚ P(e)âˆ’{e} such that (eâ€²₁, eâ€²₂. . . eâ€²_m) Îµ P(e). (2) for each eâ€² Îµ R(e) there exists eâ€²₁, eâ€²₂, . . . , eâ€²_mâŠ‚ P(e) such that (eâ€²₁, eâ€²₂, . . . , eâ€²_m)Îµ R(e).

Theorem 2 P(e) is unique.

Corollary 1 Any redescription of e is derivable from P(e).

Corollary 2 If |P(e)|>1, then each eâ€² Îµ P(e) is a relaxation of some eâ€³ Îµ R(e).

Algorithm

Input: Given an nÃ—m Boolean matrix D and a quorum kâ‰¦n. D represents n elements each with at most m features.

Output: The task is to obtain all descriptions e in the CPD form with P(e), such that |S(e)|â‰¦k.

(1) Preprocess: Find all the minimal pure disjunctions. Let them be A in number. Then this step takes O(mn+A log A) time based on the algorithm in â€œProtein folding trajectory analysis using patterned clustersâ€ Asia Pacific Bioinformatics Conference, 2005 by J. Feng, L. Parida, and R. Zhou (J. Feng, et al.)

(2) CPD Expressions Computation: Augment the input matrix D with the results of the first step to obtain nÃ—(m+a) matrix Dâ€². Find all the maximal pure conjunctions on this augmented matrix. Let them be B in number. This takes O(m(n+A)+B log B) based on the algorithm in the above-mentioned J. Feng, et al.

(3) Prime Redescription Computation: Consider a directed graph G(V,E) called the universal graph, where Ï… Îµ V corresponds to a non-empty subset of the column labels of Dâ€² denoted by C(Ï…). A directed edge (Ï…₂Ï…₁) Îµ E if C(Ï…₁) âŠ‚ C(Ï…₂) and |C(Ï…₂)|âˆ’|C(Ï…₁)|=1. Next, we label each node as follows: if C(Ï…) is reported in Step 2, we assign the label LIVE, else we assign the label DEAD to vertex Ï…. Redescription of e:

Let S(e)=C(Ï…). Then eâ€² is a redescription of e if Ï…â€² with C(Ï…â€²)=S(eâ€²) is a LIVE descendent of Ï… that has no LIVE ancestor Ï…â€³ which is a descendent of Ï….

Back to the example. Consider the example presented in Section 2. Assume quorum k=1.

1) Preprocess: At this step we compute the minimal pure disjunctions.

S(e)e (minimal pure disjunctions)new col label2, 3, 4, 5X₁+ X₂+ X₃+ X₄+ Y₁+ Y₂+ Y₃+ Y₄Z₁1, 3, 4, 5 X₁+ X₂+ X₃+ X₄+ Y₁+ Y₂+ Y₃+ Y₄Z₂1, 2, 4, 5 X₁+ X₂+ X₃+ X₄+ Y₁+ Y₂+ Y₃+ Y₄Z₃1, 2, 3, 5X₁+ X₂+ X₃+ X₄+ Y₁+ Y₂+ Y₃+ Y₄Z₄1, 2, 3, 4X₁+ X₂+ X₃+ X₄+ Y₁+ Y₂+ Y₃+ Y₄Z₅3, 4, 5X₂+ Y₁+ Y₃Z₆2, 3, 5X₁+ Y₃Z₇1, 3, 5 X₃+ X₄+ Y₂+ Y₃Z₈1, 2, 3X₁+ Y₁Z₉

2) CPD computation (e's): The expressions in the CPD form are shown below:

S(e)e (in CPD form)S(e)e (in CPD form)1 X₁ X₂ X₃X₄Y₁ Y₂ Y₃Y₄2, 3, 4, 5Z₁= (X₁+ X₂+ X₃+ X₄+ Y₁+ Y₂+ Y₃+ Y₄)2X₁ X₂X₃ X₄Y₁Y₂ Y₃Y₄1, 3, 4, 5Z₂= ( X₁+ X₂+ X₃+ X₄+ Y₁+ Y₂+ Y₃+ Y₄)3X₁X₂ X₃ X₄ Y₁Y₂Y₃ Y₄1, 2, 4, 5Z₃= ( X₁+ X₂+ X₃+ X₄+ Y₁+ Y₂+ Y₃+ Y₄)4 X₁X₂X₃ X₄ Y₁Y₂ Y₃ Y₄1, 2, 3, 5Z₄= (X₁+ X₂+ X₃+ X₄+ Y₁+ Y₂+ Y₃+ Y₄)5 X₁ X₂ X₃X₄ Y₁ Y₂Y₃Y₄1, 2, 3, 4Z₅= (X₁+ X₂+ X₃+ X₄+ Y₁+ Y₂+ Y₃+ Y₄)1, 2 X₂Y₁ Y₃3, 4, 5Z₆= (X₂+ Y₁+ Y₃)1, 4 X₁ Y₃2, 3, 5Z₇= (X₁+ Y₃)1, 5 X₁ X₂ X₃X₄ Y₂Y₄2, 3, 4 X₄Y₂2, 3X₁ X₄Y₂1, 4, 5 X₁2, 4X₃ X₄Y₂ Y₃1, 3, 5Z₈= ( X₃+ X₄+ Y₂+ Y₃)3, 4X₂ X₄ Y₁Y₂ Y₄1, 2, 5 X₂Y₄3, 5 X₃ Y₁Y₃1, 2, 4 Y₃4, 5 X₁ Y₁1, 2, 3Z₉= (X₁+ Y₁)

3) Computing Prime Redescriptions (P(e)'s). We take two cases that were also handled in Ramakrishnan, et al. Here we complete the answers using prime descriptors. In the example the features were partitioned into two sets the X_j's and the Y_j's such that each redescription is from only one set or the other. As an example consider the set S(e₁)={o₄}. The prime descriptors that separate the X's from the Y's are:
e₁ [Image Omitted] X₁X₂ X₁ X₄X₂X₃ Y₁ Y₃ Y₃ Y₄

If the mixing of the X's and the Y's are allowed,
e₁ [Image Omitted] X₁Y₂ X₁ Y₄X₂ Y₃X₃ Y₁X₃ Y₄ X₄Y₃

The only redescriptions shown in N. Ramakrishnan, et al are:
e₁ [Image Omitted] X₁X₃ Y₁ Y₃ Y₃ Y₄

The following are some non-prime descriptors. Note that each can be derived or deduced trivially from the prime descriptors.
e₁ [Image Omitted] X₁X₂X₃ X₁X₂ X₄ X₁X₃ X₄ X₁X₂X₃ X₄ Y₁Y₂ Y₃Y₂ Y₃ Y₄ Y₁Y₂ Y₃ Y₄

Consider a second example S(e₂)={o₁, o₂, o₅}. The prime descriptors of this are:
e₂ [Image Omitted] X₂Y₄

Ramakrishnan, et al. gives the redescriptions as:
e₂ [Image Omitted] (X₃âˆ©X₁)âˆª(X₄âˆ’X₃)(Y₃âˆ’Y₂)âˆª(Y₁âˆ’Y₃)Y₄

2.2 On Jaccard's coefficient J<1
Given two sets S₁and S₂the Jaccard's coefficient Jof the two is given by $J â ¡ (S_{1}, S_{2}) = \frac{ï˜ƒ S_{1} â‹‚ S_{2} ï˜„}{ï˜ƒ S_{1} â‹‚ S_{2} ï˜„ + ï˜ƒ S_{1} - S_{2} ï˜„ + ï˜ƒ S_{2} - S_{1} ï˜„}$

When S₁and S₂are identical, then J=1.0. In practice, it is useful to talk about sets that are nearly equal but not necessarily exactly, i.e., the two sets have a Jaccard's coefficient<1.

In this problem setting, we absorb this â€œapproximationâ€ in Steps 1 and 2, so that the prime descriptor computation step is unchanged. Next, we redefine S(e) taking Jaccard's coefficient J into account as follows:

Definition 5 (S(e)) Given D, a quorum k and a Jaccard's coefficient 0<Î¾<1. Let e_ibe the expression e restricted to the feature Ï…_ii.e., (F(e_i)={Ï…_i})âŠ‚F(e), and let S(e_i)âŠ‚S(e) be the collection of rows where e_iholds. Then for each pair Ï…_i, Ï…_jÎµ F(e), the following must hold:
J(S(e_i), S(e_j)=Î¾

Thus the burden of the computation is isolated into the first two steps of the algorithm. The two steps can use the algorithm presented in â€œApproximate patterns on mulit-feature data.â€ 2004. Manuscript. L. Parida (Parida).

FIG. 2 illustrates an example of the application of the instant invention. This example starts with a cluster 40 of four objects X1X2X3X4. This cluster 40 can be re-expressed as four separate clusters 42, 44, 46 and 50, each of which has three of the four objects of cluster 40. These four clusters, in turn, can be re-expressed as six clusters 52, 54, 56, 60, 62 and 64, each of which has two of the objects of the original cluster 40. Each of the clusters 42, 44, 46, and 50 can be re-expressed as three separate clusters, however because of commonality, a total of six clusters are re-expressed from the four clusters 42, 44, 46 and 50. The clusters 52, 54, 56, 60, 62 and 64 can be re-expressed as a total of four clusters 66, 70, 72 and 74, each of which has a respective one of the objects of the original cluster 40. As FIG. 2 shows, the prime descriptors are X1X2, X1X3 and X1X3X4.

It should be understood that the present invention can be realized in hardware, software, or a combination of hardware and software. Any kind of computer/server system(s)â€”or other apparatus adapted for carrying out the methods described hereinâ€”is suited. A typical combination of hardware and software could be a general purpose computer system with a computer program that, when loaded and executed, carries out the respective methods described herein. Alternatively, a specific use computer, containing specialized hardware for carrying out one or more of the functional tasks of the invention, could be utilized.

The present invention can also be embodied in a computer program product, which comprises all the respective features enabling the implementation of the methods described herein, and whichâ€”when loaded in a computer systemâ€”is able to carry out these methods. Computer program, software program, program, or software, in the present context mean any expression, in any language, code or notation, of a set of instructions intended to cause a system having an information processing capability to perform a particular function either directly or after either or both of the following: (a) conversion to another language, code or notation; and/or (b) reproduction in a different material form.

While it is apparent that the invention herein disclosed is well calculated to fulfill the objects stated above, it will be appreciated that numerous modifications and embodiments may be devised by those skilled in the art and it is intended that the appended claims cover all such modifications and embodiments as fall within the true spirit and scope of the present invention.