Method for dynamic knowledge capturing in production printing workflow domain

• US 20060242097A1
• Filed: 04/21/2005
• Published: 10/26/2006
• Est. Priority Date: 04/21/2005
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Cote, Alan Thomas, Shepherd, Michael David, Sun, Tong, Gu, Xue
• Granted Patent: US 7,395,254 B2
• Time in Patent Office: Days
• US Class Current: 706/45
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition

Abstract

A system and method are provided for managing a knowledge base system storing a plurality of data instances, each data instance including at least one field, each field having at least one item and provided with an associated field type indicating whether the field is allowed to have only a single item or multiple items. At least one large itemset is determined by generating a plurality of itemsets formed of possible combinations of items selected from items corresponding to fields of the stored data instances. Itemsets having a combination of more than one item corresponding to a field having an associated field type indicating that the field is allowed to have only a single value are eliminated. The remaining itemsets are processed for generating associate rules.

Claims

1. A knowledge base system comprising:

at least one processor;

at least one storage device accessible by the at least one processor for storing a plurality of data instances;

an interface device for receiving at least one data instance; and

a memory storing a series of executable instructions executable by the at least one processor for capturing a received data instance and determining via a field dependent heuristic determination if the received data instance is a duplicate of any data instance of the plurality of stored data instances, wherein the received data instance and the plurality of stored data instances each include at least one field each having an item, each item including at least one token, each token including a sequence of at least one character;

wherein the determination by the at least one processor comprises;

for each field of the received data instance comparing between tokens of the at least one token of the field and the at least one token of a corresponding field of a respective stored data instance and generating at least one corresponding token similarity value, wherein each token comparison between a first token and a second token includes determining a degree of matching between characters of the at least one character of the first token that and the at least one character of the second token, including taking character sequence into account, and outputting a field similarity degree based on the at least one token similarity value; and

for each respective stored data instance generating an instance similarity value based on the field similarity degree corresponding to the respective fields of the received data instance, wherein the determination of duplicity between the received data instance and the respective stored data instance is based on the instance similarity value.

2. The knowledge base system according to claim 1, wherein the series of executable instructions are further executed by the at least one processor to manage the knowledge base system as a dynamic knowledge base system comprising updating the knowledge base system, which includes storing the received data instance in the at least one storage device as a new data instance only when the determination of duplicity is that the received data instance is not a duplicate of any of the data instances of the plurality of stored data instances.

3. The knowledge base system according to claim 2, wherein the updating is performed on-the-fly.

4. The knowledge base system according to claim 1, wherein determining a degree of matching between characters of the at least one character of the first token that and the at least one character of the second token which takes character sequence into account includes sequentially comparing characters of the first token with characters of the second token, and searching for a character in characters of the second token which follow a previously found matching character which matches a character of the first token.

5. The knowledge base system according to claim 1, wherein determining the number of characters includes generating a similarity value by calculating (1−

n/x) for n characters found which do not match, where x is the number of characters in the first token.

6. The knowledge base system according to claim 5, wherein a token similarity value is generated for each token of the at least one token of at least one of the field of the received data instance and the corresponding field of the stored data instance, wherein generating the token similarity value for a token of one of the fields of the field of the received data instance and the corresponding field of the stored data instance includes taking a maximum value of corresponding similarity values generated when comparing the token to each token of the at least one token of at least one item of the other field of the field of the received data instance and the corresponding field of the stored data instance.

7. The knowledge base system according to claim 6, wherein generating the field similarity degree for the field includes summing the token similarity values generated for the tokens of the at least one of the field of the received data instance and the corresponding field of the stored data instance, and normalizing to one.

8. The knowledge base system according to claim 7, wherein generating the instance similarity value for each respective stored data instance includes summing all of the field similarity degrees generated for the respective fields of the received data instance corresponding to the comparison to the corresponding fields of the respective stored data instance.

9. The knowledge base system according to claim 8, wherein generating the instance similarity value for each respective stored data instance further includes weighting each field similarity degree for the respective fields of the received data instance with a predetermined weight value corresponding to the respective field of the received data instance.

10. The knowledge base system according to claim 1, wherein the determination of duplicity for each data instance of the plurality of stored data instances includes comparing the generated instance similarity value to a predetermined threshold value.

11. The knowledge base system according to claim 1, wherein when the field is an enumerated type field, generating the field similarity degree for the field further comprises assigning one of a high value and a low value in accordance with comparison of results of the output field similarity degree with a predetermined enumeration field threshold value.

