URBAN CRIME ANALYSIS THROUGH AREAL CATEGORIZED MULTIVARIATE ASSOCIATIONS MINING

As geospatial data grows explosively, there is a great demand for the incorporation of data mining techniques into a geospatial context. Association rules mining is a core technique in data mining and is a solid candidate for the associative analysis of large geospatial databases. In this article, we propose a geospatial knowledge discovery framework for automating the detection of multivariate associations based on a given areal base map. We investigate a series of geospatial preprocessing steps involving data conversion and classification so that the traditional Boolean and quantitative association rules mining can be applied. Our framework has been integrated into GISs using a dynamic link library to allow the automation of both the preprocessing and data mining phases to provide greater ease of use for users. Experiments with real-crime datasets quickly reveal interesting frequent patterns and multivariate associations, which demonstrate the robustness and efficiency of our approach.     

Multi-density urban hotspots detection in smart cities: A data-driven approach and experiments

The detection of city hotspots from geo-referenced urban data is a valuable knowledge support for planners, scientists, and policymakers. However, the application of classic density-based clustering algorithms on multi-density data can produce inaccurate results. Since metropolitan cities are heavily characterized by variable densities, multi-density clustering seems to be more appropriate to discover city hotspots. This paper presents CHD (City Hotspot Detector), a multi-density approach to discover urban hotspots in a city, by reporting an extensive comparative analysis with three classic density-based clustering algorithms, on both state-of-the-art and real-world datasets. The comparative experimental evaluation in an urban scenario shows that the proposed multi-density algorithm, enhanced by an additional rolling moving average technique, detects higher quality city hotspots than other classic density-based approaches proposed in literature.     

GAC-GEO: a generic agglomerative clustering framework for geo-referenced datasets

Major challenges of clustering geo-referenced data include identifying arbitrarily shaped clusters, properly utilizing spatial information, coping with diverse extrinsic characteristics of clusters and supporting region discovery tasks. The goal of region discovery is to identify interesting regions in geo-referenced datasets based on a domain expert’s notion of interestingness. Almost all agglomerative clustering algorithms only focus on the first challenge. The goal of the proposed work is to develop agglomerative clustering frameworks that deal with all four challenges. In particular, we propose a generic agglomerative clustering framework for geo-referenced datasets (GAC-GEO) generalizing agglomerative clustering by allowing for three plug-in components. GAC-GEO agglomerates neighboring clusters maximizing a plug-in fitness function that capture the notion of interestingness of clusters. It enhances typical agglomerative clustering algorithms in two ways: fitness functions support task-specific clustering, whereas generic neighboring relationships increase the number of merging candidates. We also demonstrate that existing agglomerative clustering algorithms can be considered as specific cases of GAC-GEO. We evaluate the proposed framework on an artificial dataset and two real-world applications involving region discovery. The experimental results show that GAC-GEO is capable of identifying arbitrarily shaped hotspots for different data mining tasks.     

DBCURE-MR: An efficient density-based clustering algorithm for large data using MapReduce

Clustering is a useful data mining technique which groups data points such that the points within a single group have similar characteristics, while the points in different groups are dissimilar. Density-based clustering algorithms such as DBSCAN and OPTICS are one kind of widely used clustering algorithms. As there is an increasing trend of applications to deal with vast amounts of data, clustering such big data is a challenging problem. Recently, parallelizing clustering algorithms on a large cluster of commodity machines using the MapReduce framework have received a lot of attention.In this paper, we first propose the new density-based clustering algorithm, called DBCURE, which is robust to find clusters with varying densities and suitable for parallelizing the algorithm with MapReduce. We next develop DBCURE-MR, which is a parallelized DBCURE using MapReduce. While traditional density-based algorithms find each cluster one by one, our DBCURE-MR finds several clusters together in parallel. We prove that both DBCURE and DBCURE-MR find the clusters correctly based on the definition of density-based clusters. Our experimental results with various data sets confirm that DBCURE-MR finds clusters efficiently without being sensitive to the clusters with varying densities and scales up well with the MapReduce framework.     

A dissimilarity function for geospatial polygons

