Search

Most clustering algorithms rely in some fundamental way on a measure of either similarity or distance — either between objects themselves, or between objects and cluster centroids. When the dataset contains mixed attributes, defining a suitable measure can be problematic. This paper presents a general graph-based method for clustering mixed-attribute datasets that does not require any explicit measure of similarity or distance. Empirical results on a range of well-known datasets using a range of evaluation measures show that the method achieves performance competitive with traditional clustering algorithms that require explicit calculation of distance or similarity, as well as with more recently proposed clustering algorithms based on matrix factorization.

Part-of-speech (PoS) tagging of non-standard language with models developed for standard language is known to suffer from a significant decrease in accuracy. Two methods are typically used to improve it: word normalisation, which decreases the out-of-vocabulary rate of the PoS tagger, and domain adaptation where the tagger is made aware of the non-standard language variation, either through supervision via non-standard data being added to the tagger’s training set, or via distributional information calculated from raw texts. This paper investigates the two approaches, normalisation and domain adaptation, on carefully constructed data sets encompassing historical and user-generated Slovene texts, in particular focusing on the amount of labour necessary to produce the manually annotated data sets for each approach and comparing the resulting PoS accuracy. We give quantitative as well as qualitative analyses of the tagger performance in various settings, showing that on our data set closed and open class words exhibit significantly different behaviours, and that even small inconsistencies in the PoS tags in the data have an impact on the accuracy. We also show that to improve tagging accuracy, it is best to concentrate on obtaining manually annotated normalisation training data for short annotation campaigns, while manually producing in-domain training sets for PoS tagging is better when a more substantial annotation campaign can be undertaken. Finally, unsupervised adaptation via Brown clustering is similarly useful regardless of the size of the training data available, but improvements tend to be bigger when adaptation is performed via in-domain tagging data.

We investigate the dynamics of cross-market clustering and connectedness of the Asian capital markets in this study. We perform the cross-correlation structure analysis of the daily return data of 14 global indices belonging to the major Asian capital markets by using the sub-dominant ultrametric distance based MST and Hierarchical Clustering techniques. The study dataset is for fourteen years duration (2002–2016). A rolling window approach is used to generate 151 temporally synchronous observations. We generate MSTs and Hierarchical Clustering plots (based on average linkage distance) for these temporally synchronous observations, and visually comprehend them to decipher the cross-market cluster formation, hub node formation, and connectivity structure with hub nodes. To identify those set of Asian markets having close connectivity with India, we employed a weighted hop count method and based on its scorings the Asian indices are subsequently ranked. We also investigate the influence of the 2008 financial crisis on the connectivity and clustering patterns in the Asian indices network. We also compute the key network topological parameters to decipher the dynamically varying topological properties, and with a particular reference during financial crisis periods. Keywords: Network filtering, Data mining, Applied Graph Theory, Financial network analysis, MST, Hierarchical Clustering

Identifying the type of a scanned form image greatly facilitates automated processing, including field segmentation and field recognition. Contrary to most prior work, we focus on unsupervised type identification, where the possible form types for a given collection are not known apriori. Our target domain is noisy collections of form images that contain structurally similar, yet objectively different, form types, which are challenging to differentiate in an unsupervised setting. This work presents a novel algorithm: CONFIRM (Clustering Of Noisy Form Images using Robust Matching), which simultaneously discovers the set of form types in a collection and assigns a type to each form. CONFIRM matches type-set text and rule lines between forms to create collection-specific features, which we show outperform the Bag of Visual Word (BoVW) approach employed by the current state-of-the-art in form image clustering. CONFIRM scales well to large document collections with a bootstrap clustering process, in which only a small subset of the data is clustered directly, and the rest of the data is assigned to clusters in linear time. We show that CONFIRM reduces cluster impurity on average by 44% compared to the state-of-the art on 5 collections of historical forms that contain structurally similar form types.

In this paper, we present a novel word clustering technique to capture contextual similarity among the words. Related word clustering techniques in the literature rely on the statistics of the words collected from a fixed and small word window. For example, the Brown clustering algorithm is based on bigram statistics of the words. However, in the sequential labeling tasks such as named entity recognition (NER), longer context words also carry valuable information. To capture this longer context information, we propose a new word clustering algorithm, which uses parse information of the sentences and a nonfixed word window. This proposed clustering algorithm, named as variable window clustering, performs better than Brown clustering in our experiments. Additionally, to use two different clustering techniques simultaneously in a classifier, we propose a cluster merging technique that performs an output level merging of two sets of clusters. To test the effectiveness of the approaches, we use two different NER data sets, namely, Hindi and BioCreative II Gene Mention Recognition. A baseline NER system is developed using conditional random fields classifier, and then the clusters using individual techniques as well as the merged technique are incorporated to improve the classifier. Experimental results demonstrate that the cluster merging technique is quite promising.

