Probabilistic topic models, such as latent dirichlet allocation (LDA), are often used to discover hidden semantic structure of a collection of documents. In recent years, various inference algorithms have been developed to cope with learning of topic models, among which Gibbs sampling methods remain a popular choice. In this paper, we aim to improve the inference of topic models based on the Gibbs sampling framework. We extend a state augmentation based Gibbs sampling method by maximizing the replications of latent states, and propose a new generic deterministic inference method, named maximal latent state replication (MAX), for learning of a family of probabilistic topic models. One key benefit of the proposed method lies in the deterministic nature for inference, which may help to improve its running efficiency as well as predictive perplexity. We have conducted extensive experiments on real-life publicly available datasets, and the results have validated that our proposed method MAX significantly outperforms state-of-the-art baselines for inference of existing well-known topic models.

Biclustering is a data mining technique that allows simultaneous clustering of two variables. A common biclustering task for categorical variables is to find ‘heavy’ biclusters, i.e., biclusters with high co-occurrence values. Although algorithms have been proposed to extract heavy biclusters, they provide little information about relative importance of each bicluster, as well as importance of the variables for each bicluster. To address these problems, there have been attempts to apply mixture models using information theory or Bayesian method. Although they are able to rank the biclusters and the variables for each bicluster, they do not target at extracting heavy biclusters. Furthermore, these models constrain the search for biclusters in such a way that every cell in the matrix must participate in some bicluster. We attempt to alleviate these limitations using dual topic models. First of all, we develop a generalized LDA topic model that extracts dual topics, i.e., topics in opposite directions – row- and column-topics. To obtain better topics, it applies mutual reinforcement, i.e., considering column-topics while constructing row-topics, and vice versa. Heavy biclusters, the high co-occurred relationship, are extracted using thresholds. We show that our model Dual Topic to Biclusters (DT2B) is effective in extracting heavy biclusters by experimenting over a simulated data, a text corpus (NIPS author-document) and a microarray gene expression data. Results show that biclusters extracted by DT2B are better.

Extraction of mobility patterns of people in a city helps in urban planning, traffic control, transportation management, etc. We present a demo that shows how to extract interesting individual and collective mobility patterns from mobile phone cellular data. Individual patterns are captured using a next place prediction algorithm that builds different Dynamic Bayesian Network (DBN) models and chooses the best DBN model. Collective patterns are captured by aggregating individual patterns using efficient query processing methods. Each query requires three arguments, i.e., current location cl, current time ct and query time qt. These parameters are varied to capture information at different granularity level resulting in many interesting patterns. Cellular data, although less accurate, irregular and sparser than GPS and less detailed than CDR, is cheap and abundantly available and is used by all sections of people. Demo results show that these shortcomings can be overcome, at least to some extent, by exploiting the underlying repetitive patterns. As part of individual patterns, the system predicts the next place (along with a confidence measure) for a given combination of current location, Time-of-Day and Day-of-week of a user. Collective mobility patterns can start from a planning area or a latlon (with a radius). It visually shows the major destinations along with their intensity. An interesting finding was that planning areas with higher population has higher predictability. The UI system also shows heat maps that show continuous mobility of people. These types of patterns can have significant bearing on urban planning and related applications.

CDR (Call Detail Records) data is more easily available than other network related data (such as GPS data) as most telecommunications service providers (TSPs) maintain such data. By analyzing it one can find mobility patterns of most of the population thus leading to efficient urban planning, disease and traffic control, etc. But its granularity is low as the latitude and longitude (lat-lon) of a cell tower is used as the current location of all mobile phones that are connected to the cell tower at that time. Granularity can range between 10s of metres to several kms depending on population density of a locality. This is one reason why, although there are many existing systems on visualizing mobility of people based on GPS data, there is hardly any existing system for CDR. We develop a Mobility Visualization System (MoVis) for visualizing mobility of people from their CDR records. First of all, given the CDR records of a user, we determine her stay regions (places where she stays for a significant amount of time). Trajectories of phone events (and lat-lon of cell towers) between stay regions are extracted as her trips. Start and end times of a trip are estimated using linear extrapolation. Based on the start and end times, temporal patterns are extracted. Trips with sufficient number of intermediate points are mapped to transport network that consists of train lines, bus routes and expressways. We use Kernel density estimation to visualize the most common path for a given origin and destination. Based on this we create a round-the-clock visualization of mobility of people over the entire city separately for weekdays and weekends. At the end we show the validation results.

