## 3 Proposed Ensemble Clustering
### Problem Definition
#### 3.2.1 Production of Multiple Base Clustering Results
The time complexity of the base locally reliable clustering algorithm presented in Algorithm 2 is \(O(|D_{:1}|C)\), which is in the worst case \(O\Big{(}|D_{:1}|^{1.5}I\Big{)}\) where \(I\) is number of the iterations the kmedoids clustering algorithm needs to converge. The algorithm of generating the ensemble of clustering results presented in Algorithm 1 is \(O\Big{(}|D_{:1}|I\sum_{i=1}^{B}C\Big{)}\), which is the worst case \(O\Big{(}|D_{:1}|^{1.5}IB\Big{)}\) where \(B\) is the number of basic clustering results generated. The outputs of the algorithm presented in Algorithm 1 have been the clustering set \(\mathbf{\Phi}\) and also the set of clusters' numbers in ensemble members. ### Construction of Clusters' Relations

Class labels show specific classes in the classification, while cluster labels express only the data grouping features and are not comparable in cluster analysis in different clustering results. Therefore, different clustering labels must be aligned in the ensemble clustering. Additionally, since the kmeans and kmedoids clustering algorithms can only detect spherical and uniform clusters, a number of clusters in a same clustering result can inherently be a same cluster. Therefore, analysis of the relationship between clusters through a between-cluster similarity measure is needed. Now, there are a large number of criteria proposed in the research background [49; 55; 56; 57] to measure the similarity among the clusters. For example, in the chain clustering algorithm, the distance between the closest or farthest data object of the two clusters is used for measuring the cluster separation [56; 57]. They are sensitive to noise because of their dependence on a few objects. In the center-based clustering algorithms, distance between the centers of clusters measures the lack of correlation between the two clusters. Although this measure is considered to be a computationally efficient and powerful measure to deal with noise, it cannot reflect the boundary between the two clusters. The number of common objects created by the two clusters is used to represent their similarity in cluster grouping algorithms. This measure does not consider the fact that the cluster labels of some objects may be incorrect in a cluster. Therefore, some of these objects have a significant impact on the measurement. Additionally, since two clusters of a same clustering do not have any common objects, measurement cannot be used to measure their similarity. Although there are good practical implementations of different measures, they are not suitable for ensemble clustering. In the previous section, the basic clustering generated \(\mathbf{\Phi}\) with valid local labels are different, which means that the labels of each cluster are only partially valid. Therefore, measurement of the difference between the two clusters in our local labels, instead of all the labels, is needed. However, the overlap between the local spatial spaces of both clusters should be very small because of the basic clustering generation mechanism. Therefore, we consider an \"indirect\" overlap between the two clusters in order to measure their similarity. Let us assume we have \(\Phi_{:i}\) and \(\Phi_{:j}\) as the two clusters, \(M^{\Phi_{:i}}\) and \(M^{\Phi_{:j}}\) as their cluster centers, and consequently, \(p_{5:}\big{(}\Phi_{:j},\Phi_{:j}\big{)}\) as the middle point of the two centers. We assume there is a hidden dense region between the reliable sections of the clusters pair \(\Phi_{:i}\) and \(\Phi_{:j}\), i.e., \(R^{\Phi_{:i}}\) and \(R^{\Phi_{:j}}\). We define 9 points \(p_{\text{\tiny{E}}}\big{(}\Phi_{:i},\Phi_{:j}\big{)}\) for \(k\in\{1,2,\dots,9\}\) at the equal distances on line connecting \(M^{\Phi_{:i}}\) to \(M^{\Phi_{:j}}\). We assume whatever the number of objects is larger in all of the valid local spaces, it is more likely that those clusters are the same.