Clustering is the method employed to group Web pages containing related information into clusters, which facilitates the allocation of relevant information. Clustering performance is mostly dependent on the text features' characteristics. The Arabic language has a complex morphology and is highly inflected. Thus, selecting appropriate features affects clustering performance positively. Many studies have addressed the clustering problem in Web pages with Arabic content. There are three main challenges in applying text clustering to Arabic Web page content. The first challenge concerns difficulty with identifying significant term features to represent original content by considering the hidden knowledge. The second challenge is related to reducing data dimensionality without losing essential information. The third challenge regards how to design a suitable model for clustering Arabic text that is capable of improving clustering performance. This paper presents an overview of existing Arabic Web page clustering methods, with the goals of clarifying existing problems and examining feature selection and reduction techniques for solving clustering difficulties. In line with the objectives and scope of this study, the present research is a joint effort to improve feature selection and vectorization frameworks in order to enhance current text analysis techniques that can be applied to Arabic Web pages. Keywords: Feature selection, Feature reduction, K-means, Review, Text clustering, ARABIC Web page

© 2017 ACM. Genetic programming (GP) has been shown to be very effective for performing data mining tasks. Despite this, it has seen relatively little use in clustering. In this work, we introduce a new GP approach for performing graph-based (GPGC) non-hyper-spherical clustering where the number of clusters is not required to be set in advance. The proposed GPGC approach is compared with a number of well known methods on a large number of data sets with a wide variety of shapes and sizes. Our results show that GPGC is the most generalisable of the tested methods, achieving good performance across all datasets. GPGC significantly outperforms all existing methods on the hardest ellipsoidal datasets, without needing the user to pre-define the number of clusters. To our knowledge, this is the first work which proposes using GP for graph-based clustering.

The objective of cluster analysis is to partition a set of data points into several groups based on a suitable distance measure. We first propose a model called local gravitation among data points. In this model, each data point is viewed as an object with mass, and associated with a local resultant force (LRF) generated by its neighbors. The motivation of this paper is that there exist distinct differences between the LRFs (including magnitudes and directions) of the data points close to the cluster centers and at the boundary of the clusters. To capture these differences efficiently, two new local measures named centrality and coordination are further investigated. Based on empirical observations, two new clustering methods called local gravitation clustering and communication with local agents are designed, and several test cases are conducted to verify their effectiveness. The experiments on synthetic data sets and real-world data sets indicate that both clustering approaches achieve good performance on most of the data sets.

An NIDS system based on SVM ,GA and Hierarchical Clustering is proposed.GA along with hierarchical clustering is used to provide fewer,efficient and abstraced instances of the KDD Cup 1999 dataset to SVM for further processing.GA is used to eliminate the unimportant feature and BIRCH hierarchical clustering is used to provide optimal instances of the data set to the SVM.Due to this optimal instances, SVM will be able to classify the network traffic data more accurately and precisely . This system try to reduce the detection time of r2l,u2r,probe and DoS atack and increase in the accuracy.

The demand of fast clustering increases rapidly as we keep collecting tremendously large amount of data in the last decade. In this paper, we propose a nonparametric and representative-based Sparse Self-Represented Network Map for fast clustering on large dataset. Each node in the network generates a heat map for the dataset by receiving stimulations from data within its Accepting Field. We developed a weight adjusting method to learn and summarize the clustering pattern of the data. Such learned map is used for computing clustering results, by breaking weak links and finding connected components Rather than employing an iterative process to find local minima, our network passes the dataset only once and is able to capture the global pattern of the dataset as well as detecting natural number of clusters. As a nonparametric method, we propose Sparse Dynamic Instantiation to avoid the curse of dimensionality, namely a node or a link is instantiated only when stimulated by input data. As a result, the overall complexity is linear to the data dimension. Our algorithm is tested on synthetic and real datasets and compare with popular clustering algorithms (K-means + + , Expectation–Maximization, Mean-Shift and StreamKM + + ) as well as state-of-art clustering algorithm (Affinity Propagation and Density Peak). We also applied our clustering algorithm to mobile location clustering, building a Visual Dictionary for image recognition, and clustering data streams. Our experiments indicate that our algorithm can be a better alternative for all compared popular clustering algorithms especially when efficiency is the primary consideration, namely we drastically improve time and space complexity but retain equal level of accuracy.

Propose a hierarchical trajectory clustering framework for periodic pattern mining.Propose a trajectory clustering approach that considers additional semantics.Extend the proposed clustering to take into account the sequence of trajectory.Overcome the drawbacks of traditional periodic pattern mining.Provide experimental results to demonstrate the versatility of proposed framework. Spatio-temporal periodic pattern mining is to find temporal regularities for interesting places. Many real world spatio-temporal phenomena present sequential and hierarchical nature. However, traditional spatio-temporal periodic pattern mining ignores the consideration of sequence, and fails to take into account inherent hierarchy. This paper proposes a hierarchical trajectory clustering based periodic pattern mining that overcomes the two common drawbacks from traditional approaches: hierarchical reference spots and consideration of sequence. We propose a new trajectory clustering algorithm which considers semantic spatio-temporal information such as direction, speed and time based on Traclus and present comparative experimental results with three popular clustering methods: Kernel function, Grid-based, and Traclus. We further extend the proposed trajectory clustering to hierarchical clustering with the use of the single linkage approach to generate a hierarchy of reference spots. Experimental results reveal various hierarchical periodic patterns, and demonstrate that our algorithm outperforms traditional reference spot detection algorithms.