In this paper we present methods for mapping trajectories of cell tower latitude-longitudes in mobile phone data to transport network. Compared to other forms of mobile phone data such as GPS traces, this form is the most popular and inexpensive but the least accurate and highly irregular. Unlike some earlier works on this type of data where only long trips are studied, our work is based on everyday transportation inside a city. The problems due to inaccuracy in determining position of a user and irregularity of phone events are felt even more intensely for such small distances. Our approach in processing this data takes into account its repetitive nature, i.e., A typical user makes the same trips every week. Moreover, many users follow the same transport route to go from one place to another. First of all, we defined stay region taking into consideration irregularity of phone events. Then we extracted trajectories between each pair of stay regions as trips. Then, we map these trips to existing transportation network consisting of bus services, train lines, expressways, and their combinations such as bus-train-bus. For a given origin and destination, we create a heat map that shows the most commonly used route. A round-the-clock heat map, both for weekdays and weekends, shows people's mobility at different times of a week. We validate our findings by both direct (sample survey) and indirect (comparison with available statistics) methods.

Knowledge about population distribution of planning areas helps in making urban development decisions. Two important criteria are: "where do people live?" and "where do they work?" In this paper we propose methods to find home and workplaces from mobile network data. Home and work places are essential for discovery of mobility profiles of users. Validation of home and workplace prediction is not straight forward. We validate our methods using correlation with external data. Validation results show that even though a single cellular provider has only a portion of the entire population as its users, distribution of home and work places predicted using its mobile network data match that of government statistics. On the basis of this matching, we can have faith in distributions of more difficult statistics extracted from mobile network data which are difficult to obtain from external sources. We implemented an interactive system to show various distributions such as people living and working in different planning areas, and people working in different job sectors such as manufacturing. Interesting relationships are found by calculating joint distributions, e.g., Where do people, living in a planning area, work, and vice versa. Planning areas are ranked by the average distance traveled from home to work. Another interesting fact we extract is balance. Balance of a planning area is high if people live and work there, it is low if people living in a planning area work in other planning areas. We extend these statistics to regions which consist of many planning areas. The goal of this interactive system is to understand location semantics and mobility of users to aid in making urban development decisions. A video recording with subtitles is uploaded in http://www.youtube.com/watch?v=mo-7-DsCymw.

We present methods to predict and validate home and work places of anonymized users using their mobile network data. Knowledge of home and work place of a user is essential in order to find his (and overall population) mobility profiles. There are many methods that predict home and work places using GPS data. But unlike GPS data, mobile network data using GSM do not provide the exact location of a phone event. We use a novel criterion that combines an extracted feature from mobile data (i.e., Inactivity - no phone event for a given period of time) with open source data about location category % (i.e., Streetdirectory.com) to predict home location. Results show that the new criterion gives better prediction accuracy than inactivity alone. We predict work place using the idea that one goes to her work place on most of the weekdays but rarely on weekends. We validate our methods by comparing against the ground truth obtained from open source data. Validation results show that our proposed methods are about 25% more accurate than existing methods both for home and work place predictions.

RELIEF is a very effective and extremely popular feature selection algorithm developed for the first time in 1992 by Kira and Rendell. Since then it has been modified and expanded in various ways to make it more efficient. But the original RELIEF and all of its expansions are for feature selection over labeled data for classification purposes. To the best of our knowledge, for the first time ever RELIEF is used in this paper as RELIEF-C for unlabeled data to select relevant features for clustering. We modified RELIEF so as to overcome its inherent difficulties in the presence of large number of irrelevant features and/or significant number of noisy tuples. RELIEF-C has several advantages over existing wrapper and filter feature selection methods: (a) it works well in the presence of large amount of noisy tuples, (b) it is robust even when underlying clustering algorithm fails to cluster properly, and (c) it accurately recognizes the relevant features even in the presence of large number of irrelevant features. We compared RELIEF-C with two established feature selection methods for clustering. RELIEF-C outperforms other methods significantly over synthetic, benchmark and real world data sets particularly when data set consists of large amount of noisy tuples and/or irrelevant features.

