In this paper we introduce the converse k-clustering problem as an alternative partitional clustering model. Partitional clustering is a traditional category of clustering methods, where the general formulation is to produce a given k number of clusters that minimize some compactness objective. Since the parameter k is often hard to determine in advance, we argue that in many cases converse k-clustering can be a more appropriate formulation. Given a compactness threshold as constraint, converse k-clustering minimizes the number of clusters k. Such compactness constraints, such as maximum diameter, can be intuitively specified based on domain knowledge in many real world applications. In the paper we also show how conventional combinatorial optimization techniques, such as minimum clique partition, can be adapted to solve converse k-clustering.

In this paper we introduce the partial clustering problem. Given o objects, select $p \le o$ of them such that the selected objects form an optimal clustering with respect to a given cost function f. The problem can find various applications where due to capacity constraints, only part of the data objects can be selected, and the selection criteria are based on how good a clustering the partial data can form. Partial clustering generalizes clustering, and is significantly harder involving nested combinatorial optimization. For the introduced problem, we also propose generic algorithms without specifications of the cost function, and perform preliminary experiments for initial verification.

Often people need to make comparisons in order to make selections and decisions. Increasingly such comparison activities are conducted online. For example, consumers typically read many reviews and compare various models before an online purchase. Since this comparison-based analytical and decision-making process often involves significant manual effort, it is greatly beneficial if the process can be largely automated and effectively performed by computers. In this research, we make an effort to design and implement COMPA, a web-based comparative retrieval and analytical engine in the context of consumer products that can effectively assist decision-making. COMPA takes two products A vs B as input, retrieves relevant online reviews, performs comprehensive analysis, and returns a comparison report including product comparison scores as well as supporting evidence.

Nearest neighbor search is a fundamental problem in data management and analytics with vast applications. However, a seminal paper by Beyer et al demonstrated the curse of dimensionality, where under certain conditions with high dimensionality, all the data points tend to be equidistant and thus the nearest neighbor problem is meaningless. This influential work has spawned a series of investigations of the concentration phenomenon, which, for the most part, are limited to the vector space. In this paper, we extend this investigation to sequence data, which do not have an inherent notion of dimensions or attributes. For similarity measures we consider the commonly used edit distance and longest common subsequence. We perform theoretical analysis and prove conditions under which sequences will concentrate. We also conduct experiments on synthetic data to verify the theoretical findings. Rather than the curse of dimensionality as previous studies demonstrate, we attempt to demonstrate the curse of length for sequential data.

Frequent pattern mining is one of the central tasks in data mining with broad applications in diverse domains. The mining process typically returns an overwhelmingly large number of patterns, making pattern evaluation and exploration extremely difficult. In this project, we adapt and extend information retrieval techniques to implement pattern retrieval, where we introduce Peak, an IR-based system that features a user-friendly keyword search interface allowing users to effectively explore itemset and sequential patterns based on their interest.

Online reviews have a critical impact on e-commerce business. While many studies have been done on the various characteristics of online reviews, in this paper we present a preliminary experimental analysis on RateMyProfessors, a well-known review site that allows college students to post reviews and assign ratings to professors. We collected online review data from RateMyProfessors and compared them with assumptive ground truth. Our analysis suggests an evaluation bias where RateMyProfessors ratings tend to be more negative. About 76% of professors in general and 90% of professors teaching hard courses are negatively affected.

Many academic and administrative decisions rely on evaluation of publication venues and individual researchers, such as for the purpose of hiring, promotion, and grant distribution. Thus it is important to compare and rank publication venues and researchers in an objective and authoritative manner. While many endeavors exist, in this paper we propose a novel algorithm CoRank based on venue-researcher interaction that computes reputation scores and rankings for publication values and researchers simultaneously. We observe that good researchers publish many papers in good venues, good publication venues feature many good researchers, and venue scores and researcher scores can be defined in terms of each other. CoRank is designed to break this circular definition in an iterative manner to compute reputation scores and rankings for both venues and researchers. We implement CoRank and perform experiments on real DBLP dataset to demonstrate its promise.

