System and method for topic-based document analysis for information filtering

Abstract

An information filtering process designed to sort through large volumes of dynamically generated textual information, incrementally learning process that learns as new text documents arrive and the user grades them by providing feedback. Text-based documents either dynamically retrieved from the Web or available in a textual repository on an Intranet are represented by applying key-word weighting's after capturing the user reasoning for classifying the document as relevant or irrelevant. When a new item (document) arrives, the learning agent suggests a classification and also provides an explanation by pointing out the main features (key-phrases) of the item (document) responsible for its classification. The user looks at this and provides hints by showing a list of features (key-phrases) and are truly responsible for a particular way of classifying the document. This interaction method contributes to the learning process. The apparatus includes a feedback-based clustering scheme that models user's interest profiles, a simple neural adaptation method for leaning the cluster centers to provide personalized information filtering for information seekers.

Claims

What is claimed is:

1. A Topic Analysis System for analyzing documents to assess the relevance of documents with respect to a topic of interest to a user, said system comprising:

(a) a document evaluation subsystem for evaluating a document, said document evaluation subsystem comprises means for computing inter-relation among a plurality of key-phrases within the document, wherein the computation comprises the steps of:

computing the probability of occurrence of a key-phrase in the document depending on the occurrence of said plurality of key-phrases in the document, and

computing the probability of non-occurrence of a key-phrase in the document depending on the occurrence of said plurality of key-phrases in the document; and

(b) a clustering subsystem for representing a plurality of documents with respect to the topic associated with the user, said clustering subsystem comprising means for clustering the plurality of documents, wherein the plurality of documents includes a plurality of documents analyzed by said system and a plurality of documents analyzed by the user, and the representing comprises the steps of:

assigning a document of the plurality of documents to a hierarchically related plurality of positive clusters and plurality of negative clusters.

2. The system of claim 1, wherein the document evaluation subsystem comprises means for identifying a plurality of key-phrases of the topic present in a document, wherein said identification is based on text processing of the document.

3. The system of claim 2, wherein the document evaluation subsystem further comprises means for assigning strength value to a key-phrase of the document with respect to the topic based on the frequency of occurrence of said key-phrase in the document.

4. The system of claim 2, wherein the document evaluation subsystem further comprises means for computing plurality of probabilities of a key-phrase of the document with respect to the topic based on co-occurrence of said key-phrase with a key-phrase of the document with respect to the topic, wherein the computation is based on co-occurrence matrix of strength values of plurality of key-phrases of the topic.

5. The system of claim 2, wherein the document evaluation subsystem further comprises means for computing evaluation of the document with respect to the topic based on plurality of probabilities associated with plurality of key-phrases of the document with respect to the topic.

6. The system of claim 1, wherein said clustering subsystem comprises means for updating clusters based on evaluation of the document by said system and evaluation of the document by a user in a consistent way.

7. The system of claim 6, wherein said clustering subsystem further comprises means for updating clusters based on evaluation of the document by said system, wherein said updating comprises the means for identifying a cluster containing the document, removing the document from said cluster, and recomputing a cluster center of said cluster.

8. The system of claim 6, wherein said clustering subsystem further comprises means for updating clusters based on evaluation of the document by the user, wherein said evaluation of the document includes cluster type,

and the updating comprises the steps of:

evaluating the said cluster type with respect to evaluation of the document by said system,

and performing neural adaptation process.

9. The system of claim 6, wherein said clustering subsystem further comprises means for updating clusters based on evaluation of the document by the user, wherein the evaluation of the document includes the cluster type, and a plurality of absent key-phrases, and

the updating comprises the steps of:

forming soft-rules based on said plurality of absent key-phrases, and

forming a new cluster of type opposite to said cluster type.

10. The system of claim 6, wherein said clustering subsystem further comprises means for updating clusters based on evaluation of a document by the user, wherein the evaluation of the document includes cluster type, plurality of present key-phrases, and plurality of absent key-phrases, and

