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.

Clustering in Concept Association Networks

We view association of concepts as a complex network and present a heuristic for clustering concepts by taking into account the underlying network structure of their associations. Clusters generated from our approach are qualitatively better than clusters generated from the conventional spectral clustering mechanism used for graph partitioning.

Automatic text block separation in document images

Separation of printed text blocks from the non-text areas, containing signatures, handwritten text, logos and other such symbols, is a necessary first step for an OCR involving printed text recognition. In the present work, we compare the efficacy of some feature-classifier combinations to carry out this separation task. We have selected length-nomalized horizontal projection profile (HPP) as the starting point of such a separation task. This is with the assumption that the printed text blocks contain lines of text which generate HPP's with some regularity. Such an assumption is demonstrated to be valid. Our features are the HPP and its two transformed versions, namely, eigen and Fisher profiles. Four well known classifiers, namely, Nearest neighbor, Linear discriminant function, SVM's and artificial neural networks have been considered and efficiency of the combination of these classifiers with the above features is compared. A sequential floating feature selection technique has been adopted to enhance the efficiency of this separation task. The results give an average accuracy of about 96.

Document page layout analysis using Harris corner points

Extraction of text areas from the document images with complex content and layout is one of the challenging tasks. Few texture based techniques have already been proposed for extraction of such text blocks. Most of such techniques are greedy for computation time and hence are far from being realizable for real time implementation. In this work, we propose a modification to two of the existing texture based techniques to reduce the computation. This is accomplished with Harris corner detectors. The efficiency of these two textures based algorithms, one based on Gabor filters and other on log-polar wavelet signature, are compared. A combination of Gabor feature based texture classification performed on a smaller set of Harris corner detected points is observed to deliver the accuracy and efficiency.

Scalable non-linear Support Vector Machine using hierarchical clustering

This paper discusses a method for scaling SVM with Gaussian kernel function to handle large data sets by using a selective sampling strategy for the training set. It employs a scalable hierarchical clustering algorithm to construct cluster indexing structures of the training data in the kernel induced feature space. These are then used for selective sampling of the training data for SVM to impart scalability to the training process. Empirical studies made on real world data sets show that the proposed strategy performs well on large data sets.

Agglomerative clustering using the concept of mutual nearest neighbourhood

A method for determining the mutual nearest neighbours (MNN) and mutual neighbourhood value (mnv) of a sample point, using the conventional nearest neighbours, is suggested. A nonparametric, hierarchical, agglomerative clustering algorithm is developed using the above concepts. The algorithm is simple, deterministic, noniterative, requires low storage and is able to discern spherical and nonspherical clusters. The method is applicable to a wide class of data of arbitrary shape, large size and high dimensionality. The algorithm can discern mutually homogenous clusters. Strong or weak patterns can be discerned by properly choosing the neighbourhood width.

Disaggregative Clustering Using the Concept of Mutual Nearest Neighborhood

A nonparametric, hierarchical, disaggregative clustering algorithm is developed using a novel similarity measure, called the mutual neighborhood value (MNV), which takes into account the conventional nearest neighbor ranks of two samples with respect to each other. The algorithm is simple, noniterative, requires low storage, and needs no specification of the expected number of clusters. The algorithm appears very versatile as it is capable of discerning spherical and nonspherical clusters, linearly nonseparable clusters, clusters with unequal populations, and clusters with lowdensity bridges. Changing of the neighborhood size enables discernment of strong or weak patterns.