Many e-commerce websites allow customers to contribute product ratings and reviews. Such customer feedback can be used to rank products and make recommendations. As a standard approach, products are typically ranked by their average customer ratings. A problem of this approach is that average ratings based on small samples exhibit very little statistical confidence. They can differ significantly from true average ratings resulting in misleading rankings of products. In this paper, we investigate a systematic approach that applies statistical correction to average customer ratings leading to more robust rankings of products. We also implement the approach with the Yelp API to demonstrate its utility.

In the real physical world, people visit same places for same or similar purposes, where they meet, talk, exchange ideas/feelings/emotions, help each other, develop relationships, and form communities. On the web, web surfers also visit various places that are web resources such as pages, images, and videos. However, normally they do not get to meet and interact because the web is "dark" and they cannot see each other. In this paper we describe the LIGHT project that aims at "lighting up" the web so that web surfers can meet and interact spontaneously at random places. In particular, LIGHT provides a universal solution based on a browser extension, enabling convenient and instant online communication for web surfers visiting the same or similar URLs. A URL contains instance-level information precisely describing a very specific interest. Thus LIGHT complements the communication facilities provided by online community portals, which exist to serve the social needs and general/long-term interests of online community members. This complementation is significant because there are far more momentary/situational/specific human needs and interests than those long-term/general ones.

Evaluation is ubiquitous. Often we need to evaluate a set of target entities and obtain their true ratings (average ratings from the population) or true rankings (rankings derived from true ratings). Based on the law of large numbers, average ratings from large samples can provide a good approximation. However, due to the fact that evaluation is labor-intensive, in practice large evaluation data are typically very sparse where each entity receives very few ratings. Consequently, average ratings would significantly differ from true ratings due to biased distribution of standards and preferences of evaluators. In this paper, we investigate comparative evaluation that addresses the evaluation bias problem for improved evaluation accuracy. The principle idea is to first extract a partial list for the entities evaluated by each evaluator, and then aggregate all the partial lists to obtain a total list that well approximates the true rankings. The aggregated total list can be used to further estimate the true ratings. In this paper we also study an associated problem of evaluation assignment (assigning target entities to evaluators), where we propose an iterative assignment approach to maximize accuracy of comparative evaluation given limited evaluation resources.

We introduce and theoretically study the convergence behavior of iterative matrix correlation computation and show how it can be leveraged to derive a novel bisection clustering algorithm with unique characteristics. A correlation matrix is a symmetric n × n matrix for n vectors, where the (i, j)-th entry is the Pearson correlation coefficient between vectors i and j. We observe that in general cases iterative update of the correlation matrix leads to its convergence where all entries are either 1 or -1. Moreover, the same convergence behavior holds if we select a pre-determined subset of columns from the correlation matrix in each iteration for the next iteration of correlation computation. We mathematically prove this observation, analyze its convergence behavior, and propose an efficiency improvement technique. While this observation is significant in its own right and may have many applications, we focus on how to apply it to achieve bisection clustering. Clustering is a fundamental data mining task. Bisection clustering is particularly important because it can be used as a building block to construct hierarchical clustering and arbitrary k-clustering. The derived algorithm, which we call Corbis, works in a fundamentally different way from existing ones with preferable characteristics and comparative advantages especially for high dimensional data. It can be an important addition to the arsenal of clustering algorithms.

Search personalization is an important technique for improving search performance. Existing approaches work in a black box, where users have no clue how it works and how to customize it. This lack of user control and flexibility can often be inconvenient and counter-productive. In this paper, we propose PEEPLER, a transparent search personalization framework that enables full user control and manipulation. In PEEPLER, a user can own multiple profiles and each can be modified arbitrarily. Profile terms can be automatically generated, manually entered, and expanded by adding their semantically related ones. In addition, negative terms are allowed for specification of negative preferences, which can be very useful in filtering undesirable results. The selected profile will help re-rank search results based on how consistent they are with respect to the profile. We implement PEEPLER in the context of Web search using Google Web search API, demonstrating the promise and potential of the approach.

