OsamorSoft: clustering index for comparison and quality validation in high throughput dataset

There is no specific definition of a cluster that has been widely agreed upon. But objects in a cluster should be identical or compatible and objects should be dissimilar in different clusters. This means maximizing the similarity within a cluster and reducing similarities between clusters [24, 25]. Clustering is among the methods used, specifically in genomics, for gaining insight into biological methods. Clustering can of course be seen in other fields of biological data processing [26]. Clustering algorithms is intended to classify clusters or groups of objects, which are more like one another than other clusters. This type of data analysis approach is closely linked to the task of generating a data model, that entails establishing a simple collection of properties that provides an understandable explanation of crucial aspects of a dataset [24]. In general, clustering approaches give further insight into complex data.

An early cluster index model was given by Rand [27] and this was followed by the work of Fowlkes and Mallows [10]. Rand statistic was first adjusted by Morey and Agresti [28, 29] with some level of error [30] before a more accurate adjustment was later done by Hubert and Arabie [31] to what is now popularly known as Hubert and Arabie Adjusted Rand Index (ARI_HA) [31]. Several authors in clustering community seem to believe that ARI_HA is comparatively the preferred index to most other measures [30, 32]. Krieger and Green [23] proposed a model named SEGWAY based on Rand criterion measure to provide single clustering for a set of separate partitions in a database while Tseng and Kao [9] proposed a clustering algorithm christened, correlation search technique (CST) for analysis of data from gene expression.

Several algorithms have evolved [33] and more are still being implemented at increasing pace with unequal matching pace in the development and implementation of validity measures to ensure that appropriate results are obtained [34]. Few works done on cluster validity are either in the internal cluster validity measure [35, 36] or external validity measure which is our emphasis in this article. However, tools that provide easy application of these cluster indexes are scarce and the few created are either not freely available or the programming language used for implementation are obsolete and no longer compatible or supported by current software architectures. Some common examples includes ANSI COBOL program, Clustisz for IBM 370 DOS created in 1975 by McClain and Rao [37], and the 1996 BASIC program of Saltstone and Stange [38] whose cluster quality validation implementation are now obsolete and publicly unavailable online. These tool in their current state, are no longer compatible with current software environment hence the need for a new tool that is compatible, platform independent, easy-to-use, friendly, and publicly available as proposed in this work. We were able to improve the reliability of clustering results through the implementation and use of a Java and Spreadsheet-based cluster validity tool called OsamorSoft using the clustering index model of Hubert and Arabie Adjusted Rand Index (ARI_HA). The proposed solution constitutes DNA_Omatrix and OsamorSpreadSheet used to respectively generate a matching matrix and evaluate the level of agreement between the cluster output of two k-means algorithms. It could also be useful in determining the cluster quality of each algorithm by comparing it with clusters of known structure as benchmark or gold standard algorithm.

Due to the need to have a clearer definition of the computed ARI_HA values so that outcomes can be unambiguously related to specific biological meaning and interpretation, we designed and evolved a 4-stage cluster validation value categorization. This is a modification of the Kappa statistics categorization which has some challenges in relating its outcome to biological interpretation. We programmatically counted the number of cluster membership obtained from clustering experiment of malaria microarray data using four algorithms namely Traditional k-means, Enhanced k-means, Overlapped k-means [11] and MMkmeans as described in Osamor et al. [21], [44] and use it to observe a trend. This guided us to set heuristics scale similar to Steinley [30] with stages namely Excellent, Moderate, Fair and Poor for description of ARI_HA as in Table 1.

Our method accepts cluster output of high-throughput data from two algorithms to be compared i.e. Algorithm 1 and Algorithm 2. The DNA_Omatrix tool accepts each cluster as a single file, truncates it into individual files equivalent to the number of clusters created. DNA_Omatrix processes it further to generate a matching matrix by finding the intersection of every 2 combination of clusters from the algorithms. This matrix is in turn pasted into the OsamorSpreadSheet which automatically computes the sum of squares of the matching matrix. Initially, the values of ARI_HA obtained were not very informative, hence we proposed the need to set a threshold for appropriate performance category. Our heuristics threshold are four categories ranging from Excellent with greater than or equal to 0.90 to less than 0.65 for poor level of agreement between the algorithms being compared. Despite differences in techniques, the value description is a bit similar to Kappa statistic proposed by Cohen [45, 46] but differs by having 4 sets instead of 6 sets of heuristics as present in Kappa statistics.

