Hierarchical clustering with real-time updating

The present invention relates to a document processing technique. The present invention will be described with reference to exemplary embodiments using probabilistic hierarchical clustering that represent a document in the form of bag-of-words. The present invention can be similarly applied to stochastic non-hierarchical clustering and other types of clustering.

A typical clustering system processes a set of documents with a training algorithm that classifies the documents into various classes based on the similarity and dissimilarity of the documents. For example, in one approach, a document describes the number of important words or words excluding certain stopwords (eg, "the", "an", "and", etc.) that are frequent and generally of low semantic importance. It is expressed in the word set format to be saved. Document similarity and dissimilarity are measured in terms of word count, ratio or frequency, and training divides the document into various classes based on such similarity and dissimilarity. Training also generates probabilistic model parameters that represent the number, proportion, or frequency of words that characterize the class. For example, the ratio of the number of words in a document of a class to the total number of words in a document of a class gives a parameter that models the probability of a word or the frequency of a word. Classes may be organized to form a class hierarchy as needed. In the class hierarchy, documents are associated with leaf classes, and ancestral classes identify or associate semantically or logically related grouping of leaf classes. At the end of the training, a clustering system can be leveraged to provide an easy-to-use and intuitive interface for user access to clustered documents.

<p> However, the problem is that this classification system generated in the first cluster training is generally static. Stochastic modeling parameters are calculated during initial training based on the number of words in the document and class. Stochastic modeling parameters calculated during training lose accuracy when documents are moved from one class to another in a clustering system, or when classes are split or existing classes are merged.</p><p> The clustering system can also be retrained after each update (for example, after moving each document or class, after splitting or merging each class, etc.) to maintain the latest stochastic modeling parameters. However, large clustering systems can contain tens of thousands to hundreds of thousands of documents, each containing thousands to tens of thousands of words or more. Therefore, retraining a clustering system is generally a slow idea. It takes minutes or more to retrain thousands of documents, each containing thousands or tens of thousands of words, on a document basis. Such a long time frame has nothing to do with performing real-time updates of the class hierarchy. Also, the effects of such retraining are generally not localized for moved documents or classes that have already been moved, merged, split or otherwise updated. Not only that, retraining the clustering system to reflect updates in one area of the class hierarchy can result in unintended results, for example, in another area far from the updated area.</p>

<p> According to one aspect set forth herein, there is provided a method of updating a stochastic clustering system, which is at least partially defined by stochastic model parameters indicating the number, ratio or frequency of words that characterize the class of clustering system. .. The association of one or more documents is changed from one or more source classes to one or more destination classes. The probabilistic model parameters that characterize the affected classes of the modified association are updated locally, and the probabilistic model parameters that characterize the classes that are not affected by the modified association are not updated.</p>

The clustering system will be described with reference to FIG. A clustering system is a stochastic clustering system that organizes a set of documents 10 to generate a class hierarchy 12. In some embodiments, a flat set of classes is generated. Class hierarchy 12 includes document / leaf class association 14 indicating which document 10 was associated with which leaf class in class hierarchy 12 (although the technology uses the term "class", "cluster" or "cluster" Substantially synonymous terms such as "category" are also used. Here, the term "class" should be broadly interpreted as including the term "cluster" or "category"). In some embodiments, document / leaf class related 14 is annotated to the document. It is appropriate that each document in the set of documents 10 be displayed in word set format. The word set format does not use the position of words in the document. Instead, the frequency of words that display a document by the number of important words or words, excluding certain stop words that are more frequent and generally less semantically important (eg, "the", "an", "and", etc.). Vectors and similar formats are used. The particular format used varies. For example, the word set representation has, as required, the total number of words in the document, or the number of words normalized by the total number of non-stop words in the document.