This work draws inspiration from three important sources of research on dissimilarity-based clustering and intertwines those three threads into a consistent principled functorial theory of clustering. Those three are the overlapping clustering of Jardine and Sibson, the functorial approach of Carlsson and M\'{e}moli to partition-based clustering, and the Isbell/Dress school's study of injective envelopes. Carlsson and M\'{e}moli introduce the idea of viewing clustering methods as functors from a category of metric spaces to a category of clusters, with functoriality subsuming many desirable properties. Our first series of results extends their theory of functorial clustering schemes to methods that allow overlapping clusters in the spirit of Jardine and Sibson. This obviates some of the unpleasant effects of chaining that occur, for example with single-linkage clustering. We prove an equivalence between these general overlapping clustering functors and projections of weight spaces to what we term clustering domains, by focusing on the order structure determined by the morphisms. As a specific application of this machinery, we are able to prove that there are no functorial projections to cut metrics, or even to tree metrics. Finally, although we focus less on the construction of clustering methods (clustering domains) derived from injective envelopes, we lay out some preliminary results, that hopefully will give a feel for how the third leg of the stool comes into play., Comment: Minor revisions. 24 pages, 1 figure

Clustering, the process of grouping together similar items into distinct partitions, is a common type of unsupervised machine learning that can be useful for summarizing and aggregating complex multi-dimensional data. However, data can be clustered in many ways, and there exist a large body of algorithms designed to reveal different patterns. While having access to a wide variety of algorithms is helpful, in practice, it is quite difficult for data scientists to choose and parameterize algorithms to get the clustering results relevant for their dataset and analytical tasks. To alleviate this problem, we built Clustervision , a visual analytics tool that helps ensure data scientists find the right clustering among the large amount of techniques and parameters available. Our system clusters data using a variety of clustering techniques and parameters and then ranks clustering results utilizing five quality metrics. In addition, users can guide the system to produce more relevant results by providing task-relevant constraints on the data. Our visual user interface allows users to find high quality clustering results, explore the clusters using several coordinated visualization techniques, and select the cluster result that best suits their task. We demonstrate this novel approach using a case study with a team of researchers in the medical domain and showcase that our system empowers users to choose an effective representation of their complex data.

In the era of big data, it is increasingly common that large amount of data is generated across multiple distributed sites and cannot be gathered into a centralized site for further analysis, which invalidates the assumption of traditional clustering techniques based on centralized models. The major challenge is that these distributed datasets cannot be trivially merged due to issues such as privacy concerns, limited network bandwidth among sites and limited computational capacity of a single site. To tackle this challenge, we propose an efficient distributed clustering scheme using boundary information (DCUBI), which features good flexibility and scalability. The main procedure of DCUBI consists of three steps: local-global-local. Firstly, each local site extracts the boundary points from its own local data and applies traditional clustering on boundary points only. Secondly, labeled boundary points from each site are sent to the central site as local representatives where boundary and cluster fusion is conducted to form the global clustering model. Finally, the global boundary and cluster information is sent back to each local site for refined local clustering. To demonstrate the effectiveness of DCUBI, we plug the well-known DBSCAN algorithm into DCUBI and comprehensive experiments are conducted using datasets with different properties. Experiment results clearly verify the quality of clustering by DCUBI as well as its superior time efficiency when the volume of data in each site is large. Furthermore, other popular clustering techniques especially those with high time complexity such as spectral clustering and affinity propagation clustering are also plugged into DCUBI to demonstrate the flexibility of the proposed scheme.

In this paper, a manifold-based dictionary learning method for the bag-of-features (BoF) representation optimized toward information clustering is proposed. First, the spectral representation, which unwraps the manifolds of the data and provides better clustering solutions, is formed. Then, a new dictionary is learned in order to make the histogram space, i.e., the space where the BoF historgrams exist, as similar as possible to the spectral space. The ability of the proposed method to improve the clustering solutions is demonstrated using a wide range of datasets: two image datasets, the 15-scene dataset and the Corel image dataset, one video dataset, the KTH dataset, and one text dataset, the RT-2k dataset. The proposed method improves both the internal and the external clustering criteria for two different clustering algorithms: 1) the -means and 2) the spectral clustering. Also, the optimized histogram space can be used to directly assign a new object to its cluster, instead of using the spectral space (which requires reapplying the spectral clustering algorithm or using incremental spectral clustering techniques). Finally, the learned representation is also evaluated using an information retrieval setup and it is demonstrated that improves the retrieval precision over the baseline BoF representation.

Data clustering is a very useful data mining technique to find groups of similar objects present in the dataset. Scalability to handle immense volumes, robustness to intrinsic outlier data and validity of clustering results are the main challenges of any data clustering approach. In order to address these challenges, a fuzzy weighted clustering approach which is comprehensibly parallel and distributed in every phase, is proposed in this research. Although the proposed method can be used for various data clustering purposes, it has been applied in gene expression clustering to reveal functional relationships of genes in a biological process. Conforming to MapReduce, the proposed method also presents a novel similarity measure which benefits from combining ordered weighted averaging and Spearman correlation coefficient. In the proposed method, density reachable genes were joined to establish subclusters. Afterwards, final cluster results were obtained by merging these subclusters. A voting system detects the best weights and consequently the most valid clusters among all possible results for each distinct dataset. The whole algorithm is implemented on a distributed processing platform and it is scalable to process any size of data stored in cloud infrastructures. Precision of resulting clusters were evaluated using some of the well-known cluster validity indexes in the literature. Also, the efficiency of the proposed method in scalability and robustness was compared with recently published similar researches. In all the mentioned comparisons, the proposed method outperformed recent works on the same datasets.