We propose CCRank, the first parallel framework for learning to rank based on evolutionary algorithms (EA), aiming to significantly improve learning efficiency while maintaining accuracy. CCRank is based on cooperative coevolution (CC), a divide-and-conquer framework that has demonstrated high promise in function optimization for problems with large search space and complex structures. Moreover, CC naturally allows parallelization of sub-solutions to the decomposed sub-problems, which can substantially boost learning efficiency. With CCRank, we investigate parallel CC in the context of learning to rank. We implement CCRank with three EA-based learning to rank algorithms for demonstration. Extensive experiments on benchmark datasets in comparison with the state-of-the-art algorithms show the performance gains of CCRank in efficiency and accuracy.

Ensemble learning is a common tool for data stream classification, mainly because of its inherent advantages of handling large volumes of stream data and concept drifting. Previous studies, to date, have been primarily focused on building accurate ensemble models from stream data. However, a linear scan of a large number of base classifiers in the ensemble during prediction incurs significant costs in response time, preventing ensemble learning from being practical for many real-world time-critical data stream applications, such as Web traffic stream monitoring, spam detection, and intrusion detection. In these applications, data streams usually arrive at a speed of GB/second, and it is necessary to classify each stream record in a timely manner. To address this problem, we propose a novel Ensemble-tree (E-tree for short) indexing structure to organize all base classifiers in an ensemble for fast prediction. On one hand, E-trees treat ensembles as spatial databases and employ an R-tree like height-balanced structure to reduce the expected prediction time from linear to sub-linear complexity. On the other hand, E-trees can be automatically updated by continuously integrating new classifiers and discarding outdated ones, well adapting to new trends and patterns underneath data streams. Theoretical analysis and empirical studies on both synthetic and real-world data streams demonstrate the performance of our approach.

Internet of Things (IoT) is an emerging paradigm where physical objects are connected and communicated over the Web. Its capability in assimilating the virtual world and the physical one offers many exciting opportunities. However, how to realize a smooth, seamless integration of the two worlds remains an interesting and challenging topic. In this paper, we showcase an IoT prototype system that enables seamless integration of the virtual and the physical worlds and efficient management of things of interest (TOIs), where services and resources offered by things can be easily monitored, visualized, and aggregated for value-added services by users. This paper presents the motivation, system design, implementation, and demonstration scenario of the system.

Collaborative filtering (CF) is an effective technique addressing the information overload problem. CF approaches generally fall into two categories: rating based and ranking based. The former makes recommendations based on historical rating scores of items and the latter based on their rankings. Ranking-based CF has demonstrated advantages in recommendation accuracy, being able to capture the preference similarity between users even if their rating scores differ significantly. In this study, we propose VSRank, a novel framework that seeks accuracy improvement of ranking-based CF through adaptation of the vector space model. In VSRank, we consider each user as a document and his or her pairwise relative preferences as terms. We then use a novel degree-specialty weighting scheme resembling TF-IDF to weight the terms. Extensive experiments on benchmarks in comparison with the state-of-the-art approaches demonstrate the promise of our approach.

With recent advances in radio-frequency identification (RFID), wireless sensor networks, and Web services, physical things are becoming an integral part of the emerging ubiquitous Web. Correlation discovery for ubiquitous things is critical for many important applications such as things search, recommendation, annotation, classification, clustering, composition, and management. In this paper, we propose a novel approach for discovering things correlation based on user, temporal, and spatial information captured from usage events of things. In particular, we use a spatio-temporal graph and a social graph to model things usage contextual information and user-thing relationships respectively. Then, we apply random walks with restart on these graphs to compute correlations among things. This correlation analysis lays a solid foundation and contributes to improved effectiveness in things management. To demonstrate the utility of our approach, we perform a systematic case study and comprehensive experiments on things annotation.

In this paper, we introduce and study the minimum consistent subset cover (MCSC) problem. Given a finite ground set X and a constraint t, find the minimum number of consistent subsets that cover X, where a subset of X is consistent if it satisfies t. The MCSC problem generalizes the traditional set covering problem and has minimum clique partition (MCP), a dual problem of graph coloring, as an instance. Many common data mining tasks in rule learning, clustering, and pattern mining can be formulated as MCSC instances. In particular, we discuss the minimum rule set (MRS) problem that minimizes model complexity of decision rules, the converse k-clustering problem that minimizes the number of clusters, and the pattern summarization problem that minimizes the number of patterns. For any of these MCSC instances, our proposed generic algorithm CAG can be directly applicable. CAG starts by constructing a maximal optimal partial solution, then performs an example-driven specific-to-general search on a dynamically maintained bipartite assignment graph to simultaneously learn a set of consistent subsets with small cardinality covering the ground set.