The class hierarchy 12 further includes a set of 16 probabilistic model parameters indicating the number, ratio or frequency of words that characterize the class. The illustrated clustering system utilizes a stochastic model. Class hierarchy 12 contains leaf classes that are directly associated with the document. If desired, the hierarchy does not contain the document itself, but further contains one or more ancestor classes that are the ancestors of the leaf document that contains the document. Class hierarchy 12 contains two or more levels of ancestor classes as needed. In one exemplary embodiment, the probabilistic modeling parameter 16 that characterizes the class is, for each class C, the class probability P (C), which indicates the ratio of the number of words in the document in class C to the total number of words in the set of documents 10. Document probability P (d | C) indicating the ratio of the number of words in document d of class C to the total number of words in class C (for hard partitioning, P (d | C) = if document d is not associated with class C If it is 0 and document d is associated with class C (d | C) indicates the effect of document d on class C), then the ratio of the number of words in class C to the total number of words in class C. Includes the indicated word probabilities P (w | C) and. Hard partitioning is utilized in this exemplary embodiment. It is also considered to utilize soft partitioning, where a given document may have fragmentary associations with one or more classes.

The illustrated stochastic model parameters P (C), P (d | C), and P (w | C) are examples only and are not limited. Other suitable stochastic model parameters may be defined in place of or in addition to these. In some embodiments, clustering may be performed by a non-stochastic clustering technique such as k-means method, latent semantic indexing, or hierarchical integrated method.

Class hierarchy 12 is usually generated first by a good training approach. In some embodiments, maximum likelihood approaches such as expectation-maximization (EM) and gradient descent. approach) is used to train a stochastic clustering model. Training generates probabilistic modeling parameters 16 based on the document / leaf class association 14 acquired during the training phase. The leaf class of the hierarchy is directly associated with the document. Intermediate classes that leaf classes depend on directly or indirectly are also, for example, exemplary probabilities P (c), P (d | c), P (w | c) (lowercase "c" represents non-leaf class). Has related stochastic modeling parameters such as. A good approach for non-leaf classes is P (c) = 0 for all non-leaf classes c. This indicates that the non-leaf class c does not directly contain any documents. P (d | c) and P (w | c) are weighted averages of the corresponding parameters of their children or grandchildren. That is, the following equation holds.

<maths num="1"><img file="JP5079367B2_D0001.tif" /></maths>

When the clustering system is trained, the user can use the user interface 20 to communicate with the processor 22 running the cluster navigator 24 to navigate the clustering system. In some embodiments, the user interface is a window showing a tree view of a class hierarchy in which various branches are extensible or foldable to focus on the area of interest, for displaying selected documents. It is a graphical user interface (GUI) that provides a document window and so on. Various windows can be opened and closed as needed by appropriate menu options, mouse selection, or the user input mechanism of the graphical user interface. The clustering system is static and the class hierarchy 12 is unchanged if the user simply browses the document, retrieves the document, or performs other read-only cluster system navigation operations.

However, the user may decide to change the association of one or more documents from one or more source classes to one or more destination classes. In one example of related changes, the user chooses to move one document from one class to another (see, for example, Figure 2). In another example of related changes, the user moves a leaf class from one ancestor class to another and moves the document associated with the moved leaf class during this process (see, eg, Figure 3). ). In another example of related changes, the user forms a merged leaf class by merging two or more leaf classes and moves the document associated with the original leaf class to the merged leaf class during this process. (See, for example, Figure 4). In another example of related changes, the user merges two or more leaf classes by inserting a new ancestor class, making them the direct ancestors of the two or more leaf classes that are merged, and during this process Move the document indirectly from the new ancestor class (see, for example, Figure 5). In another example of related changes, the user splits an existing leaf class into two or more split leaf classes and replaces the existing leaf class. During this process, move the document associated with the existing leaf class to the split leaf class (see, eg, Figure 6). In another example of related changes, the user performs a split by moving a document of an existing leaf class created as a direct descendant of an existing leaf class to two or more split leaf classes, and during this process. Moves the document associated with an existing leaf class to a new split leaf class (see, for example, Figure 7).