12. The knowledge base system according to claim 1, wherein a field type is provided in association with each field of the received data instance and the stored data instances of the plurality of stored data instances for indicating whether the associated field is allowed to have one of only a single item and multiple items.

13. The knowledge base system according to claim 12, wherein the series of executable instructions are further executed by the at least one processor to manage the knowledge base system as a dynamic knowledge base system including generating associate rules associated with the plurality of stored data instances, comprising determining at least one large itemset including at least one combination of at least one item that has support above a minimum predetermined support threshold value including eliminating at least one itemset having a combination of more than one item held by a field having an associated field type indicating that the field is allowed to have only a single value, and processing the remaining a least one itemset for deriving at least one associate rule.

14. A knowledge base system for operation in a production printing workflow environment comprising:

at least one storage device accessible by at least one processor for storing a plurality of data instances; and

a memory storing a series of executable instructions executable by the at least one processor for generating at least one associate rule associated with a plurality of stored data instances, wherein the plurality of stored data instances each include at least one field, each having at least one item, and an associated field type for indicating whether the field is allowed to have one of only a single item and multiple items, wherein the generating at least one associate rule by the at least one processor comprises;

generating a plurality of itemsets formed of possible combinations of at least one item selected from the at least one item corresponding to the at least one field of the plurality of stored data instances;

eliminating at least one itemset from the plurality of itemsets having a combination of more than one item corresponding to a field having an associated field type indicating that the field is allowed to have only a single value; and

processing a remaining at least one itemset for deriving at least one associate rule.

15. The knowledge base system according to claim 14, further comprising an interface device for receiving at least one data instance, wherein the series of executable instructions are further executed by the at least one processor for capturing a received data instance and managing the knowledge base system as a dynamic knowledge base system, comprising storing the received data instance with the plurality of stored data instances, and attempting to generate at least one associate rule associated with the plurality of data instances, including the received data instance.

16. The knowledge base system according to claim 14, wherein the generating at least one associate rule further comprises:

selecting an itemset from the at least one remaining itemset when a percentage of data instances of the plurality of stored data instances in which all of the items of the selected itemset occur in items corresponding to the at least one field of the respective data instances exceeds a predetermined support threshold value, and

eliminating any unselected itemsets from the at least one remaining itemset before processing the at least one remaining itemset for deriving the at least one associate rule.

17. The knowledge base system according to claim 16, wherein processing the at least one remaining itemset for deriving at least one associate rule therefrom comprises:

generating each possible subset of the selected itemset;

determining for each generated subset a ratio of a frequency of occurrence of the subset to a frequency of occurrence of the selected itemset; and

deriving a rule;

if (items of the selected itemset) then (items of the selected itemset take away the items of the subset) when the ratio exceeds a predetermined confidence threshold value.

18. A method for managing a knowledge base system, the method comprising:

storing a plurality of data instances, each data instance of the plurality of data instances including at least one field each having at least one item;

providing each field of the at least one field with an associated field type for indicating whether the field is allowed to have one of only a single item and multiple items;

generating a plurality of itemsets formed of possible combinations of at least one item selected from the at least one item corresponding to the at least one field of the plurality of stored data instances;

eliminating at least one itemset having a combination of more than one item corresponding to a field having an associated field type indicating that the field is allowed to have only a single value; and

processing at least one remaining itemset for generating at least one associate rule.

19. The method according to claim 18, wherein the method further comprises updating a schema of the knowledge base with the generated at least one associate rule.

20. The method according to claim 18, further comprising:

receiving at least one data instance;

capturing a received data instance; and

managing the knowledge base system as a dynamic knowledge base system comprising;

storing the received data instance with the plurality of stored data instances; and

attempting to generate at least one associate rule associated with the plurality of data instances including the received data instance.

21. The method according to claim 20, wherein the attempting to generate the at least one associate rule is performed on-the-fly.

22. The method according to claim 18, further comprising selecting an itemset from the at least one remaining itemset when a percentage of data instances of the plurality of stored data instances in which all of the items of the selected itemset occur in items held in the at least one field of the respective data instances exceeds a predetermined support threshold value;

and

eliminating any unselected itemsets from the at least one remaining itemset before processing the at least one remaining itemset for generating the at least one associate rule.

23. The method according to claim 22, wherein processing the at least one remaining itemset comprises:

generating each possible subset of the selected itemset;

determining for each generated subsets a ratio of a frequency of occurrence of the subset to a frequency of occurrence of the selected itemset; and

deriving a rule;

if (items of the selected itemset) then (items of the selected itemset take away the items of the subset) when the ratio exceeds a predetermined confidence threshold value.