the updating comprises the steps of:

forming a new cluster of type opposite of said cluster type based on said cluster type and said system evaluation of the document,

deleting the document from cluster containing the document based on change in interest in said topic,

performing neural adaptation process based on best possible matching of said plurality of present key-phrases with a cluster of clusters associated with said topic and the user, and

forming a new cluster with said cluster type based on best possible matching of said plurality of present key-phrases with a cluster of clusters associated with the topic and the user.

11. The system of claim 6, wherein said clustering subsystem further comprises means for forming a new positive cluster of a document, wherein the formation comprises the steps of:

attaching strategic weights to strategic key-phrases of the document with respect to the topic,

calculation of threshold, identification of overlap with any negative clusters of clusters associated with the topic and the user, and

forming cluster embeddings.

12. The system of claim 6, wherein said clustering subsystem further comprises means for forming a new negative cluster of a document, wherein said formation comprises the steps of:

attaching strategic weights to strategic key-phrases of the document with respect to the topic,

calculation of threshold, identification of overlap with any positive clusters of clusters associated with the topic and the user, and

forming cluster embeddings.

13. The system of claim 6, wherein said clustering subsystem further comprises means for performing neural adaptation process of a cluster with respect to the document, wherein said performing comprises the steps of:

attaching the document to said cluster,

determining new cluster center of said cluster,

reclassifying plurality of documents based on new threshold of said cluster,

and forming plurality of new clusters based on plurality of documents that fall outside said cluster.

Description

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to online information filtering in general, and more particularly, information filtering of Web or Intranet searching results. The method employs a rich supervised learning paradigm by accepting relevance feedback to cluster the information and more particularly it employs an efficient user-interaction-based method of text representation and cluster neighbourhood analysis providing a personalized information filtering for online search applications.

2. The Background of the Invention

The problem of information overload is overwhelming almost every Web surfer or a user scouring information from an Intranet. Information seekers on the Internet go through one or the other search engine to research a topic they are interested in. It is estimated that there are over 2500 search services. Some are directory-based where the user would drill down various levels of pre-classified information to arrive at one or two documents they might be interested in. The others are keyword-driven search engines where the user specifies the keywords that drive the search process and the search engine brings up numerous results, which the user has to browse and find out where they are of any relevance. Most search services have a combination of both.

Most of these search engines offer little or no personalized features. The user would be treated as an anonymous visitor who gets inundated with a lot of irrelevant information. For instance, if the user is searching for information about the interest, Cricket, obviously all the documents that are related to the game of Cricket will be non-sense to the user. But most search engines have little or no feature to enable the user to specify and interact with the search facility such that they get the right type of information. Instead, if we could somehow recognise the user (as if we know his or her interests) under a Topic profile, it would be a lot more effective in getting accurate information seen by the user.

Another big limitation with most search engines is that the amount of time and expertise spent in researching a subject area is never remembered. There is nothing like a "stop and resume" interface. The work involved in researching and judging documents as relevant and irrelevant has to be repeated over and over each time the search engine is used to look for information in that subject area.

Publicly indexed information available to a Web user is exploding as days pass by. A typical search engine throws up hundreds of results for a user query. A very good document could be at the bottom of the pile. Not all of these hundreds of results will be useful to the user. Instead the user would like the information to be presented in a classified manner either by relevancy or by the nature of the concept the documents cover and the concepts the user likes.

DESCRIPTION OF RELATED ART

Information filtering algorithms are designed to sort through large volumes of dynamically generated information and present the user with those that are likely to satisfy his/her information requirement. With the growth of the Internet and other networked information, research in the development of information filtering algorithms has exploded in recent years. A number of ideas and algorithms have emerged.

Some of the earlier approaches have adopted what is known as the classical supervised learning paradigm. In this paradigm, when a new icon (document) arrives, the learning agent suggests a classification, the supervisor (user) would provide a classification, and the difference is used to adjust parameters of the learning algorithm. In such a paradigm, the agent's classification and the user's classification can be independent processes. The user can also give a classification even before seeing the agent's classification.

