Enhancing minimum spanning tree-based clustering by removing density-based outliers

Traditional minimum spanning tree-based clustering algorithms only make use of information about edges contained in the tree to partition a data set. As a result, with limited information about the structure underlying a data set, these algorithms are vulnerable to outliers. To address this issue, this paper presents a simple while efficient MST-inspired clustering algorithm. It works by finding a local density factor for each data point during the construction of an MST and discarding outliers, i.e., those whose local density factor is larger than a threshold, to increase the separation between clusters. This algorithm is easy to implement, requiring an implementation of iDistance as the only k-nearest neighbor search structure. Experiments performed on both small low-dimensional data sets and large high-dimensional data sets demonstrate the efficacy of our method.     

Fast Dimension-based Partitioning and Merging clustering algorithm

Clustering multi-dense large scale high dimensional numeric datasets is a challenging task duo to high time complexity of most clustering algorithms. Nowadays, data collection tools produce a large amount of data. So, fast algorithms are vital requirement for clustering such data. In this paper, a fast clustering algorithm, called Dimension-based Partitioning and Merging (DPM), is proposed. In DPM, first, data is partitioned into small dense volumes during the successive processing of dataset dimensions. Then, noise is filtered out using dimensional densities of the generated partitions. Finally, merging process is invoked to construct clusters based on partition boundary data samples. DPM algorithm automatically detects the number of data clusters based on three insensitive tuning parameters which decrease the burden of its usage. Performance evaluation of the proposed algorithm using different datasets shows its fastness and accuracy compared to other clustering competitors.     

基于MapReduce并行化计算的大数据聚类算法

面对大数据规模庞大且计算复杂等问题,基于MapReduce框架采用两阶段渐进式的聚类思想,提出了改进的K-means并行化计算的大数据聚类方法。第一阶段,该算法通过Canopy算法初始化划分聚类中心,从而迅速获取粗精度的聚类中心点;第二阶段,基于MapReduce框架提出了并行化计算方案,使每个数据点围绕其邻近的Canopy中心进行细化的聚类或合并,从而对大数据实现快速、准确地聚类分析。在MapReduce并行框架上进行算法验证,实验结果表明,所提算法能够有效地提升并行计算效率,减少计算时间,并提升大数据的聚类精度。     

Multi-step density-based clustering

Data mining in large databases of complex objects from scientific, engineering or multimedia applications is getting more and more important. In many areas, complex distance measures are first choice but also simpler distance functions are available which can be computed much more efficiently. In this paper, we will demonstrate how the paradigm of multi-step query processing which relies on exact as well as on lower-bounding approximated distance functions can be integrated into the two density-based clustering algorithms DBSCAN and OPTICS resulting in a considerable efficiency boost. Our approach tries to confine itself to ɛ-range queries on the simple distance functions and carries out complex distance computations only at that stage of the clustering algorithm where they are compulsory to compute the correct clustering result. Furthermore, we will show how our approach can be used for approximated clustering allowing the user to find an individual trade-off between quality and efficiency. In order to assess the quality of the resulting clusterings, we introduce suitable quality measures which can be used generally for evaluating the quality of approximated partitioning and hierarchical clusterings. In a broad experimental evaluation based on real-world test data sets, we demonstrate that our approach accelerates the generation of exact density-based clusterings by more than one order of magnitude. Furthermore, we show that our approximated clustering approach results in high quality clusterings where the desired quality is scalable with respect to (w.r.t.) the overall number of exact distance computations. Stefan Brecheisen is a teaching and research assistant in Prof.$ Hans-Peter Kriegel's group. He works in the field of similarity search in spatial objects. Hans-Peter Kriegel is a full professor at the University of Munich and head of the database group since 1991. He studied computer science at the University of Karlsruhe, Germany, and finished his doctoral thesis there in 1976. He has more than 200 publications in international journals and reviewed conference proceedings. His research interests are database systems for complex objects (molecular biology, medical science, multimedia, CAD, etc.), in particular query processing, similarity search, high-dimensional index structures, as well as knowledge discovery in databases and data mining. Martin Pfeifle is a teaching and research assistant in Prof.$ Hans-Peter Kriegel's group. He finished his doctoral thesis on “Spatial Database Support for Virtual Engineering” in the spring of 2004.     

Performance evaluation of density-based clustering methods