Each of these exemplary association changes affects the class hierarchy 12, which includes the stochastic modeling parameter 16. If a new class is not created (eg, the move operation in Figures 2 and 3), the effect is a change in the value of certain stochastic modeling parameters 16. When a new or different class is created (eg, merge and split operations in Figures 4-7), the value of the current stochastic modeling parameter 16 changes and new probabilistic modeling parameters are created additionally. And / or deleted. Note that the clustering system in Figure 1 is affected by the modified association without updating the probabilistic model parameters that characterize the class that is not affected by the modified association, as well as executing or including the components of the cluster navigator 24. It is advantageous in that it includes a processor 22 that executes or includes a component that locally updates the stochastic model parameters that characterize the class. As described herein, during move and merge operations, the algebraic updater 30 of the stochastic modeling parameters performed by the processor 22 algebraically and locally performs the stochastic model parameters 12 without cluster training. Can be updated. During a split operation, the clustering builder 32 executed by processor 22 can be used to split the documents in the split leaf class. Clustering is only performed on documents associated with existing classes to be split. The clustering builder 32 may utilize a maximum likelihood stochastic clustering algorithm such as an expected value maximization (EM) algorithm, a gradient descent algorithm, etc. to perform limited cluster training. Typically, the clustering builder 32 is the same algorithm or component used to perform the initial cluster training on the complete set of documents 10 for the creation of a clustering system. In addition, the subsequent sp

The advantage of performing local updates with components 30 and 32 is that these updates can be performed in real time, for example in minutes or less, more preferably seconds or less, in a processing time acceptable to the user. is there. The algebraic update 30 is fast because it performs a local update without clustering (or reclustering) the documents. Also, since the number of documents in an existing cluster to be split is usually a small subset of the total number of documents 10 organized by the clustering system, applying the clustering builder 32 during a split operation is generally faster. For example, when using the clustering builder 32 during a split operation, the execution time for an existing cluster containing tens, hundreds, or thousands of documents is typically seconds or less. In contrast, when using Clustering Builder 32 for complete retraining of a cluster system, it is usually necessary to cluster tens of thousands or more of the set of 10 documents, so the processing time is substantial. It gets longer. In general, it is not practical to perform such a complete retraining in real time.

With reference to Fig. 1, the clustering system that performs real-time update is explained as a whole with reference to Fig. 2 to Fig. 8. In the following, processing such as document movement, class movement, and related changes including some types of merging, and split operations will be described in detail with reference to FIGS. 2 to 8. It should be noted that these various operations can be combined in various ways to perform complex real-time updates of the clustering system. For example, you can move a class to another part of the hierarchy, split it, and then move one or more documents from one newly created split class to another.

<img file="JP5079367B2_D0002.tif" />

Therefore, the algebraic updater 30 of the stochastic modeling parameters of the processor 22 performs a local update of the stochastic modeling parameters. Local updates affect the source and destination leaf classes "L1" and "LN", as well as the source leaf class "L1" and the ancestor class common to the destination leaf class "LN". It also affects the intermediate class "H1" between "L1" and the common parent class "root". In general, the probabilistic modeling parameter algebraic updater 30 updates the probabilistic modeling parameters that characterize the source and destination leaf classes, as well as being in a hierarchy between the source leaf class and the common parent class (one). Or update any intermediate ancestor class (or more), or a class (s) in the hierarchy between the destination leaf class and the common parent class. The "common parent class" refers to a common parent class located at the bottom of the hierarchy, that is, a common parent class closest to the source and destination leaf classes in the hierarchy. The common parent class itself may have a common parent class for both the source leaf class and the destination leaf class.