Existing search engines have page as the unit of information of retrieval. They typically return a ranked list of pages, each being a search result containing the query keywords. This within-one-page constraint disallows utilization of relationship information that is often available and greatly beneficial. To utilize relationship information and improve search precision, we explore cross-page search, where each answer is a logical page consisting of multiple closely related pages that collectively contain the query keywords. We have implemented a prototype Cager, providing cross-page search and visualization over real dataset.

Keyword search over graphs has a wide array of applications in querying structured, semi-structured and unstructured data. Existing models typically use minimal trees or bounded subgraphs as query answers. While such models emphasize relevancy, they would suffer from incompleteness of information and redundancy among answers, making it difficult for users to effectively explore query answers. To overcome these drawbacks, we propose a novel cluster-based model, where query answers are relevancy-connected clusters. A cluster is a subgraph induced from a maximal set of relevancy-connected nodes. Such clusters are coherent and relevant, yet complete and redundancy free. They can be of arbitrary shape in contrast to the sphere-shaped bounded subgraphs in existing models. We also propose an efficient search algorithm and a corresponding graph index for large, disk-resident data graphs.

Most existing recommender systems can be classified into two categories: collaborative filtering and content-based filtering. Hybrid recommender systems combine the advantages of the two for improved recommendation performance. Traditional recommender systems are rating-based. However, predicting ratings is an intermediate step towards their ultimate goal of generating rankings or recommendation lists. Learning to rank is an established means of predicting rankings and has recently demonstrated high promise in improving quality of recommendations. In this paper, we propose LRHR, the first attempt that adapts learning to rank to hybrid recommender systems. LRHR first defines novel representations for both users and items so that they can be content-comparable. Then, LRHR identifies a set of novel meta-level features for learning purposes. Finally, LRHR adopts RankSVM, a pairwise learning to rank algorithm, to generate recommendation lists of items for users. Extensive experiments on benchmarks in comparison with the state-of-the-art algorithms demonstrate the performance gain of our approach.

In this paper, we introduce polygene-based evolution, a novel framework for evolutionary algorithms (EAs) that features distinctive operations in the evolution process. In traditional EAs, the primitive evolution unit is gene, where genes are independent components during evolution. In polygene-based evolutionary algorithms (PGEAs), the evolution unit is polygene, i.e., a set of co-regulated genes. Discovering and maintaining quality polygenes can play an effective role in evolving quality individuals. Polygenes generalize genes, and PGEAs generalize EAs. Implementing the PGEA framework involves three phases: polygene discovery, polygene planting, and polygene-compatible evolution. Extensive experiments on function optimization benchmarks in comparison with the conventional and state-of-the-art EAs demonstrate the potential of the approach in accuracy and efficiency improvement.

Collaborative filtering (CF) is an effective technique addressing the information overload problem. Recently ranking-based CF methods have shown advantages in recommendation accuracy, being able to capture the preference similarity between users even if their rating scores differ significantly. In this study, we seek accuracy improvement of ranking-based CF through adaptation of the vector space model, where we consider each user as a document and her pairwise relative preferences as terms. We then use a novel degree-specialty weighting scheme resembling TF-IDF to weight the terms. Then we use cosine similarity to select a neighborhood of users for the target user to make recommendations. Experiments on benchmarks in comparison with the state-of-the-art methods demonstrate the promise of our approach.