With the development of the World Wide Web, document clustering is receiving more and more attention as an important and fundamental technique for unsupervised document organization, automatic topic extraction, and fast information retrieval or filtering. A good document clustering approach can assist computers in organizing the document corpus automatically into a meaningful cluster hierarchy for efficient browsing and navigation, which is very valuable for complementing the deficiencies of traditional information retrieval technologies. In this paper, we study the performance of different density-based criterion functions, which can be classified as internal, external or hybrid, in the context of partitional clustering of document datasets. In our study, a weight was assigned to each document, which defined its relative position in the entire collection. To show the efficiency of the proposed approach, the weighted methods were compared to their unweighted variants. To verify the robustness of the proposed approach, experiments were conducted on datasets with a wide variety of numbers of clusters, documents and terms. To evaluate the criterion functions, we used the WebKb, Reuters-21578, 20Newsgroups-18828, WebACE and TREC-5 datasets, as they are currently the most widely used benchmarks in document clustering research. To evaluate the quality of a clustering solution, a wide spectrum of indices, three internal validity indices and seven external validity indices, were used. The internal validity indices were used for evaluating the within-cluster scatter and between cluster separations. The external validity indices were used for comparing the clustering solutions produced by the proposed criterion functions with the “ground truth” results. Experiments showed that our approach significantly improves clustering quality. In this paper, we developed a modified differential evolution (DE) algorithm to optimize the criterion functions. This modification accelerates the convergence of DE and, unlike the basic DE algorithm, guarantees that the received solution will be feasible.     

面向海量数据的K-means聚类优化算法

针对集中式系统框架难以进行海量数据聚类分析的问题,提出基于MapReduce的K-means聚类优化算法。该算法运用MapReduce并行编程框架,引入Canopy聚类,优化K-means算法初始中心的选取,改进迭代过程中通信和计算模式。实验结果表明该算法能够有效地改善聚类质量,具有较高的执行效率以及优良的扩展性,适合用于海量数据的聚类分析。     

MPM: a hierarchical clustering algorithm using matrix partitioning method for non-numeric data

Clustering has been widely adopted in numerous applications, including pattern recognition, data analysis, image processing, and market research. When performing data mining, traditional clustering algorithms which use distance-based measurements to calculate the difference between data are unsuitable for non-numeric attributes such as nominal, Boolean, and categorical data. Applying an unsuitable similarity measurement in clustering may cause some valuable information embedded in the data attributes to be lost, and hence low quality clusters will be created. This paper proposes a novel hierarchical clustering algorithm, referred to as MPM, for the clustering of non-numeric data. The goals of MPM are to retain the data features of interest while effectively grouping data objects into clusters with high intra-similarity and low inter-similarity. MPM achieves these goals through two principal methods: (1) the adoption of a novel similarity measurement which has the ability to capture the “characterized properties” of information, and (2) the application of matrix permutation and matrix participation partitioning to the results of the similarity measurement (constructed in the form of a similarity matrix) in order to assign data to appropriate clusters. This study also proposes a heuristic-based algorithm, the Heuristic_MPM, to reduce the processing times required for matrix permutation and matrix partitioning, which together constitute the bulk of the total MPM execution time. An erratum to this article is available at .     

An efficient hybrid algorithm based on modified imperialist competitive algorithm and K-means for data clustering

Clustering techniques have received attention in many fields of study such as engineering, medicine, biology and data mining. The aim of clustering is to collect data points. The K-means algorithm is one of the most common techniques used for clustering. However, the results of K-means depend on the initial state and converge to local optima. In order to overcome local optima obstacles, a lot of studies have been done in clustering. This paper presents an efficient hybrid evolutionary optimization algorithm based on combining Modify Imperialist Competitive Algorithm (MICA) and K-means (K), which is called K-MICA, for optimum clustering N objects into K clusters. The new Hybrid K-ICA algorithm is tested on several data sets and its performance is compared with those of MICA, ACO, PSO, Simulated Annealing (SA), Genetic Algorithm (GA), Tabu Search (TS), Honey Bee Mating Optimization (HBMO) and K-means. The simulation results show that the proposed evolutionary optimization algorithm is robust and suitable for handling data clustering.     

Squeezer: An efficient algorithm for clustering categorical data

This paper presents a new efficient algorithm for clustering categorical data,Squeezer,which can produce high quality clustering results and at the same time deserve good scalability.The Squeezer algorithm reads each tuple t in sequence,either assigning t to an existing cluster (initially none),or creating t as a new cluster,which is determined by the similarities between t and clusters.Due to its characteristics,the proposed algorithm is extremely suitable for clustering data streams,where given a sequence of points,the objective is to maintain consistently good clustering of the sequence so far,using a small amount of memory and time.Outliers can also be handled efficiently and directly in Squeezer.Experimental results on real-life and synthetic datasets verify the superiority of Squeezer.     

An efficient hyperellipsoidal clustering algorithm for resource-constrained environments

