## 4 Performance Estimation
### Approach  
In the previous version of our algorithm (we will refer to it as to PHOCS-1) we made estimation in the following way. We used \(F1\)-measure as a performance measure and assumed that the \(F1\)-measure becomes smaller layer by layer (as the hierarchy is growing), that is, the \(F1\)-measure on layer \(k\) is larger than on layer \(k+1\). We estimated it at \(k+1\) level as \(F1_{k+1}^{*}=\prod_{i=1}^{k}F1_{i}\), where \(i\) is the layer number. This  
Figure 5: Example: filling in the table. estimation is rather rough and it is possible to make it finer. We propose to use absolute values of errors and the structure of nodes as well as more information about clusters--their size and performance values. We will denote:  
* cluster size;
* the number of documents in the cluster;
* the number of child clusters;
* the average number of labels for documents in the cluster;
* the number of possible further partitions for the cluster;
* \({}^{*}\) index is used for estimated numbers and measures;
* \({}^{**max}\) index is used for the best estimation for the cluster (among all possible partitions of this cluster);
* \({}^{*result}\) index is used for estimation of the whole partition (split);
* \({}^{q}\) index denotes the number of partitions for a particular cluster;
* \({}^{T}\) index is used for the values of the performance measure in the table that we fill in (like in Figure 5). Each record in the table corresponds to a specific number of child clusters \(K\). Our goal is to estimate the absolute values of true positives (\(TP^{*}\)), false negatives (\(FN^{*}\)) and false positives (\(FP^{*}\)). Then we have to calculate relative performance measures that can be used for optimizing the hierarchy, such as \(F1\)-measure (\(F1^{*}\)), Precision (\(P^{*}\)) or Recall (\(R^{*}\)). The example of estimation process is represented in Figure 6. Assume that we are currently on layer \(N\). On this layer we have already made clustering (Figure 2, step 2) and filled in the performance table (Figure 5). Assume, we are estimating classification performance for one of the partitions \(\{l_{4},l_{5},l_{6}\}\) (Figure 3 \(k=3\) and Figure 6) with two ways of splitting (Figure 4, \(S=\{1,2\}\)). \(TP^{*}\), \(FN^{*}\), and \(FP^{*}\) are computed in the following way:  
Figure 6: Estimating performance for cluster \(\{l_{4},l_{5},l_{6}\}\). * \(TP^{*}\). The number of true positives will decrease with each next level of the hierarchy. \(TP^{*}\) will depend on \(R\) and we will approximate it with the following function: \(TP^{*}_{N+2}=TP\cdot R^{T}_{K}\). \(K\) equals \(3\) for \(TP^{1*}_{N+2}\) and \(2\) for \(TP^{2*}_{N+2}\) (Figure 6, layer \(N+2\)). * \(FN^{*}\). We know \(TP^{*}\), \(N_{C}\), \(A_{C}\). So, \(FN^{*}_{N+2}=N_{C}\cdot A_{C}-TP^{*}_{N+2}\). * \(FP^{*}\). The main problem is to estimate \(FP\). Indeed the result of \(FP^{*}_{N+1}\) should be between \(TP\cdot(1-P^{T}_{K})\) and \(FP+TP\cdot(1-P^{T}_{K})\). We use a rather pessimistic estimation of it: \(FP^{*}_{N+2}=FP\cdot R^{T}_{K}+TP\cdot(1-P^{T}_{K})\). We computed \(TP^{*}\), \(FP^{*}\), \(TN^{*}\) on different layers of our cluster. We believe that a hierarchy should be rather balanced with leaves on the last two layers only. Let us denote the last layer as \(M\). Then there are two groups of leaves: leaves on the last layer (\(N^{L}_{M}\)) and leaves on the previous layer (\(N^{L}_{M-1}\)). \(N^{L}_{M}+N^{L}_{M-1}=C\). For example, Figure 6 represents a cluster of size \(3\). All leaves are on layer \(N+2\) for the first split. One leaf is on layer \(N+2\) and two leaves are on layer \(N+3\) for the second split. \[ \begin{array}{l}TP^{q*}=\frac{N^{L}_{M}}{C}\cdot TP^{*}_{M}+\frac{N^{L}_{M- 1}}{C}\cdot TP^{*}_{M-1}\\ FN^{q*}=\frac{N^{L}_{M}}{C}\cdot FN^{*}_{M}+\frac{N^{L}_{M-1}}{C}\cdot FN^{*} _{M-1}\\ FP^{q*}=\frac{N^{L}_{M}}{C}\cdot FP^{*}_{M}+\frac{N^{L}_{M-1}}{C}\cdot FP^{*} _{M-1}\end{array} \]  
Then we are able to compute relative measures for our cluster:  
\[