A parameter-free, fully-automatic approach to clustering high-dimensional categorical data is proposed. The technique is based on a two-phase iterative procedure, which attempts to improve the overall quality of the whole partition. In the first phase, cluster assignments are given, and a new cluster is added to the partition by identifying and splitting a low-quality cluster. In the second phase, the number of clusters is fixed, and an attempt to optimize cluster assignments is done. On the basis of such features, the algorithm attempts to improve the overall quality of the whole partition and finds clusters in the data, whose number is naturally established on the basis of the inherent features of the underlying data set rather than being previously specified. Furthermore, the approach is parametric to the notion of cluster quality: Here, a cluster is defined as a set of tuples exhibiting a sort of homogeneity. We show how a suitable notion of cluster homogeneity can be defined in the context of high-dimensional categorical data, from which an effective instance of the proposed clustering scheme immediately follows. Experiments on both synthetic and real data prove that the devised algorithm scales linearly and achieves nearly optimal results in terms of compactness and separation.
Urban environments continuously generate larger and larger volumes of data, whose analysis can provide descriptive and predictive models as valuable support to inspire and develop data-driven Smart City applications. To this aim, Big data analysis and machine learning algorithms can play a fundamental role to bring improvements in city policies and urban issues. This paper introduces how Big Data analysis can be exploited to design and develop data-driven smart city services, and provides an overview on the most important Smart City applications, grouped in several categories. Then, it presents three real-case studies showing how data analysis methodologies can provide innovative solutions to deal with smart city issues. The first one is an approach for spatio-temporal crime forecasting (tested on Chicago crime data), the second one is methodology to discover mobility hotsposts and trajectory patterns from GPS data (tested on Beijing taxi traces), the third one is an approach to discover predictive epidemic patterns from mobility and infection data (tested on real COVID-19 data). The presented real-world cases prove that data analytics models can effectively support city managers in tackling smart city challenges and improving urban applications.