Order-preserving submatrix (OPSM) has been widely accepted as a biologically meaningful cluster model, capturing the general tendency of gene expression across a subset of experiments. In an OPSM, the expression levels of all genes induce the same linear ordering of the experiments. The OPSM problem is to discover those statistically significant OPSMs from a given data matrix. The problem is reducible to a special case of the sequential pattern mining problem, where a pattern and its supporting sequences uniquely specify an OPSM. Unfortunately, existing methods do not scale well to massive data sets containing thousands of experiments and hundreds of thousands of genes, which are common in today's gene expression analysis. In particular, deep OPSMs, corresponding to long patterns with few supporting sequences, incur explosive computational costs in their discovery and are completely pruned off by existing methods. However, it is of particular interest of biologists to determine small groups of genes that are tightly coregulated across many experiments, and some pathways or processes may require as few as two genes to act in concert. In this paper, we study the discovery of deep OPSMs from massive data sets. We propose a novel best effort mining framework Kiwi that exploits two parameters k and w to bound the available computational resources and search a selected search space, and does what it can to find as many as possible deep OPSMs. Extensive biological and computational evaluations on real data sets demonstrate the validity and importance of the deep OPSM problem, and the efficiency and effectiveness of the Kiwi mining framework.

How to organize and present search results plays a critical role in the utility of search engines. Due to the unprecedented scale of the Web and diversity of search results, the common strategy of ranked lists has become increasingly inadequate, and clustering has been considered as a promising alternative. Clustering divides a long list of disparate search results into a few topic-coherent clusters, allowing the user to quickly locate relevant results by topic navigation. While many clustering algorithms have been proposed that innovate on the automatic clustering procedure, we introduce ClusteringWiki, the first prototype and framework for personalized clustering that allows direct user editing of the clustering results. Through a Wiki interface, the user can edit and annotate the membership, structure and labels of clusters for a personalized presentation. In addition, the edits and annotations can be shared among users as a mass-collaborative way of improving search result organization and search engine utility.

Lazy learning, such as k-nearest neighbor learning, has been widely applied to many applications. Known for well capturing data locality, lazy learning can be advantageous for highly dynamic and complex learning environments such as data streams. Yet its high memory consumption and low prediction efficiency have made it less favorable for stream oriented applications. Specifically, traditional lazy learning stores all the training data and the inductive process is deferred until a query appears, whereas in stream applications, data records flow continuously in large volumes and the prediction of class labels needs to be made in a timely manner. In this paper, we provide a systematic solution that overcomes the memory and efficiency limitations and enables fast lazy learning for concept drifting data streams. In particular, we propose a novel Lazy-tree (Ltree for short) indexing structure that dynamically maintains compact high-level summaries of historical stream records. L-trees are M-Tree [5] like, height-balanced, and can help achieve great memory consumption reduction and sub-linear time complexity for prediction. Moreover, L-trees continuously absorb new stream records and discard outdated ones, so they can naturally adapt to the dynamically changing concepts in data streams for accurate prediction. Extensive experiments on real-world and synthetic data streams demonstrate the performance of our approach.

Ensemble learning has become a common tool for data stream classification, being able to handle large volumes of stream data and concept drifting. Previous studies focus on building accurate prediction models from stream data. However, a linear scan of a large number of base classifiers in the ensemble during prediction incurs significant costs in response time, preventing ensemble learning from being practical for many real world time-critical data stream applications, such as Web traffic stream monitoring, spam detection, and intrusion detection. In these applications, data streams usually arrive at a speed of GB/second, and it is necessary to classify each stream record in a timely manner. To address this problem, we propose a novel Ensemble-tree (E-tree for short) indexing structure to organize all base classifiers in an ensemble for fast prediction. On one hand, E-trees treat ensembles as spatial databases and employ an R-tree like height-balanced structure to reduce the expected prediction time from linear to sub-linear complexity. On the other hand, E-trees can automatically update themselves by continuously integrating new classifiers and discarding outdated ones, well adapting to new trends and patterns underneath data streams. Experiments on both synthetic and real-world data streams demonstrate the performance of our approach.

How to organize and present search results plays a critical role in the utility of search engines. Due to the unprecedented scale of the Web and diversity of search results, the common strategy of ranked lists has become increasingly inadequate, and clustering has been considered as a promising alternative. Clustering divides a long list of disparate search results into a few topic-coherent clusters, allowing the user to quickly locate relevant results by topic navigation. While many clustering algorithms have been proposed that innovate on the automatic clustering procedure, we introduce ClusteringWiki, the first prototype and framework for personalized clustering that allows direct user editing of clustering results. Through a Wiki interface, the user can edit and annotate the membership, structure and labels of clusters for a personalized presentation. In addition, the edits and annotations can be shared among users as a mass collaborative way of improving search result organization and search engine utility.