An original computational approach for cluster analysis is proposed.The method consists of two phases, which are based on Self-Organizing Map.Topology-preserving and connectivity functions are used in the clustering process.The method is proved using three benchmark datasets and a real biological dataset.Automation in parameterization results in a user-friendly methodology. Data clustering is aimed at finding groups of data that share common hidden properties. These kinds of techniques are especially critical at early stages of data analysis where no information about the dataset is available. One of the mayor shortcomings of the clustering algorithms is the difficulty for non-experts users to configure them and, in some cases, interpret the results. In this work a computational approach with a two-layer structure based on Self-Organizing Map (SOM) is presented for cluster analysis. In the first level, a quantization of the data samples using topology-preserving metrics to automatically determine the number of units in the SOM is proposed. In the second level the obtained SOM prototypes are clustered by means of a connectivity analysis to explore the quality of the partitioning with different number of clusters. The most important benefit of this two-layer procedure is that computational load decreases considerably in comparison with data based clustering methods, making it possible to cluster large data sets and to consider several different clustering alternatives in a limited time. This methodology produces a two-dimensional map representation of the, usually, high dimensional input space, along with quantitative information on viable clustering alternatives, which facilitates the exploration of the possible partitions in a dataset. The efficiency and interpretation of the methodology is illustrated by its application to artificial, benchmark and real complex biological datasets. The experimental results demonstrate the ability of the method to identify possible segmentations in a dataset, compared to algorithms that only yield a single clustering solution. The proposed algorithm tackles the intrinsic limitations of SOM and the parameter settings associated with the clustering methodology, without requiring the number of clusters or the SOM architecture as a prerequisite, among others. This way, it makes possible its application even by researchers with a limited expertise in machine learning.

In high-dimensional data, clusters often exist in the form of complex hierarchical relationships. In order to explore these relationships, there is a need to integrate dimensionality reduction techniques with data mining approaches and graph theory. The correlations in data points emerge more clearly if this integration is flawless. We propose an approach called Local Graph Based Correlation Clustering (LGBACC). This approach merges hierarchical clustering, with PCA to uncover complex hierarchical relationships, and uses graph models to visualize the results. We propose a framework of this approach that is divided into four phases. Each phase is flawlessly integrated with the next phase. Visualization of data after each phase is an important output and is knitted into the fabric of the framework. The focus of this technique remains on obtaining high quality clusters. The quality of the final clusters obtained is measured using standard indices. It is found that LGBACC is better than the existing hierarchical clustering approaches. We have used real-world data sets to validate our framework. These datasets test the approach on low as well as high-dimensional data. It is found that LGBACC produces high-quality clusters across a wide spectrum of dimensionality. Scalability test on synthetically produced high-dimensional and large datasets show that the proposed approach runs efficiently. Hence, LGBACC is an efficient and scalable approach that produces high-quality clusters in high-dimensional and large data spaces.

In this paper, we propose a semi-supervised clustering method, CEC-IB , that models data with a set of Gaussian distributions and that retrieves clusters based on a partial labeling provided by the user (partition-level side information). By combining the ideas from cross-entropy clustering (CEC) with those from the information bottleneck method (IB), our method trades between three conflicting goals: the accuracy with which the data set is modeled, the simplicity of the model, and the consistency of the clustering with side information. Experiments demonstrate that CEC-IB performs similar as Gaussian mixture models in a classical semi-supervised scenario, but is faster, more robust to noisy labels, automatically determines the optimal number of clusters, and performs well when not all classes are present in the side information. Moreover, in contrast to many other semi-supervised models, it can be successfully applied in discovering natural subgroups if the partition-level side information is derived from the top levels of a hierarchical clustering.

This work proposes a novel data clustering algorithm based on the potential field model, with a hierarchical optimization mechanism on the algorithm. There are two stages in this algorithm. Firstly, we build an edge-weighted tree based on the mutual distances between all data points and their hypothetical potential values derived from the data distribution. Using the tree structure, the dataset can be divided into an appropriate number of initial sub-clusters, with the cluster centers close to the local minima of the potential field. Then the sub-clusters are further merged according to the well-designed merging criteria by analyzing their border potential values and the cluster average potential values. The proposed clustering algorithm follows a hierarchical clustering mechanism, and aims to optimize the initial sub-cluster results in the first stage. The algorithm takes advantage of the cluster merging criteria to merge the sub-clusters, so it can automatically stop the clustering process without designating the number of clusters in advance. The experimental results show that the proposed algorithm produces the most satisfactory clustering results in most cases compared with other existing methods, and can effectively identify the data clusters with arbitrary shape, size and density.