Clustering has been widely used as a fundamental data mining tool for the automated analysis of complex datasets. There has been a growing need for the use of clustering algorithms in embedded systems with restricted computational capabilities, such as wireless sensor nodes, in order to support automated knowledge extraction from such systems. Although there has been considerable research on clustering algorithms, many of the proposed methods are computationally expensive. We propose a robust clustering algorithm with low computational complexity, suitable for computationally constrained environments. Our evaluation using both synthetic and real-life datasets demonstrates lower computational complexity and comparable accuracy of our approach compared to a range of existing methods.     

加速大数据聚类K-means算法的改进

为有效处理大规模数据聚类的问题,提出一种先抽样再用最大最小距离进行K-means并行化聚类的方法。基于抽样的方法避免了聚类陷入局部解中,基于最大最小距离法使得初始聚类中心趋于最优化。大量实验结果表明,无论是在单机环境还是集群环境下,该方法受初始聚类中心的影响降低,提高了聚类的准确性,减少了聚类的迭代次数,降低了聚类的时间。     

TopPI: An efficient algorithm for item-centric mining

In this paper, we introduce item-centric mining, a new semantics for mining long-tailed datasets. Our algorithm, TopPI, finds for each item its top-k most frequent closed itemsets. While most mining algorithms focus on the globally most frequent itemsets, TopPI guarantees that each item is represented in the results, regardless of its frequency in the database.TopPI allows users to efficiently explore Web data, answering questions such as “what are the k most common sets of songs downloaded together with the ones of my favorite artist?”. When processing retail data consisting of 55 million supermarket receipts, TopPI finds the itemset “milk, puff pastry” that appears 10,315 times, but also “frangipane, puff pastry” and “nori seaweed, wasabi, sushi rice” that occur only 1120 and 163 times, respectively. Our experiments with analysts from the marketing department of our retail partner demonstrate that item-centric mining discover valuable itemsets. We also show that TopPI can serve as a building-block to approximate complex itemset ranking measures such as the p-value.Thanks to efficient enumeration and pruning strategies, TopPI avoids the search space explosion induced by mining low support itemsets. We show how TopPI can be parallelized on multi-cores and distributed on Hadoop clusters. Our experiments on datasets with different characteristics show the superiority of TopPI when compared to standard top-k solutions, and to Parallel FP-Growth, its closest competitor.     

基于密度的模糊代表点聚类算法

结合密度聚类和模糊聚类的特点,提出一种基于密度的模糊代表点聚类算法.首先利用密度对数据点成为候选聚类中心点的可能性进行处理,密度越高的点成为聚类中心点的可能性越大;然后利用模糊方法对聚类中心点进行确定;最后通过合并聚类中心点确定最终的聚类中心.所提出算法具有很好的自适应性,能够处理不同形状的聚类问题,无需提前规定聚类个数,能够自动确定真实存在的聚类中心点,可解释性好.通过结合不同聚类方法的优点,最终实现对数据的有效划分.此外,所提出的算法对于聚类数和初始化、处理不同形状的聚类问题以及应对异常值等方面具有较好的鲁棒性.通过在人工数据集和UCI真实数据集上进行实验,表明所提出算法具有较好的聚类性能和广泛的适用性.     

KNN-kernel density-based clustering for high-dimensional multivariate data

Density-based clustering algorithms for multivariate data often have difficulties with high-dimensional data and clusters of very different densities. A new density-based clustering algorithm, called KNNCLUST, is presented in this paper that is able to tackle these situations. It is based on the combination of nonparametric k-nearest-neighbor (KNN) and kernel (KNN-kernel) density estimation. The KNN-kernel density estimation technique makes it possible to model clusters of different densities in high-dimensional data sets. Moreover, the number of clusters is identified automatically by the algorithm. KNNCLUST is tested using simulated data and applied to a multispectral compact airborne spectrographic imager (CASI)_image of a floodplain in the Netherlands to illustrate the characteristics of the method.     

一种基于密度的高效聚类算法

在聚类算法DBSCAN(DensityBasedSpatialClusteringofApplicationswithNoise)的基础上,提出了一种基于密度的高效聚类算法。该算法首先对样本集按某一维排序,然后通过在核心点的邻域外按顺序选择一个未标记的样本点来扩展种子点,以便减少查询次数,降低聚类的时间花费。对样本进行非线性核变换后再进行聚类可以有效地改善聚类的质量。理论分析表明,该算法的时间复杂性接近于线性复杂度。同时测试结果也表明新算法的时间复杂度和聚类质量都显著优于DBSCAN算法。     

基于MapReduce的并行SFLA-FCM聚类算法