Several packages and programming languages have been used to implement clustering algorithms. Optimization and changes in existing methods are normally introduced during the development and implementation of these codes, this in turn leads to new versions of the original methods with diverse improvements, to make such codes more effective [47]. For assessing the similarities in clustering algorithms, several measures have been identified, [24] compared the normalized mutual information, Fowlkes-Mallows index, Adjusted Rand index and Jaccard index. Furthermore, the work of Shirkhorshidi et al. [48] studied the influence of Similarity and Dissimilarity Measures on clustering while Zhang and Fang [49] investigated missing data and imputation on clustering validity. In these cases, emphasized was not focused on ARI_HA. These problems happen when the expected value of the RI of two random partition does not take a constant value (zero for example) or the Rand statistic approaches its upper limit of unity as the number of cluster increases.

To test our method, firstly, we used example data of T₁ and T₂ matching matrix as described in Steinley [30]. This data of T₁ and T₂ fits dynamically into a 4 × 4 matrix of OsamorSpreadSheet. We may optionally hide the unused empty rows and columns using the spreadsheet’s “hide” and “unhide” feature to obtain a good sizable interface which is optional. At the completion of the experiment, the results of ARI_HA as obtained for T1 = 0.245588. Similarly, we also obtained ARI_HA for T₂ = 0.7401 following same approach. Our result is in line with the output manually generated by Steinley [30]. This implies that the T₂ has moderate validity compared to T₁ matrix with very poor validity.

Secondly, in order to ensure that further evaluation is attained using a high-throughput dataset, we employed the use of microarray data of Bozdech et al. [50, 51] containing 4915 genes by 49 time points and that of Le Roch et al. [52] containing 5119 genes by 17 time points. Following the description as specified in Osamor et al. [21], we clustered these datasets independently using MMk-means, Enhanced k-means, Traditional k-means and Overlapped k-means algorithms. DNA_Omatrix was used to correctly obtain the matching matrices and this was subsequently followed by the use of OsamorSpreadSheet to compute the ARI_HA and upon evaluation, we obtained similar result in line with Osamor et al. [21]. This result further confirm that our method as described in OsamorSoft is appreciably good to serve as a useful tool for comparing clustering qualities of algorithms especially where matching matrices can be obtained. Interestingly, the method is also able to give clue to the suitable number of k clusters to be applied from various checks of ARI_HA and ultimately make biological results easier to analyse and interpret. This is achieved by comparing the various k-cluster runs against a gold standard clustering for cluster quality checks as judged by the ARI_HA value. It is worthy to recall that Xu et al. [53] recently tried to formulated a unified validity index framework but their work is restricted to only hierarchical clustering having proposed two synthetical clustering validity (SCV) indexes where minimum spanning tree was utilized to compute the compactness of intra-cluster with a view to minimise deficiencies in accuracy for existing validity indexes. We emphasize here that the methodology described represents a big data solution as could be encapsulated in the methodology pipeline shown in Fig. 1.

It is important to state clearly again that the methodology involves the use of big data because the dataset used is a large microarray data originating from imaging technology for gene expression in the biological domain. This is to say that what constitutes what can be classified as a big data varies from domain to domain but the major attribute of a big data is that it is large and maybe structured or unstructured and imaging technology output and application usually constitute a big data problem as seen in this work. The spreadsheet design is capable of computing AHI_HA for 20x20 clusters on a screen viewport (See Fig. 3a–c).

However, if higher dimension clusters are required, the worksheet is increased by simple insertion of additional rows and columns in the worksheet up to k = 16,384. An empty excel spreadsheet that serves as a single worksheet is made up of 1,048,576 rows by 16,384 columns, hence this Osamorspreadsheet application is able to process big data in the magnitude of specified by the capacity of the rows and column in the worksheet which transcends to a huge volume of data with its attendant simplicity in design and convenience to a wider user audience.