Computationally Efficient Methods for MDL-Optimal Density Estimation and Data Clustering

The Minimum Description Length (MDL) principle is a general, well-founded theoretical formalization of statistical modeling. The most important notion of MDL is the stochastic complexity, which can be interpreted as the shortest description length of a given sample of data relative to a model class. The exact definition of the stochastic complexity has gone through several evolutionary steps. The latest instantation is based on the so-called Normalized Maximum Likelihood (NML) distribution which has been shown to possess several important theoretical properties. However, the applications of this modern version of the MDL have been quite rare because of computational complexity problems, i.e., for discrete data, the definition of NML involves an exponential sum, and in the case of continuous data, a multi-dimensional integral usually infeasible to evaluate or even approximate accurately. In this doctoral dissertation, we present mathematical techniques for computing NML efficiently for some model families involving discrete data. We also show how these techniques can be used to apply MDL in two practical applications: histogram density estimation and clustering of multi-dimensional data.

Clustering Users of Online Content Service

Online content services can greatly benefit from personalisation features that enable delivery of content that is suited to each user's specific interests. This thesis presents a system that applies text analysis and user modeling techniques in an online news service for the purpose of personalisation and user interest analysis. The system creates a detailed thematic profile for each content item and observes user's actions towards content items to learn user's preferences. A handcrafted taxonomy of concepts, or ontology, is used in profile formation to extract relevant concepts from the text. User preference learning is automatic and there is no need for explicit preference settings or ratings from the user. Learned user profiles are segmented into interest groups using clustering techniques with the objective of providing a source of information for the service provider. Some theoretical background for chosen techniques is presented while the main focus is in finding practical solutions to some of the current information needs, which are not optimally served with traditional techniques.

Feature selection and the concept of immediate neighborhood in the context of clustering techniques

The concept of feature selection in a nonparametric unsupervised learning environment is practically undeveloped because no true measure for the effectiveness of a feature exists in such an environment. The lack of a feature selection phase preceding the clustering process seriously affects the reliability of such learning. New concepts such as significant features, level of significance of features, and immediate neighborhood are introduced which result in meeting implicitly the need for feature slection in the context of clustering techniques.

An innovative clustering technique for unsupervized learning in the context of remotely sensed earth resources data analysis

A new clustering technique, based on the concept of immediato neighbourhood, with a novel capability to self-learn the number of clusters expected in the unsupervized environment, has been developed. The method compares favourably with other clustering schemes based on distance measures, both in terms of conceptual innovations and computational economy. Test implementation of the scheme using C-l flight line training sample data in a simulated unsupervized mode has brought out the efficacy of the technique. The technique can easily be implemented as a front end to established pattern classification systems with supervized learning capabilities to derive unified learning systems capable of operating in both supervized and unsupervized environments. This makes the technique an attractive proposition in the context of remotely sensed earth resources data analysis wherein it is essential to have such a unified learning system capability.

Deploying speaker verification techniques to vision-based RPA detect and avoid

Detect and Avoid (DAA) technology is widely acknowledged as a critical enabler for unsegregated Remote Piloted Aircraft (RPA) operations, particularly Beyond Visual Line of Sight (BVLOS). Image-based DAA, in the visible spectrum, is a promising technological option for addressing the challenges DAA presents. Two impediments to progress for this approach are the scarcity of available video footage to train and test algorithms, in conjunction with testing regimes and specifications which facilitate repeatable, statistically valid, performance assessment. This paper includes three key contributions undertaken to address these impediments. In the first instance, we detail our progress towards the creation of a large hybrid collision and near-collision encounter database. Second, we explore the suitability of techniques employed by the biometric research community (Speaker Verification and Language Identification), for DAA performance optimisation and assessment. These techniques include Detection Error Trade-off (DET) curves, Equal Error Rates (EER), and the Detection Cost Function (DCF). Finally, the hybrid database and the speech-based techniques are combined and employed in the assessment of a contemporary, image based DAA system. This system includes stabilisation, morphological filtering and a Hidden Markov Model (HMM) temporal filter.

Aircraft trajectory clustering techniques using circular statistics

This paper presents a statistical aircraft trajectory clustering approach aimed at discriminating between typical manned and expected unmanned traffic patterns. First, a resampled version of each trajectory is modelled using a mixture of Von Mises distributions (circular statistics). Second, the remodelled trajectories are globally aligned using tools from bioinformatics. Third, the alignment scores are used to cluster the trajectories using an iterative k-medoids approach and an appropriate distance function. The approach is then evaluated using synthetically generated unmanned aircraft flights combined with real air traffic position reports taken over a sector of Northern Queensland, Australia. Results suggest that the technique is useful in distinguishing between expected unmanned and manned aircraft traffic behaviour, as well as identifying some common conventional air traffic patterns.

Two-level k-means clustering algorithm for k-tau relationship establishment and linear-time classification