Classification rules should be open for public inspection to ensure fairness.These rules can be originally induced from some dataset. If induced classification rules are supported only by a small number of objects in the dataset, publication can lead to identification of objects supporting the rule, given their speciality. Eventually, it is possible to retrieve information about the identified objects. This identifiability is not desirable in terms of data privacy.In this paper, to avoid such privacy breaches, we propose rule clustering for achievingk-anonymity of all induced rules, i.e., the induced rules are supported by at leastkobjects in the dataset. The proposed approach merges similar rules to satisfyk-anonymity while aiming to maintain the classification accuracy. Two numerical experiments were executed to verify both the accuracy of the classifier with the rules obtained by the proposed method and the ratio of decision classes revealed from leaked information about objects. The experimental results show the usefulness of the proposed method.

Density Based Spatial Clustering of Applications with Noise (DBSCAN), a well-known Density-Based Clustering Algorithm is a advanced data clustering method with various applications in numerous fields like Satellites images, X-ray crystallography, Anomaly Detection in Temperature Data. But its run time R(n2) complexity draws a major challenge. In this research paper, we propose a new unique algorithm called Real Time Density Based Clustering RTDBC to minimize the problems in DBSCAN. In proposed algorithms, objects are allotted into clusters using labels representatives than the method of propagating directly to reduce propagation time of label considerably. In contrast, RTDBC produce fast result and continuous process of runtime and additionally users are permitted to suspend for testing the result and continue as to enhance good results.

Uncertain data clustering has become central in mining data whose observed representation is naturally affected by imprecision, staling, or randomness that is implicit when storing this data from real-word sources. Most existing methods for uncertain data clustering follow a partitional or a density-based clustering approach, whereas little research has been devoted to the hierarchical clustering paradigm. In this work, we push forward research in hierarchical clustering of uncertain data by introducing a well-founded solution to the problem via an information-theoretic approach, following the initial idea described in our earlier work [26]. We propose a prototype-based agglomerative hierarchical clustering method, dubbed U-AHC, which employs a new uncertain linkage criterion for cluster merging. This criterion enables the comparison of (sets of) uncertain objects based on information-theoretic as well as expected-distance measures. To assess our proposal, we have conducted a comparative evaluation with state-of-the-art algorithms for clustering uncertain objects, on both benchmark and real datasets. We also compare with two basic definitions of agglomerative hierarchical clustering that are treated as baseline methods in terms of accuracy and efficiency of the clustering results, respectively. Main experimental findings reveal that U-AHC generally outperforms competing methods in accuracy and, from an efficiency viewpoint, is comparable to the fastest baseline version of agglomerative hierarchical clustering. © 2017 Elsevier Inc.

The traditional methods of clustering are unable to cope with the exploding volume of data that the world is currently facing. As a solution to this problem, the research is intensified in the direction of parallel clustering methods. Although there is a variety of parallel programming models, the MapReduce paradigm is considered as the most prominent model for problems of large scale data processing of which the clustering. This paper introduces a new parallel design of a recently appeared heuristic for hard clustering using the MapReduce programming model. In this heuristic, clustering is performed by efficiently partitioning categorical large data sets according to the relational analysis approach. The proposed design, called PMR-Transitive, is a single-scan and parameter-free heuristic which determines the number of clusters automatically. The experimental results on real-life and synthetic data sets demonstrate that PMR-Transitive produces good quality results.

© 1989-2012 IEEE. Spectral clustering has been playing a vital role in various research areas. Most traditional spectral clustering algorithms comprise two independent stages (e.g., first learning continuous labels and then rounding the learned labels into discrete ones), which may cause unpredictable deviation of resultant cluster labels from genuine ones, thereby leading to severe information loss and performance degradation. In this work, we study how to achieve discrete clustering as well as reliably generalize to unseen data. We propose a novel spectral clustering scheme which deeply explores cluster label properties, including discreteness, nonnegativity, and discrimination, as well as learns robust out-of-sample prediction functions. Specifically, we explicitly enforce a discrete transformation on the intermediate continuous labels, which leads to a tractable optimization problem with a discrete solution. Besides, we preserve the natural nonnegative characteristic of the clustering labels to enhance the interpretability of the results. Moreover, to further compensate the unreliability of the learned clustering labels, we integrate an adaptive robust module with ℓ 2,p loss to learn prediction function for grouping unseen data. We also show that the out-of-sample component can inject discriminative knowledge into the learning of cluster labels under certain conditions. Extensive experiments conducted on various data sets have demonstrated the superiority of our proposal as compared to several existing clustering approaches.

The existing clustering algorithms are usually dependent on one or more input parameters, which are not easy to determine in many cases. In this paper, DSets-histeq is presented as a parameter-independent framework for data clustering. By histogram equalization transformation of pairwise data similarity matrices, the dominant sets algorithm is used to generate parameter-independent initial clusters, which are typically relatively large subsets of real clusters. This enables one to expand the initial clusters to the final ones with a cluster-growing algorithm and determine the involved parameters adaptively by making use of the information in the initial clusters. A simple yet effective method is proposed to utilize the information captured in the initial clusters. Experiments on various datasets and comparison with state-of-the-art clustering algorithms are used to illustrate the potential of the proposed framework.