模糊C均值算法（Fuzzy C-Means,FCM）是目前应用比较广泛的一种聚类算法。FCM算法的聚类质量依赖于初始聚类中心的选择并且易陷入局部极值,结合混合蛙跳算法（Shuffled Frog Leaping Algorithm,SFLA）较强的搜索能力,提出一种基于MapReduce的并行SFLA-FCM聚类算法。该算法利用SFLA算法的子群内模因信息传递和全局信息交换来搜索高质量的聚类中心,根据MapReduce编程模型设计算法流程,实现并行化,使其具有处理大规模数据集的能力。实验证明,并行SFLA-FCM算法提高了的搜索能力和聚类结果的精度,并且具有良好的加速比和扩展性。     

基于网格密度和局部敏感哈希函数的并行化聚类算法

针对大数据背景下基于划分的聚类算法中存在初始中心敏感,节点间通信开销大以及集群效率低下等问题,提出了基于网格密度和局部敏感哈希函数的PBGDLSH-MR并行化聚类算法。首先,对初始数据集提出网格密度策略(GDS)获取初始中心点,有效避免了随机选取引起的初始中心敏感的问题;其次,提出基于局部敏感哈希函数的数据分区(DP-LSH)用于投射关联性较大的数据对象到同一子数据集中,得到map上的数据分区,并设计相似性度量公式(SI)对数据分区结果进行评价,从而降低了节点间的通信开销;接着设计自适应分组策略(AGS)处理数据分区中数据倾斜的问题,进而有效地提高了集群效率;最后,结合MapReduce计算模型并行挖掘簇中心,生成最终聚类结果。实验结果表明,PBGDLSH-MR算法的聚类效果更佳,同时在大数据环境下能有效地提高并行计算的效率。     

基于密度的K-means算法在轨迹数据聚类中的优化

针对传统的K-means算法无法预先明确聚类数目,对初始聚类中心选取敏感且易受离群孤点影响导致聚类结果稳定性和准确性欠佳的问题,提出一种改进的基于密度的K-means算法。该算法首先基于轨迹数据分布密度和增加轨迹数据关键点密度权值的方式选取高密度的轨迹数据点作为初始聚类中心进行K-means聚类,然后结合聚类有效函数类内类外划分指标对聚类结果进行评价,最后根据评价确定最佳聚类数目和最优聚类划分。理论研究与实验结果表明,该算法能够更好地提取轨迹关键点,保留关键路径信息,且与传统的K-means算法相比,聚类准确性提高了28个百分点,与具有噪声的基于密度的聚类算法相比,聚类准确性提高了17个百分点。所提算法在轨迹数据聚类中具有更好的稳定性和准确性。     

基于MapReduce和改进密度峰值的划分聚类算法

对于基于划分的聚类算法随机选取初始聚类中心导致初始中心敏感,聚类结果不稳定、集群效率低等问题,提出一种基于MapReduce框架和改进的密度峰值的划分聚类算法(based on MapReduce framework and im-proved density peak partition clustering algorithm,MR-IDPACA).首先,通过自然最近邻定义新的局部密度计算方式,将搜索样本密度峰值点作为划分聚类算法的初始聚类中心;其次针对算法在大规模数据下运行时间复杂,提出基于E2LSH(exact Euclidean locality sensitive hashing)的一种分区方法,即KLSH(K of locality sensitive hashing).通过该方法对数据分区后结合MapReduce框架并行搜寻初始聚类中心,有效减少了算法在搜索初始聚类中心时的运行时间;对于MapReduce框架中的数据倾斜问题,提出ME(multistage equilibrium)策略对中间数据进行多段均衡分区,以提升算法运行效率;在MapReduce框架下并行聚类,得到最终聚类结果.实验得出MR-IDPACA算法在单机环境下有着较高的准确率和较强的稳定性,集群性能上也有着较好的加速比和运行时间,聚类效果有所提升.     

Dynamic energy efficient data placement and cluster reconfiguration algorithm for MapReduce framework

With the recent emergence of cloud computing based services on the Internet, MapReduce and distributed file systems like HDFS have emerged as the paradigm of choice for developing large scale data intensive applications. Given the scale at which these applications are deployed, minimizing power consumption of these clusters can significantly cut down operational costs and reduce their carbon footprint—thereby increasing the utility from a provider’s point of view. This paper addresses energy conservation for clusters of nodes that run MapReduce jobs. The algorithm dynamically reconfigures the cluster based on the current workload and turns cluster nodes on or off when the average cluster utilization rises above or falls below administrator specified thresholds, respectively. We evaluate our algorithm using the GridSim toolkit and our results show that the proposed algorithm achieves an energy reduction of 33% under average workloads and up to 54% under low workloads.