It is appropriate to perform algebraic updates related to mobile operations as follows. Source leaf class C_s, Destination or target leaf class C_tIt is represented by. Also, D is the document to be moved, d is the source class C_sOr target class C_tRepresents any other document in. It is appropriate to update in four operations. That is, source class C_sRemove document D from source class C_sOperation to update probabilistic modeling parameters for, source class C_sAnd source class C_sAnd target class C_tAn operation that propagates to any intermediate class in the hierarchy between the common parent class and the destination of document D, ie target cluster C._tAdd to target class C_tOperation to update probabilistic modeling parameters for, and target class C for the update_tAnd source class C_sAnd target class C_tAn operation that propagates to any intermediate class in the hierarchy with a common parent class. Local class, i.e. C_s, C_t, And only the probabilistic modeling parameters for any intermediate class between the source or target class and the common parent class are changed.

<img file="JP5079367B2_D0003.tif" />

<maths num="2"><img file="JP5079367B2_D0004.tif" /></maths>

In equation (6), N_wDIs the number of words w in document D. Equations (3) to (6) are source class C_sAlgebraically reflects the effects of removing Document D from. Also, source class C_sAnd source class C_sAnd target class C_tIf there are intermediate ancestor classes in the hierarchy with the common parent class, the stochastic modeling parameters that characterize these classes are algebraically adjusted by the following equation. C^pIs source class C_sAnd target class C_tRepresents a common parent class with. Then, the following iterative processing is performed.

<maths num="3"><img file="JP5079367B2_D0005.tif" /></maths>

Equations (7) to (10) are destinations, that is, target class C._tAlgebraically reflects the impact of the addition of Document D to. In addition, target class C_tAnd source class C_sAnd target class C_tCommon to parent class C^pIf there are intermediate ancestor classes in the hierarchy between and, the stochastic modeling parameters that characterize these classes are algebraically adjusted as follows:

<maths num="4"><img file="JP5079367B2_D0006.tif" /></maths>

<img file="JP5079367B2_D0007.tif" />

<img file="JP5079367B2_D0008.tif" />

<maths num="5"><img file="JP5079367B2_D0009.tif" /></maths>

<img file="JP5079367B2_D0010.tif" />

<maths num="6"><img file="JP5079367B2_D0011.tif" /></maths>

<img file="JP5079367B2_D0012.tif" />

<maths num="7"><img file="JP5079367B2_D0013.tif" /></maths>

<img file="JP5079367B2_D0014.tif" />

<maths num="8"><img file="JP5079367B2_D0015.tif" /></maths>

The flat merge operation will be described with reference to FIG. Leaf classes "L1" and "L2" with a common direct ancestor class "root" are merged to create a merged leaf class "L1 &amp; 2" to replace leaf classes "L1" and "L2". That is, the document association of the leaf classes "L1" and "L2" is changed to the newly created merged class "L1 &amp; 2" in place of the classes "L1" and "L2" in the class hierarchy. The class hierarchy in Figure 4 is a flat hierarchy, but more complex hierarchies can be used. For example, the class to be merged may have a common ancestor class between the root class and the leaf class to be merged, rather than being a direct descendant of the root class. For such a merge operation to make sense, the common ancestor class must have at least one additional offspring leaf class not included in the merge operation.

<img file="JP5079367B2_D0016.tif" />

<maths num="9"><img file="JP5079367B2_D0017.tif" /></maths>

<img file="JP5079367B2_D0018.tif" />

<img file="JP5079367B2_D0019.tif" />

<maths num="10"><img file="JP5079367B2_D0020.tif" /></maths>

<img file="JP5079367B2_D0021.tif" />

The flat split operation will be described with reference to FIG. The existing leaf class "L2" is split into two or more split leaf classes (two split leaf classes "L2A and L2B" in Figure 6) that replace the existing leaf class in the class hierarchy. Before the split, the existing leaf class "L2" has a class "H1" as a direct ancestor class, and after the split, the replaced split leaf classes "L2A and L2B" have a direct common ancestor class "H1". In the example of FIG. 6, the common direct ancestor class "H1" is an intermediate class, but in other embodiments the class hierarchy may be flat and the direct ancestor class and the replacement split leaf class of the existing leaf class It may be a root class.