We explore the capabilities of today's high-end Graphics processing units (GPU) on desktops to efficiently perform hierarchical agglomerative clustering (HAC) through partitioning of data. Traditional HAC has high time and memory complexities leading to low clustering efficiencies. We reduce time and memory bottlenecks of the traditional HAC algorithm by exploring the performance capabilities of the GPU, significantly accelerating the computations without compromising the accuracy of clusters. We implement the traditional HAC and the Partially Overlapping Partitioning (PoP) on GPU using Compute Unified Device Architecture (CUDA) and compare the computational performance with CPU using micro array data. The result shows that the PoP HAC and traditional HAC are up to 442 times and 66 times faster on the GPU respectively than the time taken by CPU. The PoP-enabled HAC on GPU requires only a fraction of the memory required by traditional HAC both on the CPU and GPU.

Outlier detection is studied in the context of supervised (with class label) and unsupervised (without class label – e.g., clustering) data. To the best of our knowledge there has been no study on outlier detection in transactional database, e.g. market basket data where each transaction has a numb er of items and the number of items in each transaction is not constant. Following the definition of outlier by Barnett and Lewis, 1994, we define an outlier transaction in this paper as that which appears to deviate markedly from other transactions of the database in which it occurs. This problem is important, for instance a supermarket manager would like to know the outlier transactions so as to make proper decisions. This problem is not trivial particularly when the number of items is large which is often the case in market basket data. We propose a novel and efficient solution DETACH which is different from other work in this area. The proposed method uses a unique approach of creating a representative sample, and subsequently it determines the degree to which each transaction is an outlier considering the representative sample. The proposed method, unlike its predecessors, does not require any parameter that is hard to set. We test our proposed method using benchmark market basket data from QUEST project. Results show that DETACH is very efficient and accurate.

We investigate the problem of finding frequent patterns in a continuous stream of transactions. In the literature, two prominent approaches are often used: (a) perform approximate counting (e.g., lossy counting algorithm (LCA) of Manku and Motwani, VLDB 2002) by using a lower support threshold than the one given by the user, or (b) maintain a running sample (e.g., reservoir sampling (Algo-Z) of Vitter, TOMS 1985) and generate frequent itemsets from the sample on demand. Although both are known to be practically useful, to the best of our knowledge, there has been no comparison between them. In addition, we propose a distance based sampling algorithm (DSS). An empirical comparison study on the algorithms is performed using synthetic and benchmark datasets. Results show that DSS is consistently more accurate than LCA and Algo-Z, whereas LCA performs better than Algo-Z. An outcome of this study is a new algorithm CLCA. In LCA, the proper quantification of the error parameter, ε, is non-trival. CLCA is an attempt to exploit this fact in proposing a new customized LCA algorithm. Interestingly, CLCA outperforms all other algorithms (including DSS) in mining for the frequent itemsets of user's choice.

Cross-validation (CV), which is widely used in classification problems, gives a very good estimate of the prediction accuracy of a classifier over unseen data [1]. Thus, any improvement in the accuracy estimation of the cross-validation method will benefit a lot of people and help in improving the results of many researches. In this paper the focus is on skewed noisy datasets. Applications such as fraud detection is an important example of skewed data. Usually for CV, simple random sampling (SRS) is performed to divide the data into the required number of folds, e.g., 10-fold CV requires the data to be divided into 10 folds. SRS is known to give poor performance (accuracy of classification) when data is skewed. We propose a new algorithm, based on the frequency histogram of each attribute value, to divide the dataset into the required number of folds. In this project, the effectiveness of the proposed algorithm vis-à-vis SRS is tested with datasets from the UCI machine learning repository. The results show that the proposed algorithm is significantly better in handling noisy skewed data. (Abstract)

