Method for discovering groups of objects having a selectable property from a population of objects

• US 6,154,739 A
• Filed: 06/26/1998
• Issued: 11/28/2000
• Est. Priority Date: 06/26/1997
• Status: Expired due to Term

• Current Assignee: Gmd--Forschungszentrum Informationstechnik GmbH, GMD-Forschungszentrum Informationstechnik GmbH
• Original Assignee: GMD-Forschungszentrum Informationstechnik GmbH
• Inventors: Wrobel, Stefan
• Primary Examiner(s): Homere, Jean R.
• Application Number:
  US09/105,160
• Time in Patent Office: 886 Days
• Field of Search: 707/3, 707/5, 707/6, 707/100, 707/103
• US Class Current: 1/1
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

The method is for detecting a selectable number of groups of objects having at least one selectable characteristic from a population of objects specifiable by a plurality of attributes. The objects of the population are subdivided into object groups of a first order, on the basis of respectively at least one attribute. The quality of each object group of this order is detected, on the basis of the total number of its objects and the number of its objects having said at least one characteristic. Each object group of this order is included into the number of object groups to be detected, if the object group has a quality higher than the lowest quality of the object group among the object groups detected up to this point. A hypothetical quality is detected on the basis exclusively of those objects of this object group which have at least one of the characteristics. The hypothetical quality is a quality of a hypothetical group derived from the actually processed group and including exclusively the objects thereof having the at least one characteristic. All those object groups of this order the hypothetical quality of which includes a selectable quality value and particularly is of the quality of the respective object groups, are subdivided into object groups of the next lower order, by selecting at least one attribute.

Claims

1. A method for detecting a selectable number of groups of objects having at least one selectable characteristic from a population of objects specifiable by a plurality of attributes, each of said object groups having a quality which, by means of a selectable function, results from the number of objects of the object group and from an unusualness of the distribution of the at least one characteristics within the object group and which is detected by a relation between the distribution of the characteristics of the respective object group and the distribution of the characteristics in a reference population, said method comprising the following steps:

a) selecting the at least one characteristic by selecting at least one of the attributes specifying the objects of the population,

b) subdividing the objects of the population into object groups of a first order, on the basis of respectively at least one attribute,

c) detecting the quality of each object group of this order, on the basis of the total number of its objects and the number of its objects having said at least one characteristic and/or the number of its objects not having said characteristic,

d) for each object group, including the object group of this order into the number of object groups to be detected, if the object group has a quality higher than the lowest quality of the object group among the object groups detected up to this point,

e) for each object group of this order, detecting at least one hypothetical first quality on the basis exclusively of those objects of this object group which have at least one of said characteristics, and/or at least one hypothetical second quality on the basis exclusively of those objects of this object group which do not have at least one of said characteristics, wherein the at least one of the first or second qualities is a quality of a hypothetical group derived from the actually processed group and comprising exclusively the objects thereof having one or not having one of said at least one characteristics,

f) subdividing all those object groups of this order the at least one of the respectively assigned first or second hypothetical qualities of which comprise a selectable quality value and particularly are of the quality of the respective object groups, into object groups of the next lower order, by selecting at least one attribute, and

g) repeating steps c) to f) as often as a selectable criterion for termination has been reached.

2. The method according to claim 1, characterized in that in step d) an object group is included into the number of object groups to be detected only if it is additionally verified that this object group comprises a selectable first minimum number of objects.

3. The method according to claim 1, characterized in that in step e) the first or second hypothetical quality is detected only if the number of objects having said characteristic comprises a selectable second minimum number.

4. The method according to claim 2, characterized in that the first minimum number is equal to the second minimum number.

5. The method according to claim 1, characterized in that the criterion for termination is defined in that the object groups are subdivided until at a subdivision stage no attributes exist anymore for a further subdividing into object groups.

6. The method according to claim 1, characterized in that the criterion for termination is defined in that the subdividing of object groups into the next lower order results exclusively in object groups whose number is smaller than a selectable third minimum number.

7. The method according to claim 2, characterized in that the third minimum number is equal to the first or the second minimum number.

8. The method according to claim 1, characterized in that the criterion for termination is defined to be the lapse of a selectable period of time.

9. The method according to claim 1, characterized in that the object groups at each subdivision stage according to steps c) to f) are processed in the order of their qualities and/or in the order of their first and/or second hypothetical qualities, with the object group having the highest quality and respectively hypothetical quality being processed first.

10. The method according to claim 1, characterized in that at each subdivision stage the object groups are processed according to a selectable scheme, particularly a scheme being different from one subdivision stage to the next one.

11. The method according to claim 1, characterized in that at each subdivision stage it is examined, on the basis of the combination of the attributes defining the object groups, whether a plurality of object groups with the same combination of attributes exist, and, if such is the case, only one of those object groups is examined and, depending on the results of such examinations, is further subdivided.

12. The method according to claim 1, characterized in that in step d) an object group is included into the number of object groups to be detected only if it is additionally verified that the attributes of this object group differ from those of the object group detected up to this point at least by a predeterminable minimum distance.

13. The method according to claim 1, characterized in that the attributes of the objects of the population are included in a relational database, especially in interlinked listings or the like.