Cluster training is performed to split the document associated with an existing leaf class of two or more replacement split leaf classes. However, in order to promote high-speed processing that contributes to real-time operation, the clustering builder 32 of processor 22 is used only for processing documents associated with the existing leaf class (existing leaf class L2 in FIG. 6). .. Local stochastic model parameters for characterizing split leaf classes (exemplary split leaf classes "L2A" and "L2B" shown in Figure 6) for documents associated with existing leaf classes with limited cluster training. Is generated. Limited and localized cluster training is a retraining of the entire clustering system, as the number of documents associated with one of the existing classes to be split is typically significantly less than the total number of documents organized by the clustering system. It can be done much faster than. Also, the effect is local because limited cluster training is done locally on existing leaf class documents.

<img file="JP5079367B2_D0022.tif" />

<maths num="11"><img file="JP5079367B2_D0023.tif" /></maths>

The above formula is in Document D_CEvery document in the set of split leaf class C_nIndicates that it is associated with one of. On the other hand, in the context of a global clustering system, the following equation holds.<maths num="12"><img file="JP5079367B2_D0024.tif" /></maths>

<img file="JP5079367B2_D0025.tif" />

<maths num="13"><img file="JP5079367B2_D0026.tif" /></maths>

Equations (26) and (27) are identical because the values for these stochastic modeling parameters are the same in the local context as in the case of the global clustering system context. Once the global stochastic modeling parameters have been determined, the existing leaf class (leaf class in the example in Figure 6), with the existing leaf class documentation associated with the various split leaf classes according to the results of local cluster training. The flat split is completed by replacing "L2") with a split leaf class (leaf classes "L2A" and "L2B" in the example of FIG. 6).

In a sense, flat merge is a reverse operation to flat split. If you split an existing leaf class and merge the resulting split leaf classes, you will get the same as the original existing leaf class. This reverse may not be the case. If you merge several leaf classes and split the merged class again, different leaf classes will be generated. That is, for example, merging 5 leaf classes and then splitting the merged leaf class into 5 leaf classes does not return to the same as the original 5 leaf classes.

<img file="JP5079367B2_D0027.tif" />

<maths num="14"><img file="JP5079367B2_D0028.tif" /></maths>

P (w | C) and P (d | C) do not change. The existing class C is retained and acts as a direct ancestor class of the added split leaf cluster, and the documents associated with the existing class C are associated with the various added split leaf clusters according to local cluster training. Be done.

A flat split is performed, and further flat merging of the split leaf classes is performed to obtain the original leaf class. In contrast, hierarchical merging is not the reverse operation of a hierarchical split. This is because both hierarchical merges and hierarchical splits create additional hierarchies.

In the exemplary flat split operation and hierarchical split operation described above, it was assumed that the user had no preference for how to perform the split. That is, the user relies entirely on the Clustering Builder 32 procedure to determine which documents are grouped into which split leaf class. However, in some cases, the user may want to keep a certain subset of documents together during a split operation. This is especially true for constrained splits. Therefore, the document should be a word frequency vector, or the number of important words or words excluding certain stop words that are more frequent and generally less semantically important (eg, "the", "an", "and", etc.). Describes techniques for performing (flat or hierarchical) splits in a clustering system that displays a document in wordset format, expressed in other formats for storage. The technique for keeping a selected subset of documents together during a split applies to almost any split operation context that utilizes a clustering technique that acts on the document in wordset format to distribute the documents in the split class. it can. This technique is not limited to stochastic clustering systems. Examples of symbols used in the present specification are shown below. C is the class to be split, L is the number of split classes generated by the split (split leaf clusters may replace class C in the case of flat splits, and may be subordinate to class C in the case of hierarchical splits. ). When n&gt; 1, G = [d₁, ... d_n] Represents a subset of n documents to be grouped.

<img file="JP5079367B2_D0029.tif" />

