Information analysing apparatus

• US 20040088308A1
• Filed: 08/13/2003
• Published: 05/06/2004
• Est. Priority Date: 08/16/2002
• Status: Abandoned Application

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: McClean, Alistair William, Bailey, Alexander
• Application Number:
  US10/639,655
• Publication Number:
  US 20040088308A1
• Time in Patent Office: Days
• US Class Current: 707/100
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification

Abstract

Information analysing apparatus is described for clustering information elements in items of information into groups of related information elements. The apparatus has an expected probability calculator (11a), a model parameter updater (11b) and an end point determiner (19) for iteratively calculating expected probabilities using first, second and third model parameters representing probability distributions for the groups, for the elements and for the items, updating the model parameters in accordance with the calculated expected probabilities and count data representing the number of occurrences of elements in each item of information until a likelihood calculated by the end point determiner meets a given criterion.

The apparatus includes a user input (5) that enables a user to input prior information relating to the relationship between at least some of the groups and at least some of the elements. At least one of the expected probability calculator (11a), the model parameter updater (11b) and the likelihood calculator is arranged to use prior data derived from the user input prior information in its calculation. In one example, the expected probability calculator uses the prior data in the calculation of the expected probabilities and in another example, the count data used by the model parameter updater and the likelihood calculator is modified in accordance with the prior data.

Claims

1. Information analysing apparatus for clustering information elements in items of information into groups of related information elements, the apparatus comprising:

a count data provider for providing count data representing the number of occurrences of elements in each item of information;

an initial model parameter determiner for determining first model parameters representing a probability distribution for the groups, second model parameters representing for each element the probability for each group of that element being associated with that group, and third model parameters representing for each item the probability for each group of that item being associated with that group;

a user input receiver for enabling a user to input prior information relating to the relationship between at least some of the groups and at least some of the elements;

a prior data determiner for determining from prior information input by a user using the user input receiver prior probability data for at least some of the second model parameters;

an expected probability calculator for receiving the first, second and third model parameters and the prior probability data and for calculating, for each item of information and for each information element of that item, the expected probability of that item and that element being associated with each group using the first, second and third model parameters and the prior probability data determined by the prior data determiner;

a model parameter updater for updating the first, second and third model parameters in accordance with the expected probabilities calculated by the expected probability calculator and the count data stored by the count data provider;

a likelihood calculator for calculating a likelihood on the basis of the expected probabilities and the count data stored by the count data provider; and

a controller for causing for causing the expected probability calculator, the model parameter updater and the likelihood calculator to recalculate the expected probabilities using the prior probability data and updated model parameters, to update the model parameters and to recalculate the likelihood, respectively, until the likelihood meets a given criterion.

2. Apparatus according to claim 1, wherein the user input receiver is arranged to enable a user to input prior information by specifying the allocation of information elements to groups.

3. Apparatus according to claim 2, wherein the user input receiver comprises a user interface configured to display a table having cells arranged in rows and columns with one of the columns and rows representing groups and the other representing information elements and the user input receiver is arranged to associate an information element with a group when that information element is placed by the user in a cell in the row or column representing that group.

4. Apparatus according to claim 2, wherein the user input receiver is arranged to enable a user to specify a relevance of an allocated information element to a group.

5. Apparatus according to claim 1, wherein the user input receiver is arranged to enable a user to input data indicating the overall relevance of prior information input by the user.

6. Apparatus according to claim 1, wherein the expected probability calculator is arranged to calculate the expected probabilities of a given item and element being associated with each of the groups by, for each group, obtaining a numerator value group by multiplying the first model parameter, the second model parameter, the third model parameter and the prior probability data for that group, item and element, and then normalising by dividing by the sum of the numerators for each group.

7. Information analysing apparatus for clustering information elements in items of information into groups of related information elements, the apparatus comprising:

a count data provider for providing count data representing the number of occurrences of elements in each item of information;

an initial model parameter determiner for determining first model parameters representing a probability distribution for the groups, second model parameters representing for each element the probability for each group of that element being associated with that group, and third model parameters representing for each item the probability for each group of that item being associated with that group;

a user input receiver for enabling a user to input prior information for modifying the count data;

a prior data determiner for determining from prior information input by a user using the user input receiver prior data and for modifying the count data provided by the count data provider in accordance with the prior data to provide modified count data;

an expected probability calculator for receiving the first, second and third model parameters and for calculating, for each item of information and for each information element of that item, the expected probability of that item and that element being associated with each group using the first, second and third model parameters;

a model parameter updater for updating the first, second and third model parameters in accordance with the expected probabilities calculated by the expected probability calculator and the modified count data;

a likelihood calculator for calculating a likelihood on the basis of the expected probabilities and the modified count data; and

