## 3 A Review of Conceptual Clustering Algorithms
The utility of clustering is considered a \(CU\) function that determines the similarity of objects within one cluster and their difference in relation to objects from other clusters:  
\[ \begin{split} CU=\frac{\Sigma_{C_{k\in C}}\,P(C_{k})\big{[}\sum \
olimits_{j}\sum\
olimits_{j}P\big{(}A_{i}=V_{ij}\big{|}\,C_{k}\big{)}^{2}- \sum\
olimits_{j}\sum\
olimits_{j}P\big{(}A_{i}=V_{ij}\big{)}^{2}\big{]}}{ \big{|}\big{|}\big{|}\big{|}},\\ P\big{(}A_{i}=V_{ij}\big{)}=\frac{\big{|}\big{\{}Q_{i}\big{|}Q_{i} \big{|}\in C,\,A_{i}=V_{ij}\big{\}}\big{|}}{\big{|}\big{\{}Q_{i}|Q_{i}\in C\} \big{|}},\\ P\big{(}A_{i}=V_{ij}\big{|}C_{k}\big{)}=\frac{\big{|}\big{\{}Q_{i} \big{|}Q_{i}\in C_{k},A_{i}=V_{ij}\big{\}}\big{|}}{\big{|}\big{\{}Q_{i}|Q_{i} \in C_{k}\}\big{|}},\end{split}  \tag{4}\]  
where \(P(C_{k})\) is the probability of an object to belong to a given class, \(P(A_{i}=V_{ij}\,|\,C_{k})\) is the probability of an object having the value \(V_{ij}\) for the attribute \(A_{i}\) provided that it belongs to the class \(C_{k}\), and \(\{O_{k}\}\) is the set of objects belonging to this class. When executing the algorithm, a classification tree is iteratively built. Each node in the tree represents a class. A tree slice represents a possible partition into non-overlapping classes. The utility function \(CU\) applies specifically to the slice. COBWEB (Algorithm 2) adds objects element by element to the classification tree, wherein each vertex is a probabilistic concept that represents a class. Thus, the algorithm descends the tree along the corresponding path, updates the probabilistic characteristics of the classes on the path, and performs one of the following operations at each level:  
* Assigning an object to an existing class;
* Creating a new class;
* Combining two classes into one;
* Splitting one class into two. ```
Input: Node root, Instance to insert record Output: Classification tree. If Node is a leaf then  Create two children of Node \(L_{1}\) and \(L_{2}\). Set the probabilities of \(L_{1}\) to those of Node. Set the probabilities of \(L_{2}\) to those of Instance. Add Instance to Node, updating Node's probabilities. Else  Add Instance to Node, updating Node's probabilities. For each child \(C\) of Node  Compute the category utility of clustering achieved by placing Instance in \(C\). end for \(S1\leftarrow\) the score for the best categorization (Instance is placed in \(C_{1}\)). \(S2\leftarrow\) the score for the second best categorization (Instance is placed in \(C_{2}\)). \(S3\leftarrow\) the score for placing Instance in a new category. \(S4\leftarrow\) the score for merging \(C_{1}\) and \(C_{2}\) into one category. \(S5\leftarrow\) the score for splitting \(C_{1}\) (replacing it with its child categories). end if If \(S_{1}\) is the best score then call COBWEB (\(C_{1}\), Instance). If \(S_{3}\) is the best score then set the new category's probabilities to those of Instance. If \(S_{4}\) is the best score then call COBWEB (\(C_{m}\), Instance), where \(C_{m}\) is the result of merging \(C_{1}\) and \(C_{2}\). If \(S_{5}\) is the best score then split \(C_{1}\) and call COBWEB (Node, Instance). Return Classification tree. ```  
**Algorithm 2** Conceptual clustering algorithm COBWEB  
The time complexity of the COBWEB algorithm is \(O\big{(}B^{2}\cdot log_{B}(n)\cdot AV\big{)}\), where \(B\) is the average branching factor of the tree, \(n\) is the number of instances being categorized, \(A\) is the average number of attributes per instance, and \(V\) is the average number of values per attribute [33]. The space complexity of the COBWEB algorithm is \(O(n\cdot A\cdot V\cdot L)\), where \(L\) is the number of probabilistic concepts. The formal concept analysis approach is an alternative method of conceptual clustering [23].