Learning itself can be either "supervised" or "unsupervised". In supervised learning networks the input and the desired output are both submitted to the network and the network has to "learn" to produce answers as close as possible to the correct answer. In an unsupervised learning network the answer for each input is omitted and the networks have to learn the correlation between input data and to organise inputs into categories from these correlations.

Supervised learning is a process that incorporates an external teacher. It employs Artificial Neural Networks that are particularly good at dealing with such ill-structured documentation handling and classification tasks that are usually characterised by a lack of pre-defined rules. The network is given a set of training patterns and the outputs are compared with desired values. The weights are modified in order to minimise the output error. Supervised algorithms rely on the principle of minimal disturbance, trying to reduce the output error with minimal disturbance to responses already learned.

The application of supervised learning paradigms will improve the performance of a search system. While an unsupervised approach may be easier to implement, since it does not require external intervention, a supervised approach could provide much better results in situations where a thesaurus or a knowledge base already exists or when a human expert can interact with the system. The objective is to employ neural techniques to add the "intelligence" needed in order to fulfil the user requirements better. Systems employing these models exhibit some of the features of the biological prototypes such as the capability to learn by example and to generalise beyond the training data.

Both supervised and unsupervised approaches rely upon a technique of document representation. It is a numerical representation of the document, which is used to produce an ordered document map.

One of the standard practices of document representation in information retrieval (IR) systems is the Vector Space information paradigm. This approach encodes the document set to generate the vectors necessary to train the document map. Each document is represented as a vector (V) of weights of keywords identified in the document. The word weight is calculated using the Term Frequency*Inverse Document Frequency (TFIDF) scheme which calculates the "interestingness" value of the word. Such formulae are used to calculate word weights and used to train the networks to create the information map.

Document representation techniques are used in the classification of textual documents by grouping (or clustering) similar concepts/terms as a category or topic, a process calling for cluster analysis. Two approaches to cluster analysis exist: the serial, statistical approach and the parallel, neural network approach.

In the serial approach, classes of similar documents are basically found by doing pairwise comparisons among all of the key elements. This clustering technique is serial in nature in that pairwise comparisons are made one at a time and the classification structure is created in a serial order. The parallel neural network approach is based on establishing multiple connections among the documents and clusters of documents allowing for independent, parallel comparisons.

A significant number of text-based classification algorithms for documents are based on supervised learning techniques such as Bayesian probability, decision trees or rule induction, linear discriminant analysis, logistic regression, and backpropagation-like neural networks

In spite of so many complex techniques researched to solve the problem of information filtering, the process of Searching (esp. on the Internet) is yet an unresolved problem.

Accordingly it is the object of our invention to make an attempt and provide a more effective and efficient neural network based supervised learning process that learns incrementally as documents arrive and the user grades them by providing feedback to the learning agent. The technique described in this invention can be called Supervised Clustering Analysis.

SUMMARY OF THE INVENTION

There is a need for personalization of the information searching either on the Web environment or in an Intranet supporting user participation in grading and ranking documents.

There is a need for automatic learning agents, which build subject profiles in which a user's feedback is captured and used to learn about the user's interests for pushing the right information and collaborating with others.

These and other needs are attained by the present invention, where whenever a new document arrives, a learning agent suggests a classification and also provides an explanation by pointing out the main key-phrases of the document responsible for its classification.

The user looks at this, gives his/her classification and then provides hints by showing a list of key-phrases that according to the user, are truly responsible for the classification suggested by the user. In this way the user's classification is truly of a feedback nature.

The algorithm behind the invention has three major parts.

Document Representation

Feedback and Learning

Classification

This information filtering process is designed to sort through large volumes of dynamically generated textual information, to incrementally learn as new text documents arrive and the user grades them by providing feedback.