Learning to rank represents a category of effective ranking methods for information retrieval. While the primary concern of existing research has been accuracy, learning efficiency is becoming an important issue due to the unprecedented availability of large-scale training data and the need for continuous update of ranking functions. In this paper, we investigate parallel learning to rank, targeting simultaneous improvement in accuracy and efficiency.

With a Wiki-like search interface, users can edit ranks of search results and share the edits with the rest of the world. This is an effective way of personalization, as well as a practice of mass collaboration that allows users to vote for ranking and improve search performance. Currently, there are several ongoing experimentation efforts from the industry, e.g., SearchWiki by Google and U Rank by Microsoft. Beyond that, there is little published research on this new search paradigm. In this paper, we make an effort to establish a framework for rank editing and sharing in the context of web search, where we identify fundamental issues and propose principled solutions. Comparing to existing systems, for rank editing, our framework allows users to specify not only relative, but also absolute preferences. For edit sharing, our framework provides enhanced flexibility, allowing users to select arbitrarily aggregated views. In addition, edits can be shared among similar queries. We present a prototype system Rants, that implements the framework and provides search services through the Google web search API.

We introduce and theoretically study the Gardener's problem that well models many web information monitoring scenarios, where numerous dynamically changing web sources are monitored and local information needs to be periodically updated under communication and computation capacity constraints. Typical such examples include maintenance of inverted indexes for search engines and maintenance of extracted structures for unstructured data management systems. We formulate a corresponding multicriteria optimization problem and propose heuristic solutions.

Most information extraction (IE) approaches have considered only static text corpora, over which we apply IE only once. Many real-world text corpora however are dynamic. They evolve over time, and so to keep extracted information up to date we often must apply IE repeatedly, to consecutive corpus snapshots. Applying IE from scratch to each snapshot can take a lot of time. To avoid doing this, we have recently developed Cyclex, a system that recycles previous IE results to speed up IE over subsequent corpus snapshots. Cyclex clearly demonstrated the promise of the recycling idea. The work itself however is limited in that it considers only IE programs that contain a single IE ``blackbox.'' In practice, many IE programs are far more complex, containing multiple IE blackboxes connected in a compositional ``workflow.''

The rapid growth of Web communities has motivated many solutions for building community data portals. These solutions follow roughly two approaches. The first approach (e.g., Libra, Citeseer, Cimple) employs semi-automatic methods to extract and integrate data from a multitude of data sources. The second approach (e.g., Wikipedia, Intellipedia) deploys an initial portal in wiki format, then invites community members to revise and add material. In this paper we consider combining the above two approaches to building community portals. The new hybrid machine-human approach brings significant benefits. It can achieve broader and deeper coverage, provide more incentives for users to contribute, and keep the portal more up-to-date with less user effort. In a sense, it enables building "community wikipedias", backed by an underlying structured database that is continuously updated using automatic techniques. We outline our ideas for the new approach, describe its challenges and opportunities, and provide initial solutions. Finally, we describe a real-world implementation and preliminary experiments that demonstrate the utility of the new approach.

Attribute data and relationship data are two principal types of data, representing the intrinsic and extrinsic properties of entities. While attribute data have been the main source of data for cluster analysis, relationship data such as social networks or metabolic networks are becoming increasingly available. It is also common to observe both data types carry complementary information such as in market segmentation and community identification, which calls for a joint cluster analysis of both data types so as to achieve better results. In this article, we introduce the novel Connected k -Center ( CkC ) problem, a clustering model taking into account attribute data as well as relationship data. We analyze the complexity of the problem and prove its NP-hardness. Therefore, we analyze the approximability of the problem and also present a constant factor approximation algorithm. For the special case of the CkC problem where the relationship data form a tree structure, we propose a dynamic programming method giving an optimal solution in polynomial time. We further present NetScan, a heuristic algorithm that is efficient and effective for large real databases. Our extensive experimental evaluation on real datasets demonstrates the meaningfulness and accuracy of the NetScan results.