Similarity plays an important role in many data mining tasks and information retrieval processes. Most of the supervised, semi-supervised, and unsupervised learning algorithms depend on using a dissimilarity function that measures the pair-wise similarity between the objects within the dataset. However, traditionally most of the similarity functions fail to adequately treat all the spatial attributes of the geospatial polygons due to the incomplete quantitative representation of structural and topological information contained within the polygonal datasets. In this paper, we propose a new dissimilarity function known as the polygonal dissimilarity function (PDF) that comprehensively integrates both the spatial and the non-spatial attributes of a polygon to specifically consider the density, distribution, and topological relationships that exist within the polygonal datasets. We represent a polygon as a set of intrinsic spatial attributes, extrinsic spatial attributes, and non-spatial attributes. Using this representation of the polygons, PDF is defined as a weighted function of the distance between two polygons in the different attribute spaces. In order to evaluate our dissimilarity function, we compare and contrast it with other distance functions proposed in the literature that work with both spatial and non-spatial attributes. In addition, we specifically investigate the effectiveness of our dissimilarity function in a clustering application using a partitional clustering technique (e.g. \(k\) -medoids) using two characteristically different sets of data: (a) Irregular geometric shapes determined by natural processes, i.e., watersheds and (b) semi-regular geometric shapes determined by human experts, i.e., counties.     

一种基于数据垂直划分的分布式密度聚类算法

聚类分析是数据挖掘领域的一项重要研究课题,对大数据集的聚类更以其数据量大、噪声数据多等而成为一个难点.针对数据垂直划分的情况,提出连通点集及局部噪声点集等概念.在分析局部噪声点集与全局噪声点集以及局部连通点集与全局连通点集关系的基础上,对全局噪声点进行有效过滤,进一步设计闭三角链表结构存储各个结点的聚类中间结果,提出了基于密度的分布式聚类算法DDBSCAN.理论分析和实验结果表明,算法可以有效解决垂直划分的大数据集聚类问题,算法是有效可行的.     

一种基于多视图数据的半监督特征选择和聚类算法

高维数据中许多特征之间互不相关或冗余,这给传统的学习算法带来了巨大的挑战。为了解决该问题,特征选择应运而生。与此同时,许多实际问题中数据存在多个视图而且数据的标签难以获取,多视图学习和半监督学习成为机器学习中的热点问题。本文研究怎样从"部分标签"的多视图数据中选择最大相关最小冗余的特征子集,提出一种基于多视图的半监督特征选择方法。为了剔除冗余和无关的特征,探索蕴含于多视图数据中的互补信息以及每个视图中不同特征之间的冗余关系,并利用少量标签数据蕴含的信息协同未标签数据同时进行特征选择。实验结果验证了本算法能够获得很好的特征选择效果及聚类效果。     

Impact of Fuzzy Normalization on Clustering Microarray Temporal Datasets Using Cuckoo Search

Microarrays have reformed biotechnological research in the past decade. Deciphering the hidden patterns in gene expression data proffers a prodigious preference to strengthen the understanding of functional genomics. The complexity of biological networks with larger volume of genes also increases the challenges of comprehending and interpretation of the resulting mass of data. Clustering addresses these challenges, which is essential in the data mining process to reveal natural structures and identify interesting patterns in the underlying data. The clustering of gene expression data has been proven to be useful in making known the natural structure inherent in gene expression data, understanding gene functions, cellular processes, and molecular functions. Clustering techniques are used to examine gene expression data to extract groups of genes from the tested samples based on a similarity criterion. Subspace clustering broadens the traditional clustering by extracting the groups of genes that are highly correlated in different subspace within the dataset. Mining the temporal patterns in high dimensional data is done with computational effort and thus normalization is needed. In this work, normalization using fuzzy logic is applied to the data before clustering. The multi-objective cuckoo search optimization is implemented to extract co-expressed genes over different subspaces. The proposed methods are applied to the real life temporal gene expression datasets in which it extracts the genes that are responsible for the disease grouped in a same cluster. The experiment results prove that the impact of fuzzy normalization on the dataset improves the clustering.     

一种基于相对密度和决策图的聚类算法

聚类是数据挖掘领域的一个重要研究方向,针对复杂数据集中存在的簇间密度不均匀、聚类形态多样、聚类中心的识别等问题,引入样本点k近邻信息计算样本点的相对密度,借鉴快速搜索和发现密度峰值聚类(CFSFDP)算法的簇中心点识别方法,提出一种基于相对密度和决策图的聚类算法,实现对任意分布形态数据集聚类中心快速、准确地识别和有效聚类.在7类典型测试数据集上的实验结果表明,所提出的聚类算法具有较好的适用性,与经典的DBSCAN算法和CFSFDP等算法相比,在没有显著提高时间复杂度的基础上,聚类效果更好,对不同类型数据集的适应性也更广.     

基于MapReduce的图结构聚类算法

