Clustering Categorical Data via Ensembling Dissimilarity Matrices

We present a technique for clustering categorical data by generating many dissimilarity matrices and combining them. We begin by demonstrating our technique on low-dimensional categorical data and comparing it to several other techniques that have been proposed. We show through simulations and examples that our method is both more accurate and more stable. Then we give conditions under which our method should yield good results in general. Our method extends to high-dimensional categorical data of equal lengths by ensembling over many choices of explanatory variables. In this context, we compare our method with two other methods. Finally, we extend our method to high-dimensional categorical data vectors of unequal length by using alignment techniques to equalize the lengths. We give an example to show that our method continues to provide useful results, in particular, providing a comparison with phylogenetic trees. Supplementary material for this article is available online.     

Semi-supervised model-based clustering with positive and negative constraints

Cluster analysis is a popular technique in statistics and computer science with the objective of grouping similar observations in relatively distinct groups generally known as clusters. Semi-supervised clustering assumes that some additional information about group memberships is available. Under the most frequently considered scenario, labels are known for some portion of data and unavailable for the rest of observations. In this paper, we discuss a general type of semi-supervised clustering defined by so called positive and negative constraints. Under positive constraints, some data points are required to belong to the same cluster. On the contrary, negative constraints specify that particular points must represent different data groups. We outline a general framework for semi-supervised clustering with constraints naturally incorporating the additional information into the EM algorithm traditionally used in mixture modeling and model-based clustering. The developed methodology is illustrated on synthetic and classification datasets. A dendrochronology application is considered and thoroughly discussed.     

Some robust objectives of FCM for data analyzing

There are many data clustering techniques available to extract meaningful information from real world data, but the obtained clustering results of the available techniques, running time for the performance of clustering techniques in clustering real world data are highly important. This work is strongly felt that fuzzy clustering technique is suitable one to find meaningful information and appropriate groups into real world datasets. In fuzzy clustering the objective function controls the groups or clusters and computation parts of clustering. Hence researchers in fuzzy clustering algorithm aim is to minimize the objective function that usually has number of computation parts, like calculation of cluster prototypes, degree of membership for objects, computation part for updating and stopping algorithms. This paper introduces some new effective fuzzy objective functions with effective fuzzy parameters that can help to minimize the running time and to obtain strong meaningful information or clusters into the real world datasets. Further this paper tries to introduce new way for predicting membership, centres by minimizing the proposed new fuzzy objective functions. And experimental results of proposed algorithms are given to illustrate the effectiveness of proposed methods.     

An incremental clustering algorithm based on hyperbolic smoothing

Clustering is an important problem in data mining. It can be formulated as a nonsmooth, nonconvex optimization problem. For the most global optimization techniques this problem is challenging even in medium size data sets. In this paper, we propose an approach that allows one to apply local methods of smooth optimization to solve the clustering problems. We apply an incremental approach to generate starting points for cluster centers which enables us to deal with nonconvexity of the problem. The hyperbolic smoothing technique is applied to handle nonsmoothness of the clustering problems and to make it possible application of smooth optimization algorithms to solve them. Results of numerical experiments with eleven real-world data sets and the comparison with state-of-the-art incremental clustering algorithms demonstrate that the smooth optimization algorithms in combination with the incremental approach are powerful alternative to existing clustering algorithms.     

On principle axis based line symmetry clustering techniques