We propose a multi-task clustering method by transferring knowledge of instances.The sample distance in different tasks is reweighted by learning a shared subspace.Related samples from other tasks are reused as auxiliary data to aid clustering.Our method maintains the label marginal distribution of each individual task.Better performance is observed compared with other multi-task clustering methods. Clustering is an essential issue in machine learning and data mining. As there are many related tasks in the real world, multi-task clustering, which improves the clustering performance of each task by transferring knowledge across the related tasks, receives increasing attention recently. Generally knowledge transfer can be accomplished in different ways. Nevertheless, besides transferring knowledge of feature representations, other knowledge transfer ways have seldom been adopted for multi-task clustering. In this paper, we propose a general multi-task clustering algorithm by transferring knowledge of instances. Our algorithm reweights the distance between samples in different tasks by learning a shared subspace, then selects the nearest neighbors for each sample from the other tasks in the learned shared subspace as the auxiliary data to aid the clustering process of each individual task. Experiments on real data sets in text mining and image mining demonstrate that our proposed algorithm outperforms the traditional single-task clustering methods and existing cross-domain multi-task clustering methods.

This paper presents a density- and grid- based (DGB) clustering method for categorizing data with arbitrary shapes and noise. As most of the conventional clustering approaches work only with round-shaped clusters, other methods are needed to be explored to proceed classification of clusters with arbitrary shapes. Clustering approach by fast search and find of density peaks and density-based spatial clustering of applications with noise, and so many other methods are reported to be capable of completing this task but are limited by their computation time of mutual distances between points or patterns. Without the calculation of mutual distances, this paper presents an alternative method to fulfill clustering of data with any shape and noise even faster and with more efficiency. It was successfully verified in clustering industrial data (e.g., DNA microarray data) and several benchmark datasets with different kinds of noise. It turned out that the proposed DGB clustering method is more efficient and faster in clustering datasets with any shape than the conventional methods.

Clustering, as an unsupervised learning method and an important process in data mining, is an aspect of large and distributed data analysis. In many applications, such as peer-to-peer systems, huge volumes of data are distributed between multiple sources. Analysis of these volumes of data and identifying appropriate clusters is challenging due to transmission, processing and storage costs. In this paper, a gossip-based distributed clustering algorithm for P2P networks called Efficient GBDC-P2P is proposed, based on an improved gossip communicative approach by combining the peer sampeling and CYCLON protocol and the idea of partitioning-based data clustering. This algorithm is appropriate for data clustering in unstructured P2P networks, and it is adapted to the dynamic conditions of these networks. In the Efficient GBDC-P2P algorithm, distributed peers perform clustering operation in a distributed way only through local communications with their neighbors. Our approach does not rely on the central server to carry out data clustering task and without the need to synchronize operations. Evaluation results verify the efficiency of our proposed algorithm for data clustering in unstructured P2P networks. Furthermore, comparative analyses with other well-established distributed clustering approaches demonstrate the superior accuracy of the proposed method.

A new initialization technique is proposed to improve the performance of K-means.A data transformation approach is proposed to solve empty cluster problem.An efficient method is proposed to estimate the optimal number of clusters.Proposed clustering method provides more accurate clustering results. Clustering provides a knowledge acquisition method for intelligent systems. This paper proposes a novel data-clustering algorithm, by combining a new initialization technique, K-means algorithm and a new gradual data transformation approach to provide more accurate clustering results than the K-means algorithm and its variants by increasing the clusters coherence. The proposed data transformation approach solves the problem of generating empty clusters, which frequently occurs for other clustering algorithms. An efficient method based on the principal component transformation and a modified silhouette algorithm is also proposed in this paper to determine the number of clusters. Several different data sets are used to evaluate the efficacy of the proposed method to deal with the empty cluster generation problem and its accuracy and computational performance in comparison with other K-means based initialization techniques and clustering methods. The developed estimation method for determining the number of clusters is also evaluated and compared with other estimation algorithms. Significances of the proposed method include addressing the limitations of the K-means based clustering and improving the accuracy of clustering as an important method in the field of data mining and expert systems. Application of the proposed method for the knowledge acquisition in time series data such as wind, solar, electric load and stock market provides a pre-processing tool to select the most appropriate data to feed in neural networks or other estimators in use for forecasting such time series. In addition, utilization of the knowledge discovered by the proposed K-means clustering to develop rule based expert systems is one of the main impacts of the proposed method.

With the rapid advances of sensing technologies and wireless communications, large amounts of dynamic data pertaining to industrial production are being collected from many sensor nodes deployed in the industrial Internet of Things. Analyzing those data effectively can help to improve the industrial services and mitigate the system unprepared breakdowns. As an important technique of data analysis, clustering attempts to find the underlying pattern structures embedded in unlabeled information. Unfortunately, most of the current clustering techniques that could only deal with static data become infeasible to cluster a significant volume of data in the dynamic industrial applications. To tackle this problem, an incremental clustering algorithm by fast finding and searching of density peaks based on k-mediods is proposed in this paper. In the proposed algorithm, two cluster operations, namely cluster creating and cluster merging, are defined to integrate the current pattern into the previous one for the final clustering result, and k-mediods is employed to modify the clustering centers according to the new arriving objects. Finally, experiments are conducted to validate the proposed scheme on three popular UCI datasets and two real datasets collected from industrial Internet of Things in terms of clustering accuracy and computational time.