图结构聚类（SCAN）是一种著名的基于密度的图聚类算法。该算法不仅能够找到图中的聚类结构,而且还能发现图中的Hub节点和离群节点。然而,随着图数据规模越来越大,传统的SCAN算法的复杂度为O（m^1.5）（m为图中边的条数）,因此很难处理大规模的图数据。为了解决SCAN算法的可扩展性问题,本文提出了一种新颖的基于MapReduce的海量图结构聚类算法MRSCAN。具体地,我们提出了一种计算核心节点,以及两种合并聚类的MapReduce算法。最后,在多个真实的大规模图数据集上进行实验测试,实验结果验证了算法的准确性、有效性,以及可扩展性。     

基于占空比的聚类算法评价指标研究

基于密度的聚类算法（DBSCAN）是最有效的轨迹数据挖掘方法之一,但基于密度的聚类算法往往受到输入参数选择的限制。在轨迹数据挖掘中,聚类结果不仅受到类内距离和类间距离的影响,还受到聚类中坐标点个数的影响。因此,提出了一种新的基于内外占空比的集群有效性指标来平衡这三个因素,该指标可以自动选择密度聚类的输入参数,并在不同的数据集上形成有效的聚类,优化后的聚类方法可应用于出行者行为轨迹的深度分析和挖掘。实验结果证明,与传统的有效性指标相比,提出的基于占空比的评价指标能够优化输入参数,获得较好的出行者位置信息聚类结果。     

Permutation-test-based clustering method for detection of dynamic patterns in Spatio-temporal datasets

Massive spatio-temporal data have been collected from the earth observation systems for monitoring the changes of natural resources and environment. To find the interesting dynamic patterns embedded in spatio-temporal data, there is an urgent need for detecting spatio-temporal clusters formed by objects with similar attribute values occurring together across space and time. Among different clustering methods, the density-based methods are widely used to detect such spatio-temporal clusters because they are effective for finding arbitrarily shaped clusters and rely on less priori knowledge (e.g. the cluster number). However, a series of user-specified parameters is required to identify high-density objects and to determine cluster significance. In practice, it is difficult for users to determine the optimal clustering parameters; therefore, existing density-based clustering methods typically exhibit unstable performance. To overcome these limitations, a novel density-based spatio-temporal clustering method based on permutation tests is developed in this paper. High-density objects and cluster significance are determined based on statistical information on the dataset. First, the density of each object is defined based on the local variance and a fast permutation test is conducted to identify high-density objects. Then, a proposed two-stage grouping strategy is implemented to group high-density objects and their neighbors; hence, spatio-temporal clusters are formed by minimizing the inhomogeneity increase. Finally, another newly developed permutation test is conducted to evaluate the cluster significance based on the cluster member permutation. Experiments on both simulated and meteorological datasets show that the proposed method exhibits superior performance to two state-of-the-art clustering methods, i.e., ST-DBSCAN and ST-OPTICS. The proposed method can not only identify inherent cluster patterns in spatio-temporal datasets, but also greatly alleviates the difficulty in selecting appropriate clustering parameters.     

Structure revealing techniques based on parallel coordinates plot

Parallel coordinates plot (PCP) is an excellent tool for multivariate visualization and analysis, but it may fail to reveal inherent structures for complex and large datasets. Therefore, polyline clustering and coordinate sorting are inevitable for the accurate data exploration and analysis. In this paper, we propose a suite of novel clustering and dimension sorting techniques in PCP, to reveal and highlight hidden trend and correlation information of polylines. Spectrum theory is first introduced to specifically design clustering and sorting techniques for a clear view of clusters in PCP. We also provide an efficient correlation based sorting technique to optimize the ordering of coordinates to reveal correlated relations, and show how our view-range metrics, generated based on the aggregation constraints, can be used to make a clear view for easy data perception and analysis. Experimental results generated using our framework visually represent meaningful structures to guide the user, and improve the efficiency of the analysis, especially for the complex and noisy data.     

Peculiarity oriented multidatabase mining

Peculiarity rules are a new class of rules which can be discovered by searching relevance among a relatively small number of peculiar data. Peculiarity oriented mining in multiple data sources is different from, and complementary to, existing approaches for discovering new, surprising, and interesting patterns hidden in data. A theoretical framework for peculiarity oriented mining is presented. Within the proposed framework, we give a formal interpretation and comparison of three classes of rules, namely, association rules, exception rules, and peculiarity rules, as well as describe how to mine interesting peculiarity rules in multiple databases.     