Partitional clustering algorithms, which partition the dataset into a pre-defined number of clusters, can be broadly classified into two types: algorithms which explicitly take the number of clusters as input and algorithms that take the expected size of a cluster as input. In this paper, we propose a variant of the k-means algorithm and prove that it is more efficient than standard k-means algorithms. An important contribution of this paper is the establishment of a relation between the number of clusters and the size of the clusters in a dataset through the analysis of our algorithm. We also demonstrate that the integration of this algorithm as a pre-processing step in classification algorithms reduces their running-time complexity.

RACK: RApid Clustering using K-means algorithm

The k-means algorithm is an extremely popular technique for clustering data. One of the major limitations of the k-means is that the time to cluster a given dataset D is linear in the number of clusters, k. In this paper, we employ height balanced trees to address this issue. Specifically, we make two major contributions, (a) we propose an algorithm, RACK (acronym for RApid Clustering using k-means), which takes time favorably comparable with the fastest known existing techniques, and (b) we prove an expected bound on the quality of clustering achieved using RACK. Our experimental results on large datasets strongly suggest that RACK is competitive with the k-means algorithm in terms of quality of clustering, while taking significantly less time.

Intent Based Clustering of Search Engine Query Log

The keyword based search technique suffers from the problem of synonymic and polysemic queries. Current approaches address only theproblem of synonymic queries in which different queries might have the same information requirement. But the problem of polysemic queries,i.e., same query having different intentions, still remains unaddressed. In this paper, we propose the notion of intent clusters, the members of which will have the same intention. We develop a clustering algorithm that uses the user session information in query logs in addition to query URL entries to identify cluster of queries having the same intention. The proposed approach has been studied through case examples from the actual log data from AOL, and the clustering algorithm is shown to be successful in discerning the user intentions.

Clustering kinetics in aluminium-silver alloys

Resistometric studies of isochronal and isothermal annealing of an Al-0.64 at.% Ag alloy have given a value of 0.13 ± 0.02 eV for the silver-vacancy binding energy and 0.55 ± 0.03 eV for the migration energy of solute atoms.

Clustering phenomena in Al-4.4 at. % Zn alloy with 0.03 and 0.08 at. % Ag additions

The influence of 0.03 and 0.08 at. % Ag additions on the clustering of Zn atoms in an Al-4.4 at. % Zn alloy has been studied by resistometry. The effect of quenching and ageing temperatures shows that the ageing-ratio method of calculating the vacancy-solute atom binding energy is not applicable to these alloys. Zone-formation in Al-Zn is unaffected by Ag additions, but the zone-reversion process seems to be influenced. Apparent vacancy-formation energies in the binary and ternary alloys have been used to evaluate the v-Ag atom binding energy as 0.21 eV. It is proposed that, Ag and Zn being similar in size, the relative vacancy binding results from valency effects, and that in Al-Zn-Ag alloys clusters of Zn and Ag may form simultaneously, unaffected by the presence of each other. © 1970 Chapman and Hall Ltd.

Clustering and solute-vacancy binding energies in Al-4.4% Zn alloy with 0.01% ternary additions

Isochronal and isothermal ageing experiments have been carried out to determine the influence of 0.01 at. % addition of a second solute on the clustering rate in the quenched Al-4,4 a/o Zn alloy. The influence of quenching and ageing temperatures has been interpreted to obtain the apparent vacancy formation and vacancy migration energies in the various ternary alloys. Using a vacancy-aided clustering model the following values of binding free energy have been evaluated: Ce-0.18; Dy-0.24; Fe-0.18; Li-0.25; Mn-0.27; Nb-0.18; Pt-0.23; Sb-0.21; Si-0.30; Y-0.25; and Yb-0.23 (± 0.02 eV). These binding energy values refer to that between a solute atom and a single vacancy. The values of vacancy migration energy (c. 0.4 eV) and the experimental activation energy for solute diffusion (c. 1.1 eV) are unaffected by the presence of the ternary atoms in the Al-Zn alloy.

Resistometric studies of solute-vacancy interactions and clustering kinetics in an FCC matrix [AlZn Alloy with Ag, Ce, Dy, Li, Nb, Pt, Sb, Y, or Yb]

Al-4.4 a/oZn and Al-4.4 a/oZn with Ag, Ce, Dy, Li, Nb, Pt, Y, or Yb, alloys have been investigated by resistometry with a view to study the solute-vacancy interactions and clustering kinetics in these alloys. Solute-vacancy binding energies have been evaluated for all these elements by making use of appropriate methods of evaluation. Ag and Dy additions yield some interesting results and these have been discussed in the thesis. Solute-vacancy binding energy values obtained here have been compared with other available values and discussed. A study of the type of interaction between vacancies and solute atoms indicates that the valency effect is more predominant than the elastic effect.