The paper addresses dynamic combinatorial clustering. First, a systematic literature survey on dynamic/online clustering is presented (problems, methods, applications). Second, restructuring approach to clustering is described (one-stage clustering, multi-stage clustering, sorting). Third, two network application examples of dynamic/multistage clustering are examined: (a) multi-stage connection of users to access points, (b) partition coloring problem in optical networks (wavelength routing and assignment).

In the clustering of incomplete data, the processing of missing attribute values and the optimization procedure of clustering are always of concern. In this paper, a novel clustering method is proposed to cope with incomplete data. Owing to the uncertainty of missing values, we first estimate these values in the form of intervals using the nearest neighbor method, which utilizes information about the distribution of data and transforms incomplete data set into an interval-valued one. Then, a kernel method is introduced to increase the separability between data by implicitly mapping them into a higher dimensional feature space, in which a kernel-induced distance is used to replace the Euclidean distance so that the data can be processed in the original data space. We realize the kernel clustering of incomplete data set by means of a gradient-based alternating optimization of interval data clustering based on the interval kernel distance. Finally, the experimental results demonstrate that the proposed approach is superior in terms of its clustering performance.

The k-weakly hierarchical, pyramidal and paired hierarchical models are alternative multilevel clustering models that extend hierarchical clustering. In this paper, we study these various multilevel clustering models in the framework of general convexity. We prove a characterization of the paired hierarchical model via a four-point condition on the segment operator, and examine the case of k-weakly hierarchical models for k3. We also prove sufficient conditions for an interval convexity to be either hierarchical, paired hierarchical, pyramidal, weakly hierarchical or k-weakly hierarchical. Moreover, we propose a general algorithm for computing the interval convexity induced by any given interval operator, and deduce a unified clustering scheme for capturing either of the considered multilevel clustering models. We illustrate our results with two interval operators that can be defined from any dissimilarity index and propose a parameterized definition of an adaptive interval operator for cluster analysis.

The text clustering technique is an appropriate method used to partition a huge amount of text documents into groups. The documents size affects the text clustering by decreasing its performance. Subsequently, text documents contain sparse and uninformative features, which reduce the performance of the underlying text clustering algorithm and increase the computational time. Feature selection is a fundamental unsupervised learning technique used to select a new subset of informative text features to improve the performance of the text clustering and reduce the computational time. This paper proposes a hybrid of particle swarm optimization algorithm with genetic operators for the feature selection problem. The k-means clustering is used to evaluate the effectiveness of the obtained features subsets. The experiments were conducted using eight common text datasets with variant characteristics. The results show that the proposed algorithm hybrid algorithm (H-FSPSOTC) improved the performance of the clustering algorithm by generating a new subset of more informative features. The proposed algorithm is compared with the other comparative algorithms published in the literature. Finally, the feature selection technique encourages the clustering algorithm to obtain accurate clusters.

Image content clustering is an effective way to organize large databases thereby making the content based image retrieval process much easier. However, clustering of images with varied background and foreground is quite challenging. In this paper, we propose a novel image content clustering paradigm suitable for clustering large and diverse image databases. In our approach images are represented in a continuous domain based on a probabilistic Gaussian Mixture Model (GMM) with the images modeled as mixture of Gaussian distributions in the selected feature space. The distance metric between the Gaussian distributions is defined in the sense of Kullback–Leibler (KL) divergence. The clustering is done using a semi-supervised learning framework where labeled data in the form of cluster templates is used to classify the unlabelled data. The clusters are formed around initially chosen seeds and are updated in the due course based on user inputs. In our clustering approach the user interaction is done in a structured way as to get maximum inputs from the user in a limited time. We propose two methods to carry out the structured user interaction using which the cluster templates are updated to improve the quality of the clusters formed. The proposed method is experimentally evaluated on benchmark datasets that are specifically chosen to include a wide variation of images around a common theme that is typically encountered in applications like photo-summarization and poses a major semantic gap challenge to conventional clustering approaches. The experimental results presented demonstrate the effectiveness of the proposed approach.

Face clustering and face tracking are two areas of active research in automatic facial video processing. They, however, have long been studied separately, despite the inherent link between them. In this paper, we propose to perform simultaneous face clustering and face tracking from real world videos. The motivation for the proposed research is that face clustering and face tracking can provide useful information and constraints to each other, thus can bootstrap and improve the performances of each other. To this end, we introduce a Coupled Hidden Markov Random Field (CHMRF) to simultaneously model face clustering, face tracking, and their interactions. We provide an effective algorithm based on constrained clustering and optimal tracking for the joint optimization of cluster labels and face tracking. We demonstrate significant improvements over state-of-the-art results in face clustering and tracking on several videos. HighlightsA systematic approach to jointly solving two related tasks, i.e., face clustering and face tracklet linking in videos.Multiple types of prior knowledge extracted from videos.A novel and efficient method for constraint propagation, to augment the initial constraints extracted from videos.A Coupled Hidden Markov Random Field model to formulate clustering and tracklet linking together, and to incorporate different types of dependencies.