In this paper, at first a new line symmetry (LS) based distance is proposed which calculates the amount of symmetry of a point with respect to the first principal axis of a data set. The proposed distance uses a recently developed point symmetry (PS) based distance in its computation. Kd-tree based nearest neighbor search is used to reduce the complexity of computing the closest symmetric point. Thereafter an evolutionary clustering technique is described that uses this new principal axis based LS distance for assignment of points to different clusters. The proposed GA with line symmetry distance based (GALS) clustering technique is able to detect any type of clusters, irrespective of their geometrical shape, size or convexity as long as they possess the characteristics of LS. GALS is compared with the existing genetic algorithm based K-means clustering technique, GAK-means, existing genetic algorithm with PS based clustering technique, GAPS, spectral clustering technique, and average linkage clustering technique. Five artificially generated data sets having different characteristics and seven real-life data sets are used to demonstrate the superiority of the proposed GALS clustering technique. In a part of experiment, utility of the proposed genetic LS distance based clustering technique is demonstrated for segmenting the satellite image of the part of the city of Kolkata. The proposed technique is able to distinguish different landcover types in the image. In the last part of the paper genetic algorithm is used to search for the suitable line of symmetry of each cluster.     

Correspondence and canonical analysis of relational data

Correspondence analysis, a data analytic technique used to study two‐way cross‐classifications, is applied to social relational data. Such data are frequently termed “sociometric” or “network” data. The method allows one to model forms of relational data and types of empirical relationships not easily analyzed using either standard social network methods or common scaling or clustering techniques. In particular, correspondence analysis allows one to model:

—two‐mode networks (rows and columns of a sociomatrix refer to different objects)

—valued relations (e.g. counts, ratings, or frequencies).

In general, the technique provides scale values for row and column units, visual presentation of relationships among rows and columns, and criteria for assessing “dimensionality” or graphical complexity of the data and goodness‐of‐fit to particular models. Correspondence analysis has recently been the subject of research by Goodman, Haberman, and Gilula, who have termed their approach to the problem “canonical analysis” to reflect its similarity to canonical correlation analysis of continuous multivariate data. This generalization links the technique to more standard categorical data analysis models, and provides a much‐needed statistical justificatioa

We review both correspondence and canonical analysis, and present these ideas by analyzing relational data on the 1980 monetary donations from corporations to nonprofit organizations in the Minneapolis St. Paul metropolitan area. We also show how these techniques are related to dyadic independence models, first introduced by Holland, Leinhardt, Fienberg, and Wasserman in the early 1980's. The highlight of this paper is the relationship between correspondence and canonical analysis, and these dyadic independence models, which are designed specifically for relational data. The paper concludes with a discussion of this relationship, and some data analyses that illustrate the fart that correspondence analysis models can be used as approximate dyadic independence models.     

Dissimilarity Plots: A Visual Exploration Tool for Partitional Clustering

For hierarchical clustering, dendrograms are a convenient and powerful visualization technique. Although many visualization methods have been suggested for partitional clustering, their usefulness deteriorates quickly with increasing dimensionality of the data and/or they fail to represent structure between and within clusters simultaneously. In this article we extend (dissimilarity) matrix shading with several reordering steps based on seriation techniques. Both ideas, matrix shading and reordering, have been well known for a long time. However, only recent algorithmic improvements allow us to solve or approximately solve the seriation problem efficiently for larger problems. Furthermore, seriation techniques are used in a novel stepwise process (within each cluster and between clusters) which leads to a visualization technique that is able to present the structure between clusters and the micro-structure within clusters in one concise plot. This not only allows us to judge cluster quality but also makes misspecification of the number of clusters apparent. We give a detailed discussion of the construction of dissimilarity plots and demonstrate their usefulness with several examples. Experiments show that dissimilarity plots scale very well with increasing data dimensionality.

Supplemental materials with additional experiments for this article are available online.     

Chameleon based on clustering feature tree and its application in customer segmentation