a controller for causing for causing the expected probability calculator, the model parameter updater and the likelihood calculator to recalculate the expected probabilities using updated model parameters, to update the model parameters and to recalculate the likelihood, respectively, until the likelihood meets a given criterion.

8. A method of clustering information elements in items of information into groups of related information elements, the method comprising a processor carrying out the steps of:

providing count data representing the number of occurrences of elements in each item of information;

determining initial first model parameters representing a probability distribution for the groups, initial second model parameters representing for each element the probability for each group of that element being associated with that group, and initial third model parameters representing for each item the probability for each group of that item being associated with that group;

determining from prior information input by a user using a user input receiver prior probability data for at least some of the second model parameters;

calculating, for each item of information and for each information element of that item, the expected probability of that item and that element being associated with each group using the initial first, second and third model parameters and the determined prior probability data;

updating the first, second and third model parameters in accordance with calculated expected probabilities and the count data;

calculating a likelihood on the basis of the expected probabilities and the count data; and

causing the expected probability calculating, model parameter updating and likelihood calculating to be repeated, until the likelihood meets a given criterion.

9. A method according to claim 8, wherein the prior information specifies the allocation of information elements to groups.

10. A method according to claim 9, further comprising displaying on a display of the user input receiver a table having cells arranged in rows and columns with one of the columns and rows representing groups and the other representing information elements to enable input of prior information and associating an information element with a group when that information element is placed by the user in a cell in the row or column representing that group.

11. A method according to claim 9, comprising enabling a user to specify a relevance of an allocated information element to a group using the user input receiver.

13. A method according to claim 8, further comprising calculating expected probabilities of a given item and element being associated with each of the groups by, for each group, obtaining a numerator value group by multiplying the first model parameter, the second model parameter, the third model parameter and the prior probability data for that group, item and element, and then normalising by dividing by the sum of the numerators for each group.

30. A signal comprising program instructions for programming a processor to carry out a method in accordance with claim 8.

32. A storage medium comprising program instructions for programming processor to carry out a method in accordance with claim 8.

12. A method according to any of claims, which further comprises enabling a user to input data indicating the overall relevance of prior information input by the user using the user input receiver.

14. A method of clustering information elements in items of information into groups of related information elements, the method comprising a processor carrying out the steps of:

providing count data representing the number of occurrences of elements in each item of information;

determining initial first model parameters representing a probability distribution for the groups, initial second model parameters representing for each element the probability for each group of that element being associated with that group, and initial third model parameters representing for each item the probability for each group of that item being associated with that group;

determining prior data from prior information input by a user using a user input receiver;

modifying the count data in accordance with the prior data to provide modified count data;

calculating, for each item of information and for each information element of that item, the expected probability of that item and that element being associated with each group using the first, second and third model parameters;

updating the first, second and third model parameters in accordance with the calculated expected probabilities and the modified count data;

calculating a likelihood on the basis of the expected probabilities and the modified count data; and

causing the expected probability calculating, model parameter updating and likelihood calculating to be repeated, until the likelihood meets a given criterion.

15. Calculating apparatus for information analysing apparatus for clustering information elements in items of information into groups of related information elements, the apparatus comprising:

a receiver for receiving count data representing the number of occurrences of elements in each item of information modified by prior information input by a user using the user input, first model parameters representing a probability distribution for the groups, second model parameters representing for each element the probability for each group of that element being associated with that group, third model parameters representing for each item the probability for each group of that item being associated with that group;

an expected probability calculator for receiving the first, second and third model parameters and for calculating, for each item of information and for each information element of that item, the expected probability of that item and that element being associated with each group using the first, second and third model parameters;

a model parameter updater for updating the first, second and third model parameters in accordance with the expected probabilities calculated by the expected probability calculator and the modified count data;

a likelihood calculator for calculating a likelihood on the basis of the expected probabilities and the modified count data; and

a controller for causing for causing the expected probability calculator, the model parameter updater and the likelihood calculator to recalculate the expected probabilities using updated model parameters, to update the model parameters and to recalculate the likelihood, respectively, until the likelihood meets a given criterion.

16. Apparatus according to claim 15, wherein the expected probability calculator is arranged to calculate the expected probabilities of a given item and element being associated with each of the groups by, for each group, obtaining a numerator value group by multiplying the first model parameter, the second model parameter and the third model parameter for that group, item and element, and then normalising by dividing by the sum of the numerators for each group.

17. Apparatus according to claim 15, wherein the model parameter updater is arranged to update the first model parameter for each group by multiplying the count data for each combination of information element and item of information by the corresponding expected probability, summing the resultant values for all items of information and all information elements and normalising by dividing by the sum of the count data for each element in each item.

18. Apparatus according to claim 15, wherein the model parameter updater is arranged to update the second model parameter for each group and information element combination by, for each item of information, obtaining a second model parameter numerator value by multiplying the count data for that element and item of information combination by the corresponding expected probability and summing the resultant values for all items of information, and then normalising by dividing by the sum of the second model parameter numerator values for all information elements.