Time-focused clustering of trajectories of moving objects

Spatio-temporal, geo-referenced datasets are growing rapidly, and will be more in the near future, due to both technological and social/commercial reasons. From the data mining viewpoint, spatio-temporal trajectory data introduce new dimensions and, correspondingly, novel issues in performing the analysis tasks. In this paper, we consider the clustering problem applied to the trajectory data domain. In particular, we propose an adaptation of a density-based clustering algorithm to trajectory data based on a simple notion of distance between trajectories. Then, a set of experiments on synthesized data is performed in order to test the algorithm and to compare it with other standard clustering approaches. Finally, a new approach to the trajectory clustering problem, called temporal focussing, is sketched, having the aim of exploiting the intrinsic semantics of the temporal dimension to improve the quality of trajectory clustering. The authors are members of the Pisa KDD Laboratory, a joint research initiative of ISTI-CNR and the University of Pisa: .     

A genetic-fuzzy mining approach for items with multiple minimum supports

Data mining is the process of extracting desirable knowledge or interesting patterns from existing databases for specific purposes. Mining association rules from transaction data is most commonly seen among the mining techniques. Most of the previous mining approaches set a single minimum support threshold for all the items and identify the relationships among transactions using binary values. In the past, we proposed a genetic-fuzzy data-mining algorithm for extracting both association rules and membership functions from quantitative transactions under a single minimum support. In real applications, different items may have different criteria to judge their importance. In this paper, we thus propose an algorithm which combines clustering, fuzzy and genetic concepts for extracting reasonable multiple minimum support values, membership functions and fuzzy association rules from quantitative transactions. It first uses the k-means clustering approach to gather similar items into groups. All items in the same cluster are considered to have similar characteristics and are assigned similar values for initializing a better population. Each chromosome is then evaluated by the criteria of requirement satisfaction and suitability of membership functions to estimate its fitness value. Experimental results also show the effectiveness and the efficiency of the proposed approach.     

文本挖掘及其应用

文本挖掘是指利用数据挖掘技术，从大量的文本数据中提取感兴趣的、潜在的有用模式和隐藏的信息。本文详细阐述了文本挖掘的功能、文本挖掘的过程、文本挖掘的应用，并在文章最后介绍了文本挖掘的工具及演示实例。     

文本挖掘技术研究进展

文本挖掘是一个对具有丰富语义的文本进行分析从而理解其所包含的内容和意义的过程,已经成为数据挖掘中一个日益流行而重要的研究领域。首先给出了文本挖掘的定义和框架,对文本挖掘中预处理、文本摘要、文本分类、聚类、关联分析及可视化技术进行了详尽的分析,并归纳了最新的研究进展。最后指出了文本挖掘在知识发现中的重要意义,展望了文本挖掘在信息技术中的发展前景。     

Finding density-based subspace clusters in graphs with feature vectors

Data sources representing attribute information in combination with network information are widely available in today??s applications. To realize the full potential for knowledge extraction, mining techniques like clustering should consider both information types simultaneously. Recent clustering approaches combine subspace clustering with dense subgraph mining to identify groups of objects that are similar in subsets of their attributes as well as densely connected within the network. While those approaches successfully circumvent the problem of full-space clustering, their limited cluster definitions are restricted to clusters of certain shapes. In this work we introduce a density-based cluster definition, which takes into account the attribute similarity in subspaces as well as a local graph density and enables us to detect clusters of arbitrary shape and size. Furthermore, we avoid redundancy in the result by selecting only the most interesting non-redundant clusters. Based on this model, we introduce the clustering algorithm DB-CSC, which uses a fixed point iteration method to efficiently determine the clustering solution. We prove the correctness and complexity of this fixed point iteration analytically. In thorough experiments we demonstrate the strength of DB-CSC in comparison to related approaches.     

VDBSCAN:变密度聚类算法

传统的密度聚类算法不能识别并聚类多个不同密度的簇。对此提出了变密度聚类算法VDBSCAN,针对密度不稳定的数据集,可有效识别并同时聚类不同密度的簇,避免合并和遗漏。VDBSCAN算法的基本思想是:根据k-dist图和DK分析,对数据集中的不同密度层次自动选择一组Eps值,分别调用DBSCAN算法。不同的Eps值,能够找到不同密度的簇。4个二维数据集实验验证了VDB-SCAN算法的有效性,表明VDBSCAN算法可以有效地聚类密度不均匀的数据集,且参数Eps的自动选择方法也是有效的和健壮的。