Document clustering

• US 7,539,653 B2
• Filed: 10/07/2005
• Issued: 05/26/2009
• Est. Priority Date: 10/07/2005
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Handley, John C.
• Primary Examiner(s): Holmes, Michael B
• Application Number:
  US11/246,336
• Publication Number:
  US 20070083368A1
• Time in Patent Office: 1,327 Days
• Field of Search: None
• US Class Current: 706/17
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 16/93 Document management systems

Abstract

Methods and systems for clustering document collections are disclosed. A system for clustering observations may include a processor and a processor-readable storage medium. The processor-readable storage medium may contain one or more programming instructions for performing a method of clustering observations. A plurality of parameter vectors and a plurality of observations may be received. A distribution may also be determined. An optimal partitioning of the observations may then be selected based on the distribution, the parameter vectors and a likelihood function.

Claims

1. A system for clustering document collection observations, the system comprising:

a processor; and

a processor-readable storage medium in communication with the processor, wherein the processor-readable storage medium contains one or more programming instructions for;

receiving a plurality of parameter vectors,

determining a distribution,

receiving a plurality of observations, wherein each observation corresponds to a document collection,

selecting an optimal partitioning of the observations based on the distribution, the parameter vectors, and a likelihood function, and

determining a cluster of observations based on the optimal partitioning.

2. The system of claim 1 wherein selecting an optimal partitioning comprises one or more programming instructions for performing the following:

for each possible partitioning of the observations, wherein each partitioning comprises one or more segments, wherein each segment comprises one or more observations;

determining a maximum likelihood parameter vector for each segment, wherein the maximum likelihood parameter vector comprises the parameter vector that maximizes the product of the distributions for each observation in the segment, and

calculating a penalized likelihood value using the likelihood function based on at least a plurality of likelihoods, wherein each likelihood comprises the distribution for each observation with respect to the maximum likelihood parameter vector for the segment containing the observation; and

selecting an optimal partitioning, wherein the optimal partitioning comprises the partitioning having the smallest penalized likelihood value.

3. The system of claim 2 wherein the processor-readable storage medium further contains one or more programming instructions for determining a cluster topic for each segment of the optimal partitioning.

4. The system of claim 1 wherein selecting an optimal partitioning comprises one or more programming instructions for performing the following:

for each possible segment of one or more observations, determining a maximum log likelihood value for the segment, wherein the maximum log likelihood value comprises the largest sum of the logarithms of a distribution for each observation in the segment;

for each possible number of segments, wherein the possible number of segments may range from one to the number of observations, inclusive,

determining an optimal sub-partitioning from one or more partitionings having the number of segments, wherein the optimal sub-partitioning comprises the partitioning having a largest value for a sum of one or more log likelihood values, wherein each log likelihood value comprises the logarithm of the distribution of an observation with respect to a parameter vector for the segment containing the observation, and

calculating a penalized likelihood value using the likelihood function for the optimal sub-partitioning having the number of segments; and

selecting an optimal partitioning, wherein the optimal partitioning comprises the optimal sub-partitioning having the smallest penalized likelihood value.

5. The system of claim 4 wherein the processor-readable storage medium further contains one or more programming instructions for determining a cluster topic for each segment of the optimal partitioning.

6. The system of claim 1 wherein the likelihood function comprises the Akaike'"'"'s Information Criterion.

7. The system of claim 1 wherein the plurality of observations are time-ordered.

8. The system of claim 1 wherein the distribution comprises one or more of the following:

a multinomial distribution; and

a Bernoulli distribution.

9. A method of clustering observations, the method comprising:

receiving a plurality of parameter vectors;

determining a distribution;

receiving a plurality of observations, wherein each observation corresponds to a customer service log, wherein the plurality of observations are time-ordered;

selecting, by a processor, an optimal partitioning of the observations based on the distribution, the parameter vectors, and a likelihood function; and

determining a cluster of observations based on the optimal partitioning.

10. The method of claim 9 wherein selecting an optimal partitioning comprises:

for each possible partitioning of the observations, wherein each partitioning comprises one or more segments, wherein each segment comprises one or more observations;

determining a maximum likelihood parameter vector for each segment, wherein the maximum likelihood parameter vector comprises the parameter vector that maximizes the product of the distributions for each observation in the segment, and

calculating a penalized likelihood value using the likelihood function based on at least a plurality of likelihoods, wherein each likelihood comprises the distribution for each observation with respect to the maximum likelihood parameter vector for the segment containing the observation; and

selecting an optimal partitioning, wherein the optimal partitioning comprises the partitioning having the smallest penalized likelihood value.

11. The method of claim 10, further comprising:

determining a cluster topic for each segment of the optimal partitioning.

12. The method of claim 9 wherein selecting an optimal partitioning comprises:

for each possible segment of one or more observations, determining a maximum log likelihood value for the segment, wherein the maximum log likelihood value comprises the largest sum of the logarithms of a distribution for each observation in the segment;

for each possible number of segments, wherein the possible number of segments may range from one to the number of observations, inclusive,

determining an optimal sub-partitioning from one or more partitionings having the number of segments, wherein the optimal sub-partitioning comprises the partitioning having a largest value for a sum of one or more log likelihood values, wherein each log likelihood value comprises the logarithm of the distribution of an observation with respect to a parameter vector for the segment containing the observation, and

calculating a penalized likelihood value using the likelihood function for the optimal sub-partitioning having the number of segments; and

selecting an optimal partitioning, wherein the optimal partitioning comprises the optimal sub-partitioning having the smallest penalized likelihood value.

13. The method of claim 12, further comprising:

determining a cluster topic for each segment of the optimal partitioning.

14. The method of claim 9 wherein the likelihood function value comprises a value determined using the Akaike'"'"'s Information Criterion.

15. The method of claim 9 wherein the distribution comprises one or more of the following:

a multinomial distribution; and

a Bernoulli distribution.

16. The method of claim 9 wherein the plurality of parameter vectors are received from a processor-readable carrier.

17. The method of claim 9 wherein the plurality of observations are received from a processor-readable carrier.

18. The method of claim 9 wherein the distribution is determined using at least one processor.