19. Apparatus according to claim 15, wherein the model parameter updater is arranged to update the third model parameters for each group and item of information combination by, for each information element, obtaining a third model parameter numerator value by multiplying the count data for that information element and item of information combination by the corresponding expected probability and then summing the resultant values for all information elements, and then normalising by dividing by the sum of the third model parameter numerator values for all items of information.

20. Apparatus according to claim 15, wherein the likelihood calculator is arranged to calculate a likelihood value by summing the results of multiplying the count for each item of information and information element combination by the logarithm of the corresponding expected probability.

21. Apparatus according to claim 15, further comprising a matrix store having a first store configured to store a K element vector of first model parameters, a second store configured to store a N by K matrix of second model parameters and a third store configured to store an M by K matrix of third model parameters, where K is the number of groups, N is the number of items of information and M is the number of information elements, the initial model parameter determiner and the model parameter updater being arranged to write model parameter data to the first, second and third stores and the expected probability calculator being arranged to read model parameter data from the first, second and third stores.

22. Apparatus according to claim 15, comprising a word count store configured to store a N by X matrix of word counts where N is the number of items of information and X is the number of information elements, the model parameter updater and the likelihood calculator being arranged to read word counts from the word count store.

23. Information analysing apparatus for clustering information elements in items of information into groups of related information elements, the apparatus comprising:

a count data provider for providing count data representing the number of occurrences of elements in each item of information;

an initial model parameter determiner for determining a plurality of parameters;

a user input receiver for enabling a user to input prior information relating to the relationship between at least some of the groups and at least some of the elements;

a prior data determiner for determining from prior information input by a user using the user input receiver prior probability data;

an expected probability calculator for receiving the first, second and third model parameters and the prior probability data and for calculating, for each item of information and for each information element of that item, the expected probability of that item and that element being associated with each group using the plurality of parameters and the prior probability data determined by the prior data determiner;

a parameter updater for updating the plurality of parameters in accordance with the expected probabilities calculated by the expected probability calculator and the count data stored by the count data provider.

24. Apparatus according to claim 23, further comprising:

a likelihood calculator for calculating a likelihood on the basis of the expected probabilities and the count data stored by the count data provider; and

a controller for causing the expected probability calculator, the parameter updater and the likelihood calculator to recalculate the expected probabilities using the prior probability data and updated parameters, to update the parameters and to recalculate the likelihood, respectively, until the likelihood meets a given criterion.

25. Apparatus according to claim 23, wherein the plurality of parameters comprise first model parameters representing a probability distribution for the groups, second model parameters representing for each element the probability for each group of that element being associated with that group, and third model parameters representing for each item the probability for each group of that item being associated with that group.

26. A method of clustering information elements in items of information into groups of related information elements, the method comprising the steps of:

providing count data representing the number of occurrences of elements in each item of information;

determining a plurality of parameters;

receiving from a user prior information relating to the relationship between at least some of the groups and at least some of the elements;

determining prior probability data from prior information input by a user;

calculating, for each item of information and for each information element of that item, the expected probability of that item and that element being associated with each group using the plurality of parameters and the determined prior probability data;

updating the plurality of parameters in accordance with the calculated expected probabilities and the count data.

27. A method according to claim 26, further comprising:

calculating a likelihood on the basis of the expected probabilities and the count data; and

causing the expected probability calculating, the parameter updating and the likelihood calculating to be repeated until the likelihood meets a given criterion.

28. A method according to claim 26, wherein the plurality of parameters comprise first model parameters representing a probability distribution for the groups, second model parameters representing for each element the probability for each group of that element being associated with that group, and third model parameters representing for each item the probability for each group of that item being associated with that group.

31. A signal comprising program instructions for programming a processor to carry out a method in accordance with claim 26.

33. A storage medium comprising program instructions for programming a processor to carry out a method in accordance with claim 28.

29. Information analysing apparatus for clustering information elements in items of information into groups of related information elements, the apparatus comprising:

count data providing means for providing count data representing the number of occurrences of elements in each item of information;

initial model parameter determining means for determining a plurality of parameters;

user input means for enabling a user to input prior information relating to the relationship between at least some of the groups and at least some of the elements;

prior data determining means for determining from prior information input by a user using the user input means prior probability data;

expected probability calculating means for receiving the first, second and third model parameters and the prior probability data and for calculating, for each item of information and for each information element of that item, the expected probability of that item and that element being associated with each group using the plurality of parameters and the prior probability data determined by the prior data determining means;

parameter updating means for updating the plurality of parameters in accordance with the expected probabilities calculated by the expected probability calculating means and the count data stored by the count data providing means.