Text-based documents either dynamically retrieved from the Web or available in a textual repository on an Intranet are represented by applying key-word weighting's after capturing the user reasoning for classifying the document as relevant or irrelevant.

When a new item (document) arrives, the learning agent suggests a classification and also provides an explanation by pointing out the main features (key-phrases) of the item (document) responsible for its classification. The user looks at this and provides hints by showing a list of features (key-phrases) that are truly responsible for a particular way of classifying the document.

This interaction method contributes to the learning process. The apparatus includes a feedback-based clustering scheme that models user's interest profiles, a simple neural adaptation method for learning the cluster centres to provide personalized information filtering for information seekers.

BRIEF DESCRIPTION OF THE DRAWINGS

Reference is made to the attached drawings, wherein elements having the same reference numeral designations represent like elements throughout and wherein:

FIG. 1 is a schematic diagram depicting the process of formation of a new cluster.

FIG. 2 is a schematic diagram depicting the process of feedback & learning and document classification.

DETAILED DESCRIPTION OF THE INVENTION

Before the detailed description of the invention is narrated, the list of terms used in this document are all collected and defined in the table below in the form of a glossary.

    Item          Symbol  Definition
    Document      D       A unit of writing analyzed for relevance
                          or irrelevance to the user based on the
                          information contained
    Topic         T       User's interests in a subject profiled
                          in the form of a list of key-phases of
                          relevance or irrelevance as far as the
                          subject in concerned.
    Occurrence    OS      Defines the importance with which a
    strength              key-phrase occurs in a document.
                          It is derived by multiplying the
                          Number of occurrences of
                          key-phrase * an appropriate factor
                          (Factor = Title: 1.0, Header: 0.75,
                          Text: 0.5, Footer: 0.25)
                          Factor may also be heuristically determined.
    Key-phrase    S       Minimum of (1, occurrence_strength)
    strength
    Raw Document  RDR     N-dimensional column vector of key-phrases/
    Representation         strengths Example: {Key-phrase1 0.5,
    (RDR)                 Key-phrase2 0.25, Key-phrase3 1.0,
                          Key-phrase4 0.75}
    Co-occurrence Co      Defines how a pair of key-phrases
    matrix                co-occur in documents.
    Probability   P       N x N dimensional matrix indicating
    Matrix                the probability with which the presence
                          of a key-phrase implies the presence of
                          another key-phrase.
    Expanded      EDR     N-dimensional column vector of
    Document              key-phrases. This vector representation of
    Representation         documents not only considers the strengths
                          of key-phrases but also their
                          co-occurrence probabilities.
    Cluster       C       A set of similar documents of relevance
                          or irrelevance.
    Cluster center CC      N-dimensional vector with strength values
                          of key-phrases which strongly represent
                          the cluster. This is also the mean
                          of the vector spaces (EDR's) of documents
                          representing the cluster.
    Strategic     SW      Function of key-phrase's actual weight in
    Weight                the document and the weight with which it
                          is represented in the center.
    Cluster Type  CT      Indicates whether the cluster represents
                          a collection of documents of relevance or
                          irrelevance (positive or negative)
                          to the user.
    Word_factor   W       Defined for a key-phrase. Denotes how
                          strongly it helps in classifying the
                          document. It means the because of the
                          key-phrase either the Number of positive
                          docs. that contain the phrase or the
                          Number of negative docs. that contain
                          the phrase is greater than the other
    Distance      Di      Distance of the document from the cluster
                          center CC.
    Threshold     T       Represents the distance from the centre
                          of the cluster to the Origin
    Origin        O       An imaginary document which has very
                          weak or zero strength values for all
                          key-phrases representing the cluster
                          center.

                  High Relevant                 1.0
                  Relevant                      0.5
                  Average                       0.0
                  Irrelevant                   -0.5
                  Highly Irrelevant              -1.0

    Agent's Grade = {
                      Highly Relevant if Score is greater than or equal
                                      to 0.6
                      Relevant        if Score is between 0.25 and 0.6
                      Average         if Score is between 0.0 and 0.25
                      Irrelevant      if Score is between -0.75
                                      and -0.5
                      Highly Irrelevant if Score is less than or equal
                                      to -0.75
                    }

                              Step 1
    If the user has pointed out at least one key-phrase then through text
    processing, the current document is analyzed to calculate strengths of all
    new key-phrases and the document representation. D is updated to include
    all these new key-phrases.
    Also to all centers and documents representations in the agent's database.
    zeroes are appended in the rows at the bottom corresponding to each new
    key-phrase.

                              Step 2
    If user_type is NOT same as Agent_type then skip to Step 4
    If there are key-phrases pointed out by the user then skip to Step 3
    The winning center is modified according to the neural adaptation rule:
    winning center = (1-.epsilon.) * winning center + .epsilon.*d
    where .epsilon.=0.1 is the adaptation step size.
    Note: The neural adaptation rule has been used here so as to move the
    center if each cluster towards the mean of the documents won by that
    cluster.
    In course of time, this neural adaptation achieves two things.
    Drives the center values of all key-phrases unrelated to the interest
     profile
    represented by the cluster to zero{character pullout}.
    Makes stronger center values for all key-phrases that are truly related
    to the cluster.sup..psi..
    Most neural adaptation rules slowly decrease .epsilon. towards zero as a
    function of the number of adaptation steps in order to ensure
    convergence. Here .epsilon. is kept constant so that more importance is
    given to documents that arrived more recently.
    The threshold of the winning cluster is computed.
    Skip to Step 7.

                              Step 3
    In D, the value of each uese-pointed key-phrase that is present in the
    current document is increased to 0.51 in case it is below 0.51.
    A new cluster is formed with
    .fwdarw. type = user_type,
    .fwdarw. center = the modified d and
    .fwdarw. list of document vectors = {the modified d}
    Example: Suppose the user likes documents of "Life on Mars" and a
    positive cluster has already been formed around this single key-phrase.
    Now, suppose the current document is a special "Life on Mars" article
    about "Meteorite Evidence". The article belongs to the earlier formed
    cluster with "Life on Mars" as the key-phrase, and so the agent
    grades the article as being relevant.
    Suppose the user agrees with this classification but also takes the extra
    effort to point the new key-phrase, "Meteorite Evidence". What the user
    probably means is that articles relating to "Meteorite Evidence" deserve
    special treatment. Therefore, it is a good idea to form a new cluster with
    the key-phrase, "Meteorite Evidence" present strongly. Even if the user
    does not exactly mean the need for a special treatment, the creation of the
    new cluster doesn't cause harm to future agent classifications in any way.
    Skip to Step 6.

                              Step 4
    If key-phrases pointed out by the user present in the document then
    skip to Step 5.
    Otherwise continue.
    If D is not weak (i.e. it has at least one D.sub.1 that is greater than
     0.5) then
    a new cluster is formed with
    .fwdarw. type = user_type,
    .fwdarw. center = D and
    .fwdarw. list of document vectors = {D}
    Skip to Step 6.
    Note: Suppose the user disagrees with the agent's classification of the
    current document, but feels that pointing out the special key-phrases is
    not necessary and that the key-phrases, which are already with the agent
    are sufficient.
    In such a case, this step simply forms a cluster of the user-type around
     the
    current document's representation. It is important to ensure that not all
    values of the center are weak. This is for the reason that if a center has
     all
    its values less than or equal to 0.5, then according to the distance
    measure, any document will belong to the corresponding cluster, which is
    dangerous.

                              Step 5
    In D, the value of each user-pointed key-phrase is increased to 0.75 if it
    is not already so and the value of each of the other key-phrases is
    decreased to 0.51 in case it is above 0.51.
    A new cluster is formed with
    .fwdarw. type = user_type,
    .fwdarw. center = the modified D and
    .fwdarw. list of document vectors = {the modified D}
    Skip to Step 6
    Example: As in the example give under Step 3, suppose there is already
    one positive cluster with "Life on Mars" as its main key-phrase.
    Suppose the current document is about "Galileo" and "French Explorer"
    projects to Mars, the two projects in which the user has no interest.
    Although the agent grades the article as relevant because of the
    occurrence of the key-phrase "Life on Mars", the user grades it
    irrelevant and points out the key-phrases, "Galileo" and "French
    Explorer". In this scenario, this step of the algorithm creates a
    negative cluster whose center has these two key-phrases strongly
    represented.

                              Step 6
    If the user has pointed out key-phrases, which are, absent in the
    document, then another cluster is formed with
    .fwdarw. type = user_type,
    .fwdarw. for all i, center = {
        0.75 - if i-th key-phrase is absent
        0.51 - if i-th key-phrase is present and D.sub.i > 0.51
        D.sub.i - otherwise } and
    .fwdarw. list of document vectors = { center } where center is defined
     above.
    Skip to Step 7.
    Example: Suppose the current article is about "National Basketball
    Tournament" between "New York" and "Chicago". The agent has
    graded it to be relevant and the user agrees. While giving feedback, the
    user wants to convey to the agent that a similar "National Basketball
    Tournament" article between "New York" and "Wisconsin" will be
    irrelevant. The user, therefore, points out the key-phrase, "Wisconsin",
    which is absent in the current document. In such a scenario, the above
    step forms a negative cluster, in whose center, the key-phrase,
    "Wisconsin" s highlighted.

                              Step 7
    For each new cluster formed, its threshold is computed.
    If user_type is positive then the thresholds of all negative clusters
    whithin it are recomputed so as to exclude D
    For each old cluster whose center or threshold has been modified, it is
    found out whether any document vector in its List of document vectors
    has been displaced from the cluster. Such document vectors are removed
    from the list and put into the List of displaced document vectors.
    Each document vector in the List of displaced document vectors is routed
    back to the feedback learning algorithm.

    D   Represents a document and interchangably the representation of the
        document
    Di  Distance function used to find the proximity between a document and
        a center
    CC  Cluster center
    C.sup.+  Denotes a positive center
    C.sup.-  Denotes a negative cluster or a negative pocket in a positive
     cluster
    i   Subscript value, denotes the i-th component of the associated item

    1. Apply all hard rules.sup..sym. to D
    2. If hard rules apply successfully then
          Do
              Put D in the corresponding category
              Return
        Enddo
    3. Find distance to all positive cluster centers.
    4. If a set of positives win then
        For each winning positive cluster
          Do
              Put the positive cluster in positive candidacy list L+
              Find distances to all embedded negative clusters associated
              with the winning positive cluster
              If a set of these negatives win then
              Do
                    Remove the positive cluster from L+
                    Put the winning negative in L-
              Enddo
          Enddo
    5. If L+ is non-empty then
          Do
              Find the winning positive cluster W+ for D
              Classify document as positive with W+ winning
              Return
          Enddo
          Do
              Find distances to all negative cluster centers
              If a set of negatives win then
              Do
                    Find the winning negative cluster W-
                    Classify document as negative with W- winning
                    Return
              Enddo
          Enddo
        Else
          Do
            Classify document as unclassifiable
            Return
          Enddo
    6. Apply soft rules to D
    7. If a soft rule succeeds
          Do
            Put D in the corresponding category
            Return
          Enddo

• Inventors
  Rao, Kalyan;
• Assignee
  Satyam Computer Services Limited of Mayfair Centre (Secunderabad, IN)
• Published
  Jun-15-2004
• Current US Classes:
  704/245
  707/5
• Application #
  708580
• International Classes
  G06F 017/30; G06F 007/00
• Field of Search
  707/5 707/104.1 707/102 704/245
• Examiner
  Robinson; Greta
• Agent
  Venable LLP, Voorhees; Catherine M.
• US Patent References:
  5864855
  6125362
  6189002
  6236987
  6415283
  6446061
  6460036