Mining data streams for frequent patterns is important in many applications. Unlike traditional static databases, the underlying process that generates the data streams evolves over time. Past data may become outdated and of little use when compared to the most recent one. When a significant change occurs, much harm is done to the mining result if it is not properly handled. In this paper, an online algorithm for change detection in frequent pattern mining is proposed. Although there have been several studies mainly for adapting to changes, we contend that this is not enough. The ability to detect and characterize change is essential in many applications. A novel test strategy is designed to gather the ldquoevidencerdquo sufficient to conclude on whether the current sample differ significantly from a reference sample. Different statistical tests are evaluated and our study shows that the chi-square test is the most suitable for enumerated or count data.

As the amount of multimedia data is increasing day-by-day thanks to less expensive storage devices and increasing numbers of information sources, machine learning algorithms are faced with large-sized and noisy datasets. Fortunately, the use of a good sampling set for training influences the final results significantly. But using a simple random sample (SRS) may not obtain satisfactory results because such a sample may not adequately represent the large and noisy dataset due to its blind approach in selecting samples. The difficulty is particularly apparent for huge datasets where, due to memory constraints, only very small sample sizes are used. This is typically the case for multimedia applications, where data size is usually very large. In this article we propose a new and efficient method to sample of large and noisy multimedia data. The proposed method is based on a simple distance measure that compares the histograms of the sample set and the whole set in order to estimate the representativeness of the sample. The proposed method deals with noise in an elegant manner which SRS and other methods are not able to deal with. We experiment on image and audio datasets. Comparison with SRS and other methods shows that the proposed method is vastly superior in terms of sample representativeness, particularly for small sample sizes although time-wise it is comparable to SRS, the least expensive method in terms of time.

This correspondence presents a novel hybrid wrapper and filter feature selection algorithm for a classification problem using a memetic framework. It incorporates a filter ranking method in the traditional genetic algorithm to improve classification performance and accelerate the search in identifying the core feature subsets. Particularly, the method adds or deletes a feature from a candidate feature subset based on the univariate feature ranking information. This empirical study on commonly used data sets from the University of California, Irvine repository and microarray data sets shows that the proposed method outperforms existing methods in terms of classification accuracy, number of selected features, and computational efficiency. Furthermore, we investigate several major issues of memetic algorithm (MA) to identify a good balance between local search and genetic search so as to maximize search quality and efficiency in the hybrid filter and wrapper MA.

An audio event refers to some specific audio sound which plays important role for video content analysis. In our previous work [3], we have established audio event identification as an audio classification task. Due to the large size of audio database, representative samples are necessary for training the classifier. However, the commonly used random selection of training samples is often not adequate in selecting representative samples. In this paper we present EASIER sampling algorithm to select those data which more efficiently represent audio data characters for audio event identifier training. EASIER deterministically produces a subsample whose “distance” from the complete database is minimal. Experiments in the context of audio event identification show that EASIER outperforms simple random sampling significantly.

A variety of mining and analysis problems --- ranging from association-rule discovery to contingency table analysis to materialization of certain approximate datacubes --- involve the extraction of knowledge from a set of categorical count data. Such data can be viewed as a collection of "transactions," where a transaction is a fixed-length vector of counts. Classical algorithms for solving count-data problems require one or more computationally intensive passes over the entire database and can be prohibitively slow. One effective method for dealing with this ever-worsening scalability problem is to run the algorithms on a small sample of the data. We present a new data-reduction algorithm, called EASE, for producing such a sample. Like the FAST algorithm introduced by Chen et al., EASE is especially designed for count data applications. Both EASE and FAST take a relatively large initial random sample and then deterministically produce a subsample whose "distance" --- appropriately defined --- from the complete database is minimal. Unlike FAST, which obtains the final subsample by quasi-greedy descent, EASE uses epsilon-approximation methods to obtain the final subsample by a process of repeated halving. Experiments both in the context of association rule mining and classical χ2 contingency-table analysis show that EASE outperforms both FAST and simple random sampling, sometimes dramatically.

