A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 3: Grid-Based Clustering <s> Spatial data mining, i.e., discovery of interesting characteristics and patterns that may implicitly exist in spatial databases, is a challenging task due to the huge amounts of spatial data and to the new conceptual nature of the problems which must account for spatial distance. Clustering and region oriented queries are common problems in this domain. Several approaches have been presented in recent years, all of which require at least one scan of all individual objects (points). Consequently, the computational complexity is at least linearly proportional to the number of objects to answer each query. In this paper, we propose a hierarchical statistical information grid based approach for spatial data mining to reduce the cost further. The idea is to capture statistical information associated with spatial cells in such a manner that whole classes of queries and clustering problems can be answered without recourse to the individual objects. In theory, and confirmed by empirical studies, this approach outperforms the best previous method by at least an order of magnitude, especially when the data set is very large. <s> BIB001 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 3: Grid-Based Clustering <s> Data mining applications place special requirements on clustering algorithms including: the ability to find clusters embedded in subspaces of high dimensional data, scalability, end-user comprehensibility of the results, non-presumption of any canonical data distribution, and insensitivity to the order of input records. We present CLIQUE, a clustering algorithm that satisfies each of these requirements. CLIQUE identifies dense clusters in subspaces of maximum dimensionality. It generates cluster descriptions in the form of DNF expressions that are minimized for ease of comprehension. It produces identical results irrespective of the order in which input records are presented and does not presume any specific mathematical form for data distribution. Through experiments, we show that CLIQUE efficiently finds accurate cluster in large high dimensional datasets. <s> BIB002 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 3: Grid-Based Clustering <s> Clustering web sessions is to group web sessions based on similarity and consists of minimizing the intra-group similarity and maximizing the inter-group similarity. The other question that arises is how to measure similarity between web sessions. Here in this paper we adopted a CLIQUE (CLUstering in QUEst) algorithm for clustering web sessions for web personalization. Then we adopted various similarity measures like Euclidean distance, projected Euclidean distance Jaccard, cosine and fuzzy dissimilarity measures to measure the similarity of web sessions using sequence alignment to determine learning behaviors. This has significant results when comparing similarities between web sessions with various measures, we performed a variety of experiments in the context of density based clustering, based on sequence alignment to measure similarities between web sessions where sessions are chronologically ordered sequences of page visits. <s> BIB003 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 3: Grid-Based Clustering <s> Clustering has been widely used to identify possible structures in data and help users to understand data in an unsupervised manner. Traditional clustering methods often provide a single partitioning of the data that groups similar data objects in one group while separates dissimilar ones into different groups. However, it has been well recognized that assuming only a single clustering for a data set can be too strict and cannot capture the diversity in applications. Multiple clustering structures can be hidden in the data, and each represents a unique perspective of the data. Different multi-clustering methods, which aim to discover multiple independent structures hidden in data, have been proposed in the recent decade. Although multi-clustering methods may provide more information for users, it is still challenging for users to efficiently and effectively understand each clustering structure. Subspace multi-clustering methods address this challenge by providing each clustering a feature subspace. Moreover, most subspace multi-clustering methods are especially scalable for high-dimensional data, which has become more and more popular in real applications due to the advances of big data technologies. In this paper, we focus on the subject of subspace multi-clustering, which has not been reviewed by any previous survey. We formulate the subspace multi-clustering problem and categorize the methodologies in different perspectives (e.g., de-coupled methods and coupled methods). We compare different methods on a series of specific properties (e.g., input parameters and different kinds of subspaces) and analyze the advantages and disadvantages. We also discuss several interesting and meaningful future directions. <s> BIB004 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 3: Grid-Based Clustering <s> Gene expression data analysis has paramount implications for gene treatments, cancer diagnosis and other domains. Clustering is an important and promising tool to analyze gene expression data. Gene expression data is often characterized by a large amount of genes but with limited samples, thus various projective clustering techniques and ensemble techniques have been suggested to combat with these challenges. However, it is rather challenging to synergy these two kinds of techniques together to avoid the curse of dimensionality problem and to boost the performance of gene expression data clustering. In this paper, we employ a projective clustering ensemble (PCE) to integrate the advantages of projective clustering and ensemble clustering, and to avoid the dilemma of combining multiple projective clusterings. Our experimental results on publicly available cancer gene expression data show PCE can improve the quality of clustering gene expression data by at least 4.5% (on average) than other related techniques, including dimensionality reduction based single clustering and ensemble approaches. The empirical study demonstrates that, to further boost the performance of clustering cancer gene expression data, it is necessary and promising to synergy projective clustering with ensemble clustering. PCE can serve as an effective alternative technique for clustering gene expression data. <s> BIB005 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 3: Grid-Based Clustering <s> Abstract Density-based clustering has been widely used in many fields. A new effective grid-based and density-based spatial clustering algorithm, GRIDEN, is proposed in this paper, which supports parallel computing in addition to multi-density clustering. It constructs grids using hyper-square cells and provides users with parameter k to control the balance between efficiency and accuracy to increase the flexibility of the algorithm. Compared with conventional density-based algorithms, it achieves much higher performance by eliminating distance calculations among points based on the newly proposed concept of e-neighbor cells. Compared with conventional grid-based algorithms, it uses a set of symmetric ( 2 k + 1 ) D cells to identify dense cells and the density-connected relationships among cells. Therefore, the maximum calculated deviation of e-neighbor points in the grid-based algorithm can be controlled to an acceptable level through parameter k. In our experiments, the results demonstrate that GRIDEN can achieve a reliable clustering result that is infinite closed with respect to the exact DBSCAN as parameter k grows, and it requires computational time that is only linear to N. <s> BIB006 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 3: Grid-Based Clustering <s> Spatial data clustering has played an important role in the knowledge discovery in spatial databases. However, due to the increasing volume and diversity of data, conventional spatial clustering methods are inefficient even on moderately large data sets, and usually fail to discover clusters with diverse shapes and densities. To address these challenges, we propose a two-phase clustering method named KMDD (clustering by combining K-means with density and distance-based method) to fast find clusters with diverse shapes and densities in spatial databases. In the first phase, KMDD uses a partition-based algorithm (K-means) to cluster the data set into several relatively small spherical or ball-shaped subclusters. After that, each subcluster is given a local density; to merge subclusters, KMDD utilizes the idea that genuine cluster cores are characterized by a higher density than their neighbor subclusters and by a relatively large distance from subclusters with higher densities. Extensive experiments on both synthetic and real-world data sets demonstrate that the proposed algorithm has a near-linear time complexity with respect to the data set size and dimension, and has the capability to find clusters with diverse shapes and densities. <s> BIB007 </s> A Review of Computational Methods for Clustering Genes with Similar Biological Functions <s> Category 3: Grid-Based Clustering <s> Abstract Clustering is an important technique to deal with large scale data which are explosively created in internet. Most data are high-dimensional with a lot of noise, which brings great challenges to retrieval, classification and understanding. No current existing approach is “optimal” for large scale data. For example, DBSCAN requires O(n2) time, Fast-DBSCAN only works well in 2 dimensions, and ρ-Approximate DBSCAN runs in O(n) expected time which needs dimension D to be a relative small constant for the linear running time to hold. However, we prove theoretically and experimentally that ρ-Approximate DBSCAN degenerates to an O(n2) algorithm in very high dimension such that 2D > > n. In this paper, we propose a novel local neighborhood searching technique, and apply it to improve DBSCAN, named as NQ-DBSCAN, such that a large number of unnecessary distance computations can be effectively reduced. Theoretical analysis and experimental results show that NQ-DBSCAN averagely runs in O(n*log(n)) with the help of indexing technique, and the best case is O(n) if proper parameters are used, which makes it suitable for many realtime data. <s> BIB008
The design of grid-based clustering divides the entire data space into multiple, non-overlapping grid structures BIB006 BIB007 . This method performs faster than density-based clustering. Grid-based clustering can benefit from dividing the data space into grids to reduce its time complexity BIB008  . CLIQUE, grid-clustering technique for high-dimensional very large spatial databases (GCHL), and statistical information grid (STING) are examples of grid-based clustering BIB002 BIB003  BIB001 BIB004 . The GCHL technique can discover concave (deeper) and convex (higher) regions when applied in medical and geographical fields and by using the average eight direction (AED) technique   . However, both techniques struggle to identify complex clusters from high dimensional data. CLIQUE partitions the data space into cells and searches subspaces by counting the number of points in each cell  . Searching a suitable set of dimensions for each cluster can form the candidate subspace for the centroid of the cluster. Different groups of points are clustered in different subspaces BIB005 .