<tables num="1"><img file="JP5079367B2_D0030.tif" /></tables>

<img file="JP5079367B2_D0031.tif" />

<maths num="15"><img file="JP5079367B2_D0032.tif" /></maths> (29)

<img file="JP5079367B2_D0033.tif" />

<img file="JP5079367B2_D0034.tif" />

<img file="JP5079367B2_D0035.tif" />

<maths num="16"><img file="JP5079367B2_D0036.tif" /></maths> (30)

<img file="JP5079367B2_D0037.tif" />

With reference to FIG. 1 again, it is appropriate that the document move, leaf class move, leaf class merge, and leaf class split operations described herein are performed in real time with user input supplied from user interface 20. By "real time" is meant that the operation can be performed in a time frame acceptable to the user interacting with the user interface 20. Such a time frame is usually preferably a few minutes or less, more preferably a few seconds or less. According to embodiments, the user interface 20 is a graphical user interface (GUI). Class hierarchy 12 is appropriately represented in a tree or tree-like structure, which contains branches that can be extended or folded as needed. The user can select classes, documents, etc. using a mouse or other pointing device in the structure. For example, in one approach, the user performs a move operation on a document or leaf class by right-clicking on the document or leaf class and displaying a context-sensitive menu containing options for the move operation. When the user selects a move operation from the context sensitive menu, a dialog box about the destination class appears. When the user selects a destination class, for example by clicking with the mouse pointer, the document or leaf class is moved as described herein, displaying an updated tree view of class hierarchy 12. The GUI preferably includes appropriate checks for the operation, for example displaying the move operation selection option in the context sensitive menu only when the user right-clicks on the document or leaf class. In some embodiments, the user can &lt;CONTROL&gt; or &lt;ALT&gt; while left-clicking on the document, for example.

To perform a merge operation, the user, for example, left-clicks on the document and presses the &lt;CONTROL&gt; or &lt;ALT&gt; key to appropriately select multiple leaf classes to be merged, and then the selected group. Right-click on it to bring up the context sensitive menu. If the GUI determines that the selection is a leaf class with all common direct ancestor classes (eg root classes), the GUI includes merge options in the context sensitive menu. When the user selects the merge option, the GUI asks whether it intends to do a flat merge or a hierarchical merge (or include separate options for "flat merge" and "hierarchical merge" in the context sensitive menu. May be). The selected leaf classes are then merged by a selected flat merge or hierarchical merge, as described herein, and an updated tree view of class hierarchy 12 is displayed.

To perform a split operation, the user selects the leaf class to be split and right-clicks to display the context sensitive menu. If the GUI determines that a leaf class has been selected, the GUI will include a split option in the context sensitive menu. When the user selects the split option from the context-sensitive menu, the GUI responds by asking whether they intend to do a flat split or a hierarchical split (or, in the context-sensitive menu, "flat split" and "hierarchical split". May be included as an option separately). In addition, the GUI asks for a value that indicates the number of split classes to create. It is preferable to include a check in the GUI to ensure that the number of split classes given by the user is greater than 1 and less than the total number of documents in the class to be split. The selected leaf class is then split in the manner described herein to display an updated tree view of class hierarchy 12.

Document G^(p)To perform a constrained split with one or more subsets of, for example, the user double-clicks to open the leaf class and clicks on the target document contained in the subset of documents &lt;CONTROL&gt; Select a subset by pressing, &lt;ALT&gt;, or another grouping key. By repeating this process as needed, as described herein, two or more subsets of the documents to be combined can be defined. The user then selects the split option as described above, the GUI cancels the selected group and puts them together using the replaced temporary document. If necessary, before splitting, the GUI asks the user whether to cluster the groups into separate split leaf classes (ie, whether clustering should adopt an "exclusive group constraint"). Perform a constrained split according to the user's response.