Processing applications with a large number of dimensions has been a challenge for the KDD community. Feature selection, an effective dimensionality reduction technique, is an essential pre-processing method to remove noisy features. In the literature only a few methods have been proposed for feature selection for clustering, and almost all these methods are 'wrapper' techniques that require a clustering algorithm to evaluate candidate feature subsets. The wrapper approach is largely unsuitable in real-world applications due to its heavy reliance on clustering algorithms that require parameters such as the number of clusters, and the lack of suitable clustering criteria to evaluate clustering in different subspaces. In this paper we propose a 'filter' method that is independent of any clustering algorithm. The proposed method is based on the observation that data with clusters has a very different point-to-point distance histogram to that of data without clusters. By exploiting this we propose an entropy measure that is low if data has distinct clusters and high if it does not. The entropy measure is suitable for selecting the most important subset of features because it is invariant with the number of dimensions, and is affected only by the quality of clustering. Extensive performance evaluation over synthetic, benchmark, and real datasets shows its effectiveness.

Clustering is an important data exploration task. Its use in data mining is growing very fast. Traditional clustering algorithms which no longer cater for the data mining requirements are modified increasingly. Clustering algorithms are numerous which can be divided in several categories. Two prominent categories are distance-based and density-based (e.g. K-means and DBSCAN, respectively). While K-means is fast, easy to implement and converges to local optima almost surely, it is also easily affected by noise. On the other hand, while density-based clustering can find arbitrary shape clusters and handle noise well, it is also slow in comparison due to neighborhood search for each data point, and faces a difficulty in setting the density threshold properly. We propose BRIDGE that efficiently merges the two by exploiting the advantages of one to counter the limitations of the other and vice versa. BRIDGE enables DBSCAN to handle very large data efficiently and improves the quality of K-means clusters by removing the noisy points. It also helps the user in setting the density threshold parameter properly. We further show that other clustering algorithms can be merged using a similar strategy. An example given in the paper merges BIRCH clustering with DBSCAN.

The authors show that most hierarchical agglomerative clustering (HAC) algorithms follow a 90-10 rule where roughly 90% iterations from the beginning merge cluster pairs with dissimilarity less than 10% of the maximum dissimilarity. We propose two algorithms: 2-phase and nested, based on partially overlapping partitioning (POP). To handle high-dimensional data efficiently, we propose a tree structure particularly suitable for POP. Extensive experiments show that the proposed algorithms reduce the time and memory requirement of existing HAC algorithms significantly without compromising accuracy.

Dimensionality reduction is an important problem for efficient handling of large databases. Many feature selection methods exist for supervised data having class information. Little work has been done for dimensionality reduction of unsupervised data in which class information is not available. Principal component analysis (PCA) is often used. However, PCA creates new features. It is difficult to obtain intuitive understanding of the data using the new features only. We are concerned with the problem of determining and choosing the important original features for unsupervised data. Our method is based on the observation that removing an irrelevant feature from the feature set may not change the underlying concept of the data, but not so otherwise. We propose an entropy measure for ranking features, and conduct extensive experiments to show that our method is able to find the important features. Also it compares well with a similar feature ranking method (Relief) that requires class information unlike our method.

Feature selection has been the focus of interest for quite some time and much work has been done. With the creation of huge databases and the consequent requirements for good machine learning techniques, new problems arise and novel approaches to feature selection are in demand. This survey is a comprehensive overview of many existing methods from the 1970's to the present. It identifies four steps of a typical feature selection method, and categorizes the different existing methods in terms of generation procedures and evaluation functions, and reveals hitherto unattempted combinations of generation procedures and evaluation functions. Representative methods are chosen from each category for detailed explanation and discussion via example. Benchmark datasets with different characteristics are used for comparative study. The strengths and weaknesses of different methods are explained. Guidelines for applying feature selection methods are given based on data types and domain characteristics. This survey identifies the future research areas in feature selection, introduces newcomers to this field, and paves the way for practitioners who search for suitable methods for solving domain-specific real-world applications.