In this paper, we introduce and study the Minimum Consistent Subset Cover (MCSC) problem. Given a finite ground set X and a constraint t, find the minimum number of consistent subsets that cover X, where a subset of X is consistent if it satisfies t. The MCSC problem generalizes the traditional set covering problem and has Minimum Clique Partition, a dual problem of graph coloring, as an instance. Many practical data mining problems in the areas of rule learning, clustering, and frequent pattern mining can be formulated as MCSC instances. In particular, we discuss the Minimum Rule Set problem that minimizes model complexity of decision rules as well as some converse k-clustering problems that minimize the number of clusters satisfying certain distance constraints. We also show how the MCSC problem can find applications in frequent pattern summarization. For any of these MCSC formulations, our proposed novel graph-based generic algorithm CAG can be directly applicable. CAG starts by constructing a maximal optimal partial solution, then performs an example-driven specific-to-general search on a dynamically maintained bipartite assignment graph to simultaneously learn a set of consistent subsets with small cardinality covering the ground set. Our experiments on benchmark datasets show that CAG achieves good results compared to existing popular heuristics.

The ultimate goal of data mining is to extract knowledge from massive data. Knowledge is ideally represented as human-comprehensible patterns from which end-users can gain intuitions and insights. Yet not all data mining methods produce such readily understandable knowledge, e.g., most clustering algorithms output sets of points as clusters. In this paper, we perform a systematic study of cluster description that generates interpretable patterns from clusters. We introduce and analyze novel description formats leading to more expressive power, motivate and define novel description problems specifying different trade-offs between interpretability and accuracy. We also present effective heuristic algorithms together with their empirical evaluations.

Order-preserving submatrixes (OPSMs) have been accepted as a biologically meaningful subspace cluster model, capturing the general tendency of gene expressions across a subset of conditions. In an OPSM, the expression levels of all genes induce the same linear ordering of the conditions. OPSM mining is reducible to a special case of the sequential pattern mining problem, in which a pattern and its supporting sequences uniquely specify an OPSM cluster. Those small twig clusters, specified by long patterns with naturally low support, incur explosive computational costs and would be completely pruned off by most existing methods for massive datasets containing thousands of conditions and hundreds of thousands of genes, which are common in today's gene expression analysis. However, it is in particular interest of biologists to reveal such small groups of genes that are tightly coregulated under many conditions, and some pathways or processes might require only two genes to act in concert. In this paper, we introduce the KiWi mining framework for massive datasets, that exploits two parameters k and w to provide a biased testing on a bounded number of candidates, substantially reducing the search space and problem scale, targeting on highly promising seeds that lead to significant clusters and twig clusters. Extensive biological and computational evaluations on real datasets demonstrate that KiWi can effectively mine biologically meaningful OPSM subspace clusters with good efficiency and scalability.

Attribute data and relationship data are two principle types of data, representing the intrinsic and extrinsic properties of entities. While attribute data has been the main source of data for cluster analysis, relationship data such as social networks or metabolic networks are becoming increasingly available. It is also common to observe both data types carry orthogonal information such as in market segmentation and community identification, which calls for a joint cluster analysis of both data types so as to achieve more accurate results. For this purpose, we introduce the novel Connected k-Center problem, taking into account attribute data as well as relationship data. We analyze the complexity of this problem and prove its NP-completeness. We also present a constant factor approximation algorithm, based on which we further design NetScan, a heuristic algorithm that is efficient for large, real databases. Our experimental evaluation demonstrates the meaningfulness and accuracy of the NetScan results.

Clustering is one of the major data mining tasks. So far, the database and data mining literature lacks systematic study of cluster descriptions, which are essential to provide the user with understandable knowledge of the clusters and support further interactive exploration. In this paper, we introduce novel description formats leading to more descriptive power. We define two alternative problems of generating cluster descriptions, Minimum Description Length and Maximum Description Accuracy, providing different trade-offs between interpretability and accuracy. We also present heuristic algorithms for both problems, together with their empirical evaluation and comparison to state-of-the-art algorithms.