The above GUI operation is an example using a mouse operation that is familiar to users of a general GUI system such as a Microsoft Windows (registered trademark) computer operating system. Other GUI executions may be utilized to facilitate the execution of real-time document movements, leaf class movements, class merges, and class split operations, as described herein. It also considers that these operations can be performed in real time or as queued processes for subsequent processing, using non-graphical interfaces such as batch processing scripts and command line user interfaces. ..

The class move, split, and merge operations have been described for moving, splitting, and merging leaf clusters. Note that these operations can be extended to move, split, and merge larger branches in the class hierarchy.

<img file="JP5079367B2_D0038.tif" />

<maths num="17"><img file="JP5079367B2_D0039.tif" /></maths>

<img file="JP5079367B2_D0040.tif" />

<maths num="18"><img file="JP5079367B2_D0041.tif" /></maths>

<img file="JP5079367B2_D0042.tif" />

<img file="JP5079367B2_D0043.tif" />

<maths num="19"><img file="JP5079367B2_D0044.tif" /></maths>

The algebraic updater 30 of the stochastic modeling parameters calculates the parameters for the merged class c in a manner similar to equations (17) to (19) as follows.<maths num="20"><img file="JP5079367B2_D0045.tif" /></maths>

The result of the equation is 0 because the non-leaf class itself does not contain any documentation, so P (c)_n) = 0. The word probabilities of the merged class c are given by the following equation.

<maths num="21"><img file="JP5079367B2_D0046.tif" /></maths>

<img file="JP5079367B2_D0047.tif" />

The hierarchical merging of leaf classes was explained with reference to Fig. 5 and equations (20) to (22). More generally, the same direct ancestor (ie, parent) class C, whether leaf class or non-leaf class.^PAny set of classes with can be merged.

Referring to FIG. 8, for example, a non-leaf class H2 having a direct ancestor class H1 and having progeny leaf classes L2 and L3 is a leaf class having a direct ancestor class H1. It is hierarchically merged with "L4". As shown in Figure 8, hierarchical merging involves inserting the newly merged non-leaf class "c" between the direct ancestor class "H1" and the merged classes "H2" and "L4". It is done in.

<img file="JP5079367B2_D0048.tif" />

<maths num="22"><img file="JP5079367B2_D0049.tif" /></maths>

<maths num="23"><img file="JP5079367B2_D0050.tif" /></maths>

The algebraic updater 30 of the stochastic modeling parameters calculates the parameters for the inserted merged class c in a manner similar to equations (20) to (22) as follows.

<maths num="24"><img file="JP5079367B2_D0051.tif" /></maths>(The above expression indicates that the inserted merged class c is a non-leaf class that does not itself contain any documentation).

<maths num="25"><img file="JP5079367B2_D0052.tif" /></maths>

In the formula, N_wcIs the total number of occurrences of the word w in the document associated with the leaf class that depends on the merged class c. Parent C with common class c to complete the merge^pClass c inserted and merged into the hierarchical structure below_nIs configured to be subordinate to the inserted class c.

<figref num="1">It is the schematic of the clustering system including the real-time hierarchy update.</figref><figref num="2">Schematic of an update that moves a document from a source class to a destination class.</figref><figref num="3">It is a schematic diagram of an update that moves a leaf class from a source ancestor class to a destination ancestor class.</figref><figref num="4">Schematic of an update that merges two leaf classes with a common direct ancestor class.</figref><figref num="5">Schematic of an update that merges two leaf classes with a common direct ancestor class by creating a common direct ancestor class.</figref><figref num="6">It is a schematic diagram of an update that splits an existing leaf class into two split leaf classes that replace the existing leaf class.</figref><figref num="7">Schematic of an update that splits an existing leaf class into two split leaf classes by moving the existing leaf class documentation to two new split leaf classes that have the existing leaf class as a common direct ancestor class.</figref><figref num="8">It is a schematic diagram of an update that merges a non-leaf class and a leaf class that have a common direct ancestor class by creating a common direct ancestor class.</figref>