Clustering analysis plays an important role in the filed of data mining. Nowadays, hierarchical clustering technique is becoming one of the most widely used clustering techniques. However, for most algorithms of hierarchical clustering technique, the requirements of high execution efficiency and high accuracy of clustering result cannot be met at the same time. After analyzing the advantages and disadvantages of the hierarchical algorithms, the paper puts forward a two-stage clustering algorithm, named Chameleon Based on Clustering Feature Tree (CBCFT), which hybridizes the Clustering Tree of algorithm BIRCH with algorithm CHAMELEON. By calculating the time complexity of CBCFT, the paper argues that the time complexity of CBCFT increases linearly with the number of data. By experimenting on sample data set, this paper demonstrates that CBCFT is able to identify clusters with large variance in size and shape and is robust to outliers. Moreover, the result of CBCFT is as similar as that of CHAMELEON, but CBCFT overcomes the shortcoming of the low execution efficiency of CHAMELEON. Although the execution time of CBCFT is longer than BIRCH, the clustering result of CBCFT is much satisfactory than that of BIRCH. Finally, through a case of customer segmentation of Chinese Petroleum Corp. HUBEI branch; the paper demonstrates that the clustering result of the case is meaningful and useful. The research is partially supported by National Natural Science Foundation of China (grants #70372049 and #70121001).     

Potential inventory cost reductions using advanced time series forecasting techniques

This paper compares demand forecasts computed using the time series forecasting techniques of vector autoregression (VAR) and Bayesian VAR (BVAR) with forecasts computed using exponential smoothing and seasonal decomposition. These forecasts for three demand data series were used to determine three inventory management policies for each time series. The inventory costs associated with each of these policies were used as a further basis for comparison of the forecasting techniques. The results show that the BVAR technique, which uses mixed estimation, is particularly useful in reducing inventory costs in cases where the limited historical data offer little useful information for forecasting. The BVAR technique was effective in improving forecast accuracy and reducing inventory costs in two of the three cases tested. In the third case, unrestricted VAR and exponential smoothing produced the lowest experimental forecast errors and computed inventory costs. Furthermore, this research illustrates that improvements in demand forecasting can provide better cost reductions than relying on stochastic inventory models to provide cost reductions.     

A network flow model for biclustering via optimal re-ordering of data matrices

The analysis of large-scale data sets using clustering techniques arises in many different disciplines and has important applications. Most traditional clustering techniques require heuristic methods for finding good solutions and produce suboptimal clusters as a result. In this article, we present a rigorous biclustering approach, OREO, which is based on the Optimal RE-Ordering of the rows and columns of a data matrix. The physical permutations of the rows and columns are accomplished via a network flow model according to a given objective function. This optimal re-ordering model is used in an iterative framework where cluster boundaries in one dimension are used to partition and re-order the other dimensions of the corresponding submatrices. The performance of OREO is demonstrated on metabolite concentration data to validate the ability of the proposed method and compare it to existing clustering methods.     

A Decision Criterion for the Optimal Number of Clusters in Hierarchical Clustering

Clustering has been widely used to partition data into groups so that the degree of association is high among members of the same group and low among members of different groups. Though many effective and efficient clustering algorithms have been developed and deployed, most of them still suffer from the lack of automatic or online decision for optimal number of clusters. In this paper, we define clustering gain as a measure for clustering optimality, which is based on the squared error sum as a clustering algorithm proceeds. When the measure is applied to a hierarchical clustering algorithm, an optimal number of clusters can be found. Our clustering measure shows good performance producing intuitively reasonable clustering configurations in Euclidean space according to the evidence from experimental results. Furthermore, the measure can be utilized to estimate the desired number of clusters for partitional clustering methods as well. Therefore, the clustering gain measure provides a promising technique for achieving a higher level of quality for a wide range of clustering methods.     

Hybrid evolutionary algorithms in a SVR traffic flow forecasting model

Accurate urban traffic flow forecasting is critical to intelligent transportation system developments and implementations, thus, it has been one of the most important issues in the research on road traffic congestion. Due to complex nonlinear data pattern of the urban traffic flow, there are many kinds of traffic flow forecasting techniques in literature, thus, it is difficult to make a general conclusion which forecasting technique is superior to others. Recently, the support vector regression model (SVR) has been widely used to solve nonlinear regression and time series problems. This investigation presents a SVR traffic flow forecasting model which employs the hybrid genetic algorithm-simulated annealing algorithm (GA-SA) to determine its suitable parameter combination. Additionally, a numerical example of traffic flow data from northern Taiwan is used to elucidate the forecasting performance of the proposed SVRGA-SA model. The forecasting results indicate that the proposed model yields more accurate forecasting results than the seasonal autoregressive integrated moving average (SARIMA), back-propagation neural network (BPNN), Holt-Winters (HW) and seasonal Holt-Winters (SHW) models. Therefore, the SVRGA-SA model is a promising alternative for forecasting traffic flow.     

Model-based clustering of time series in group-specific functional subspaces

This work develops a general procedure for clustering functional data which adapts the clustering method high dimensional data clustering (HDDC), originally proposed in the multivariate context. The resulting clustering method, called funHDDC, is based on a functional latent mixture model which fits the functional data in group-specific functional subspaces. By constraining model parameters within and between groups, a family of parsimonious models is exhibited which allow to fit onto various situations. An estimation procedure based on the EM algorithm is proposed for determining both the model parameters and the group-specific functional subspaces. Experiments on real-world datasets show that the proposed approach performs better or similarly than classical two-step clustering methods while providing useful interpretations of the groups and avoiding the uneasy choice of the discretization technique. In particular, funHDDC appears to always outperform HDDC applied on spline coefficients.     

Clustering reduced interval data using Hausdorff distance

Summary  In the last decade, factorial and clustering techniques have been developed to analyze multidimensional interval data (MIDs). In classic data analysis, PCA and clustering of the most significant components are usually performed to extract cluster structure from data. The clustering of the projected data is then performed, once the noise is filtered out, in a subspace generated by few orthogonal variables. In the framework of interval data analysis, we propose the same strategy. Several computational questions arise from this generalization. First of all, the representation of data onto a factorial subspace: in classic data analysis projected points remain points, but projected MIDs do not remains MIDs. Further, the choice of a distance between the represented data: many distances between points can be computed, few distances between convex sets of points are defined. We here propose optimized techniques for representing data by convex shapes, for computing the Hausdorff distance between convex shapes, based on an L ₂ norm, and for performing a hierarchical clustering of projected data.     

K-Harmonic means data clustering with tabu-search method

Clustering is a popular data analysis and data mining technique. Since clustering problem have NP-complete nature, the larger the size of the problem, the harder to find the optimal solution and furthermore, the longer to reach a reasonable results. A popular technique for clustering is based on K-means such that the data is partitioned into K clusters. In this method, the number of clusters is predefined and the technique is highly dependent on the initial identification of elements that represent the clusters well. A large area of research in clustering has focused on improving the clustering process such that the clusters are not dependent on the initial identification of cluster representation. Another problem about clustering is local minimum problem. Although studies like K-Harmonic means clustering solves the initialization problem trapping to the local minima is still a problem of clustering. In this paper we develop a new algorithm for solving this problem based on a tabu search technique—Tabu K-Harmonic means (TabuKHM). The experiment results on the Iris and the other well known data, illustrate the robustness of the TabuKHM clustering algorithm.     

Comparative performance of the FSCL neural net and K-means algorithm for market segmentation

Given the success of neural networks in a variety of applications in engineering, such as speech and image quantization, it is natural to consider its application to similar problems in other domains. A related problem that arises in business is market segmentation for which clustering techniques are used. In this paper, we explore the ability of a specific neural network, namely the Frequency-Sensitive Competitive Learning Algorithm (FSCL), to cluster data for developing strategic marketing decisions. To this end, we investigate the comparative performance of FSCL vis-à-vis the K-means clustering technique. A cluster analysis conducted on brand choice data for the coffee category revealed that the two methodologies resulted in widely differing cluster solutions. In an effort to address the dispute over the appropriate methodology, a comparative performance investigation was undertaken using simulated data with known cluster solutions in a fairly large experimental design to mimic varying data quality to reflect data collection and measurement error. Based on the results of these studies, it is observed that a combination of the two methodologies, wherein the results of the FSCL network are input as seeds to the K-means, seems to provide more managerially insightful segmentation schemes.     

The Application of Kernel Smoothing to Time Series Data

There are already a lot of models to fit a set of stationary time series, such as AR, MA, and ARMA models. For the non-stationary data, an ARIMA or seasonal ARIMA models can be used to fit the given data. Moreover, there are also many statistical softwares that can be used to build a stationary or non-stationary time series model for a given set of time series data, such as SAS, SPLUS, etc. However, some statistical softwares wouldn＇t work well for small samples with or without missing data, especially for small time series data with seasonal trend. A nonparametric smoothing technique to build a forecasting model for a given small seasonal time series data is carried out in this paper. And then, both the method provided in this paper and that in SAS package are applied to the modeling of international airline passengers data respectively, the comparisons between the two methods are done afterwards. The results of the comparison show us the method provided in this paper has superiority over SAS＇s method.     

Determination of lockbox collection points via simulated annealing

This research presents a heuristic to solve the lockbox location problem via a search-based technique known as simulated annealing. In the past, more traditional mathematical programming techniques have been used to address this problem, but with limited success due to its combinatorial nature. Because simulated annealing is a search-based technique, an optimal solution is not guaranteed, but past research has demonstrated that search-based heuristics can provide reasonable solutions without the difficulties associated with the more traditional formulations. In this paper, the simulated annealing methodology is used to solve a large lockbox location problem at several differing levels of cost. The results compare favourably to solutions obtained from a K-means clustering heuristic.     

Application of honey-bee mating optimization algorithm on clustering

Cluster analysis is one of attractive data mining technique that use in many fields. One popular class of data clustering algorithms is the center based clustering algorithm. K-means used as a popular clustering method due to its simplicity and high speed in clustering large datasets. However, K-means has two shortcomings: dependency on the initial state and convergence to local optima and global solutions of large problems cannot found with reasonable amount of computation effort. In order to overcome local optima problem lots of studies done in clustering. Over the last decade, modeling the behavior of social insects, such as ants and bees, for the purpose of search and problem solving has been the context of the emerging area of swarm intelligence. Honey-bees are among the most closely studied social insects. Honey-bee mating may also be considered as a typical swarm-based approach to optimization, in which the search algorithm is inspired by the process of marriage in real honey-bee. Honey-bee has been used to model agent-based systems. In this paper, we proposed application of honeybee mating optimization in clustering (HBMK-means). We compared HBMK-means with other heuristics algorithm in clustering, such as GA, SA, TS, and ACO, by implementing them on several well-known datasets. Our finding shows that the proposed algorithm works than the best one.     

An improved clustering method based on biological visual models

A clustering methodology based on biological visual models that imitates how humans visually cluster data by spatially associating patterns has been recently proposed. The method is based on Cellular Neural Networks and some resolution adjustments. The Cellular Neural Network rebuilds low-density areas while different resolutions find the best clustering option. The algorithm has demonstrated good performance compared to other clustering techniques. However, its main drawbacks correspond to its inability to operate with more than two-dimensional data sets and the computational time required for the resolution adjustment mechanism. This paper proposes a new version of this clustering methodology to solve such flaws. In the new approach, a pre-processing stage is incorporated featuring a Self-Organization Map that maps complex high-dimensional relations into a reduced lattice yet preserving the topological organization of the initial data set. This reduced representation is employed as the two-dimensional data set for further processing. In the new version, the resolution adjustment process is also accelerated through the use of an optimization method that combines the Hill-Climbing and the Random Search techniques. By incorporating such mechanisms rather than evaluating all possible resolutions, the optimization strategy finds the best resolution for a clustering problem by using a limited number of iterations. The proposed approach has been evaluated, considering several two-dimensional and high-dimensional datasets. Experimental evidence exhibits that the proposed algorithm performs the clustering task over complex problems delivering a 46% faster on average than the original method. The approach is also compared to other popular clustering techniques reported in the literature. Computational experiments demonstrate competitive results in comparison to other algorithms in terms of accuracy and robustness.