Reducing package-related cost is essential for various companies and institutions. Different packages are usually designed separately for each and every product, which results in less cost-effective packaging systems. In this study, a data mining model with three clustering algorithms was developed to modularize a packaging system by reducing the variety of packaging sizes. The three algorithms were k-means clustering, agglomerative hierarchical clustering and self-organizing feature map. The package models with similar shapes and sizes were clustered automatically and replaced by one package model with a size that suited them all. The study also analysed the financial effects including the purchasing and inventory costs of the package material and the transportation cost of the packaged products. The case study was carried out at Ericsson to select the best clustering algorithm of the three and to test the effectiveness and applicability of the proposed model. The results show that the packaging system modularized by the agglomerative hierarchical clustering algorithm is more cost-effective in this case compared with the ones modularized by the other two clustering algorithms and with the one without modularization. Copyright © 2017 John Wiley & Sons, Ltd.

Spectral clustering methods have various real-world applications, such as face recognition, community detection, protein sequences clustering etc. Although spectral clustering methods can detect arbitrary shaped clusters, resulting thus in high clustering accuracy, the heavy computational cost limits their scalability. In this paper, we propose an accelerated spectral clustering method based on landmark selection. According to the Weighted PageRank algorithm, the most important nodes of the data affinity graph are selected as landmarks. Furthermore, the selected landmarks are provided to a landmark spectral clustering technique to achieve scalable and accurate clustering. In our experiments, by using two benchmark face and shape image data sets, we examine several landmark selection strategies for scalable spectral clustering that either ignore or consider the topological properties of the data in the affinity graph. Also, we show that the proposed method outperforms baseline and accelerated spectral clustering methods, in terms of computational cost and clustering accuracy, respectively. Finally, we provide future directions in spectral clustering.

Hierarchical clustering is a popular approach in a number of fields with many well known algorithms. However, all existing work to our knowledge implements a greedy heuristic algorithm with no explicit objective function. In this work we formalize hierarchical clustering as an integer linear programming (ILP) problem with a natural objective function and the dendrogram properties enforced as linear constraints. Our experimental work shows that even for small data sets finding the global optimum produces more accurate results. Formalizing hierarchical clustering as an ILP with constraints has several advantages beyond finding the global optima. Relaxing the dendrogram constraints such as transitivity can produce novel problem variations such as finding hierarchies with overlapping clusterings. It is also possible to add constraints to encode guidance such as must – link , cannot – link , must – link – before etc. Finally, though exact solvers exist for ILP we show that a simple randomized algorithm and a linear programming (LP) relaxation can be used to provide approximate solutions faster.

The volume of spatio-textual data is drastically increasing in these days, and this makes more and more essential to process such a large-scale spatio-textual dataset. Even though numerous works have been studied for answering various kinds of spatio-textual queries, the analyzing method for spatio-textual data has rarely been considered so far. Motivated by this, this paper proposes a k-means based clustering algorithm specialized for a massive spatio-textual data. One of the strong points of the k-means algorithm lies in its efficiency and scalability, implying that it is appropriate for a large-scale data. However, it is challenging to apply the normal k-means algorithm to spatio-textual data, since each spatio-textual object has non-numeric attributes, that is, textual dimension, as well as numeric attributes, that is, spatial dimension. We address this problem by using the expected distance between a random pair of objects rather than constructing actual centroid of each cluster. Based on our experimental results, we show that the clustering quality of our algorithm is comparable to those of other k-partitioning algorithms that can process spatio-textual data, and its efficiency is superior to those competitors. HighlightsThe problem of clustering large-scale spatio-textual data is firstly studied. It has many real applications like location-based data cleaning.A modified version of the k-means clustering algorithm is developed for spatio-textual data using the expected pairwise distance.Experimentally, our algorithm is not only fast enough to tackle a massive spatio-textual dataset, but also fairly effective in terms of the quality.

Clustering is one of the recently challenging tasks since there is an ever-growing amount of data in scientific research and commercial applications. High quality and fast document clustering algorithms are in great demand to deal with large volume of data. The computational requirements for bringing such growing amount data to a central site for clustering are complex. The proposed algorithm uses optimal centroids for K-Means clustering based on Particle Swarm Optimization(PSO). PSO is used to take advantage of its global search ability to provide optimal centroids which aids in generating more compact clusters with improved accuracy. This proposed methodology utilizes Hadoop and MapReduce framework which provides distributed storage and analysis to support data intensive distributed applications. Experiments were performed on Reuter’s and RCV1 document dataset which shows an improvement in accuracy with reduced execution time.

Cluster analysis has proved to be an invaluable tool for the exploratory and unsupervised analysis of high-dimensional datasets. Among methods for clustering, hierarchical approaches have enjoyed substantial popularity in genomics and other fields for their ability to simultaneously uncover multiple layers of clustering structure. A critical and challenging question in cluster analysis is whether the identified clusters represent important underlying structure or are artifacts of natural sampling variation. Few approaches have been proposed for addressing this problem in the context of hierarchical clustering, for which the problem is further complicated by the natural tree structure of the partition, and the multiplicity of tests required to parse the layers of nested clusters. In this article, we propose a Monte Carlo based approach for testing statistical significance in hierarchical clustering which addresses these issues. The approach is implemented as a sequential testing procedure guaranteeing control of the family-wise error rate. Theoretical justification is provided for our approach, and its power to detect true clustering structure is illustrated through several simulation studies and applications to two cancer gene expression datasets.