Graph Neural Networks (GNNs), which generalize deep neural networks to graph-structured data, have drawn considerable attention and achieved state-of-the-art performance in numerous graph related tasks. However, existing GNN models mainly focus on designing graph convolution operations. The graph pooling (or downsampling) operations, that play an important role in learning hierarchical representations, are usually overlooked. In this paper, we proposed a novel multi-view graph pooling operator dubbed as MVPool, which ranks nodes across different views with different contextual graph information. Meanwhile, attention mechanism is utilized to promote the collaboration of different views for generating robust node rankings. Then the pooling operation adaptively selects a subset of nodes to form an induced subgraph based on the ranking list. To preserve the underlying graph topological information, we further introduce a structure learning mechanism to learn a refined graph structure for the pooled graph at each layer. The proposed MVPool operator is a general strategy that can be integrated into various graph neural network architectures. By combining MVPool operator with graph neural networks, we perform hierarchical representation learning for both node and graph level classification as well as clustering tasks. Experimental results on nine widely used benchmarks demonstrate the effectiveness of our proposed model.

A heterogeneous information network (HIN) is one whose nodes model objects of different types and whose links model objects’ relationships. To enrich its information, objects in an HIN are typically associated with additional attributes. We call such an HIN anAttributed HINor AHIN. We study the problem of clustering objects in an AHIN, taking into account objects’ similarities with respect to both object attribute values and their structural connectedness in the network. We show how supervision signal, expressed in the form of amust-link setand acannot-link set, can be leveraged to improve clustering results. We put forward the SCHAIN algorithm to solve the clustering problem, and two highly efficient variants, SCHAIN-PI and SCHAIN-IRAM, which employ thepower iteration based methodand theimplicitly restarted Arnoldi methodrespectively to compute eigenvectors of a matrix. We conduct extensive experiments comparing SCHAIN-based algorithms with other state-of-the-art clustering algorithms. Our results show that SCHAIN-IRAM outperforms other competitors in terms of clustering effectiveness and is highly efficient.

User recommendation aims at recommending users with potential interests in the social network. Previous works have mainly focused on the undirected social networks with symmetric relationship such as friendship, whereas recent advances have been made on the asymmetric relationship such as the following and followed by relationship. Among the few existing direction-aware user recommendation methods, the random walk strategy has been widely adopted to extract the asymmetric proximity between users. However, according to our analysis on real-world directed social networks, we argue that the asymmetric proximity captured by existing random walk based methods are insufficient due to the inbalance in-degree and out-degree of nodes. To tackle this challenge, we propose InfoWalk, a novel informative walk strategy to efficiently capture the asymmetric proximity solely based on random walks. By transferring the direction information into the weights of each step, InfoWalk is able to overcome the limitation of edges while simultaneously maintain both the direction and proximity. Based on the asymmetric proximity captured by InfoWalk, we further propose the qualitative (DNE-L) and quantitative (DNE-T) directed network embedding methods, capable of preserving the two properties in the embedding space. Extensive experiments conducted on six real-world benchmark datasets demonstrate the superiority of the proposed DNE model over several state-of-the-art approaches in various tasks.

Predicting drug response based on the genomic profile of a cancer patient is one of the hallmarks of precision oncology. Despite current methods for drug response prediction becoming more accurate, there is still a need to switch from 'black box' predictions to methods that offer high accuracy as well as interpretable predictions. This is of particular importance in real-world applications such as drug response prediction in cancer patients. In this paper, we propose BDKANN, a novel knowledge-based method that employs the hierarchical information on how proteins form complexes and act together in pathways to form the architecture of a deep neural network. We employ BDKANN to predict cancer drug response from cell line gene expression data and our experimental results demonstrate that not only does BDKANN have a low prediction error compared to baseline models but it also allows meaningful interpretation of the network. These interpretations can both explain predictions made and discover novel connections in the biological knowledge that may lead to new hypotheses about mechanisms of drug action.

Graph similarity learning, which measures the similarities between a pair of graph-structured objects, lies at the core of various machine learning tasks such as graph classification, similarity search, etc. In this paper, we devise a novel graph neural network based framework to address this challenging problem, motivated by its great success in graph representation learning. As the vast majority of existing graph neural network models mainly concentrate on learning effective node or graph level representations of a single graph, little effort has been made to jointly reason over a pair of graph-structured inputs for graph similarity learning. To this end, we propose Hierarchical Hypergraph Matching Networks (H2sup>MN) to calculate the similarities between graph pairs with arbitrary structure. Specifically, our proposed H2MN learns graph representation from the perspective of hypergraph, and takes each hyperedge as a subgraph to perform subgraph matching, which could capture the rich substructure similarities across the graph. To enable hierarchical graph representation and fast similarity computation, we further propose a hyperedge pooling operator to transform each graph into a coarse graph of reduced size. Then, a multi-perspective cross-graph matching layer is employed on the coarsened graph pairs to extract the inter-graph similarity. Comprehensive experiments on five public datasets empirically demonstrate that our proposed model can outperform state-of-the-art baselines with different gains for graph-graph classification and regression tasks.

Sampling strategies have been widely applied in many recommendation systems to accelerate model learning from implicit feedback data. A typical strategy is to draw negative instances with uniform distribution, which, however, will severely affect a model’s convergence, stability, and even recommendation accuracy. A promising solution for this problem is to over-sample the “difficult” (a.k.a. informative) instances that contribute more on training. But this will increase the risk of biasing the model and leading to non-optimal results. Moreover, existing samplers are either heuristic, which require domain knowledge and often fail to capture real “difficult” instances, or rely on a sampler model that suffers from low efficiency. To deal with these problems, we propose CoSam, an efficient and effective collaborative sampling method that consists of (1) a collaborative sampler model that explicitly leverages user-item interaction information in sampling probability and exhibits good properties of normalization, adaption, interaction information awareness, and sampling efficiency, and (2) an integrated sampler-recommender framework, leveraging the sampler model in prediction to offset the bias caused by uneven sampling. Correspondingly, we derive a fast reinforced training algorithm of our framework to boost the sampler performance and sampler-recommender collaboration. Extensive experiments on four real-world datasets demonstrate the superiority of the proposed collaborative sampler model and integrated sampler-recommender framework.

Large-scale online promotions, such as Double 11 and Black Friday, are of great value to e-commerce platforms nowadays. Traditional methods are not successful when we aim to maximize global Gross Merchandise Volume (GMV) in the promotion scenarios due to three limitations. The first is that the GMV of sellers varies significantly from daily scenarios to promotions. Second, these methods do not consider explosive demands in promotions, so that a consumer may fail to purchase some popular items due to sellers' limited capacities. Third, the traffic distribution over sellers presents divergence in different channels, thus rendering the performance of the traditional single-channel methods far from optimal in creating commercial values. To address these problems, we design a Multi-Channel Sellers Traffic Allocation (MCSTA) optimization model to obtain optimal page view (PV) distribution concerning global GMV. Then we propose a general constrained non-smooth convex optimization solution with a Multi-Objective Shortest Distance (MOSD) hyperparameter tuning method to solve MCSTA. This is the first work to systematically address this issue in the scenario of large-scale online promotions. The empirical results show that MCSTA achieves significant improvement of GMV by 1.1% based on A/B test during Alibaba's "Global Shopping Festival", one of the world's largest online sales events. Furthermore, we deploy MCSTA in other popular scenarios, including everyday promotion and video live stream service, to showcase that MCSTA can be widely applied in e-commerce and online entertainment services.

We study the problem of applying spectral clustering to cluster multi-scale data, which is data whose clusters are of various sizes and densities. Traditional spectral clustering techniques discover clusters by processing a similarity matrix that reflects the proximity of objects. For multi-scale data, distance-based similarity is not effective because objects of a sparse cluster could be far apart while those of a dense cluster have to be sufficiently close. Following [16], we solve the problem of spectral clustering on multi-scale data by integrating the concept of objects' "reachability similarity" with a given distance-based similarity to derive an objects' coefficient matrix. We propose the algorithm CAST that applies trace Lasso to regularize the coefficient matrix. We prove that the resulting coefficient matrix has the "grouping effect" and that it exhibits "sparsity". We show that these two characteristics imply very effective spectral clustering. We evaluate CAST and 10 other clustering methods on a wide range of datasets w.r.t. various measures. Experimental results show that CAST provides excellent performance and is highly robust across test cases of multi-scale data.

Temporal causal discovery aims to find cause-effect relationships between time-series. However, none of the existing techniques is able to identify the causal profile, the temporal pattern that the causal variable needs to follow in order to trigger the most significant change in the outcome. Toward a new horizon, this study introduces the novel problem of Causal Profile Discovery, which is crucial for many applications such as adverse drug reaction and cyber-attack detection. This work correspondingly proposes Heidegger to discover causal profiles, comprised of a flexible randomized block design for hypothesis evaluation and an efficient profile search via on-the-fly graph construction and entropy-based pruning. Heidegger's performance is demonstrated/evaluated extensively on both synthetic and real-world data. The experimental results show the proposed method is robust to noise and flexible at detecting complex patterns.

Graph embedding has become the research focus in both academic and industrial communities due to its powerful capabilities. The majority of existing work overwhelmingly learn node embeddings in the context of static, plain or attributed, homogeneous graphs. However, many real-world applications frequently involve bipartite graphs with temporal and attributed interaction edges, named temporal interaction graphs. The temporal interactions usually imply different facets of interest and might even evolve over time, thus putting forward huge challenges in learning effective node representations. In this paper, we propose a novel framework named TigeCMN to learn node representations from a sequence of temporal interactions. Specifically, we devise two coupled memory networks to store and update node embeddings in external matrices explicitly and dynamically, which forms deep matrix representations and could enhance the expressiveness of the node embeddings. We conduct experiments on two real-world datasets and the experimental results empirically demonstrate that TigeCMN can outperform the state-of-the-arts with different gains.

The e-commerce era is witnessing a rapid development of various annual online promotions, such as Black Friday, Cyber Monday, and Alibaba's 11.11, etc. S ales P redictions for O nline P romotions (SPOP) are a set of sales related forecasts for the promotion day, including gross merchandise volume, sales volume, best selling products, etc. SPOP is highly important for e-commerce platforms to efficiently organize merchandise and maximize business values. However, sales patterns during the promotions are varied according to different scenarios, each model of which is designed with different features, static or dynamic, for one task in particular. Therefore, several models are proposed with part of features that are possibly beneficial to other tasks, which indicates the universal representation for the items needs to be learned across different promotion scenarios. To address this problem, this paper proposes a D eep I tem N etwork for O nline P romotions (DINOP). In DINOP, we design a novel T arget U sers C ontrolled G ated R ecurrent U nit (TUC-GRU) structure for dynamic features, and provide a new attention mechanism introducing static users profiles. In contrast to traditional prediction models, the network we proposed can effectively and efficiently learn universal item representation by incorporating users' properties as controllers. Furthermore, it can successfully discover the static and dynamic features guided by the multi-task learning, and is easily extended to other sales related prediction problems without retraining. Empirical results show that performance of DINOP in the real data set of Alibaba's Global Shopping Festival is superior to other state-of-the-arts practical methodologies in terms of the convergence rate and prediction accuracy.

With the availability of abundant online multi-relational video information, recommender systems that can effectively exploit these sorts of data and suggest creatively interesting items will become increasingly important. Recent research illustrates that tensor models offer effective approaches for complex multi-relational data learning and missing element completion. So far, most tensor-based user clustering models have focused on the accuracy of recommendation. Given the dynamic nature of online media, recommendation in this setting is more challenging as it is difficult to capture the users’ dynamic topic distributions in sparse data settings as well as to identify unseen items as candidates of recommendation. Targeting at constructing a recommender system that can encourage more creativity, a deep Bayesian probabilistic tensor framework for tag and item recommendation is proposed. During the score ranking processes, a metric called Bayesian surprise is incorporated to increase the creativity of the recommended candidates. The new algorithm, called Deep Canonical PARAFAC Factorization (DCPF), is evaluated on both synthetic and large-scale real-world problems. An empirical study for video recommendation demonstrates the superiority of the proposed model and indicates that it can better capture the latent patterns of interactions and generates interesting recommendations based on creative tag combinations.

Users' consumption behaviors are affected by both their personal preference and their exposure to items (i.e. whether a user knows the items).Most of the recent works in social recommendation assume that people share similar preference with their socially connected friends. However, this assumption may not hold due to the diversity of social relations, and modeling social influence on users' preference may not be suitable for implicit feedback data (i.e. whether a user has consumed certain items). Since users often share item information with their social relations, it will be less restrictive to model social influence on users' exposure to items. We notice that a user's exposure is affected by the exposure of the other users in his social communities and by the consumption of his connected friends. In this paper, we propose a novel social exposure-based recommendation model SoEXBMF by integrating two kinds of social influence on users' exposure, i.e. social knowledge influence and social consumption influence, into basic EXMF model for better recommendation performance. Furthermore, SoEXBMF uses Bernoulli distribution instead of Gaussian distribution in EXMF to better model the binary implicit feedback data. A variational inference method has been developed for the proposed SoEXBMF model to infer the posterior and make the recommendations. Extensive experiments on three real-world datasets demonstrate the superiority of our method over existing methods in various evaluation metrics.

With over 34 billion IoT devices to be installed by 2020, the Internet of Things (IoT) is fundamentally changing our lives. One of the greatest benefits of the IoT is the powerful automations achieved by applying rules to IoT devices. For instance, a rule named "Make me a cup of coffee when I wake up'' automatically turns on the coffee machine when the sensor in the bedroom detects motion in the morning. With large numbers of possible rules out there, a recommendation system is of great necessity to help users find rules they need. However, little effort has been made to design a model tailored for the IoT rule recommendation, which comes with lots of new challenges compared with traditional recommendation tasks. We not only need to re-define "users'' and "items'' in the recommendation task, but also have to consider a new type of entities, devices, and the extra information and constraints brought by them. To handle these challenges, we propose a novel efficient recommendation algorithm, which not only considers the implicit feedback of users on rules, but also takes user-rule-device interactions and the match between rule device requirements and user device possessions into account. In collaboration with Samsung, one of the leading companies in this field, we have designed an IoT rule recommendation framework and evaluated our algorithm on a real-life industry dataset. Experiments show the effectiveness and efficiency of our method.

Attributed network embedding focuses on learning low-dimensional latent representations of nodes which can well preserve the original topological and node attributed proximity at the same time. Existing works usually assume that nodes with similar topology or similar attributes should also be close in the embedding space. This assumption ignores the phenomenon of partial correlation between network topological and node attributed similarities i.e. nodes with similar topology may be dissimilar in their attributes and vice versa. Partial correlation between the two information sources should be considered especially when there exist fraudulent edges (i.e., information from one source is vague) or unbalanced data distributions (i.e, topology structure similarity and node attribute similarity have different distributions). However, it is very challenging to consider the partial correlation between topology and attributes due to the heterogeneity of these two information sources. In this paper, we take partial correlation between topology and attributes into account and propose the Personalized Relation Ranking Embedding (PRRE) method for attributed networks which is capable of exploiting the partial correlation between node topology and attributes. The proposed PRRE model utilizes two thresholds to define different node relations and employs the Expectation-Maximization (EM) algorithm to learn these thresholds as well as other embedding parameters. Extensive experiments results on multiple real-world datasets show that the proposed PRRE model significantly outperforms the state-of-the-art methods in terms of various evaluation metrics.

With the explosive growth of online social networks, many social recommendation methods have been proposed and demonstrated that social information has potential to improve the recommendation performance. However, existing social recommendation methods always assume that the data is missing at random (MAR) but this is rarely the case. In fact, by analysing two real-world social recommendation datasets, we observed the following interesting phenomena: (1) users tend to consume and rate the items that they like and the items that have been consumed by their friends. (2) When the items have been consumed by more friends, the average values of the observed ratings will become smaller, not larger as assumed by the existing models. To model these phenomena, we integrate the missing not at random (MNAR) assumption in social recommendation and propose a new social recommendation method SPMF-MNAR, which models the observation process of rating data based on user's preference and social influence. Extensive experiments conducted on large real-world datasets validate that SPMF-MNAR achieves better performance than existing social recommendation methods and the non-social methods based on MNAR assumption.

The e-commerce era is witnessing a rapid increase of mobile Internet users. Major e-commerce companies nowadays see billions of mobile accesses every day. Hidden in these records are valuable user behavioral characteristics such as their shopping preferences and browsing patterns. And, to extract these knowledge from the huge dataset, we need to first link records to the corresponding mobile devices. This Mobile Access Records Resolution (MARR) problem is confronted with two major challenges: (1) device identifiers and other attributes in access records might be missing or unreliable; (2) the dataset contains billions of access records from millions of devices. To the best of our knowledge, as a novel challenge industrial problem of mobile Internet, no existing method has been developed to resolve entities using mobile device identifiers in such a massive scale. To address these issues, we propose a SParse Identifier-linkage Graph (SPI-Graph) accompanied with the abundant mobile device profiling data to accurately match mobile access records to devices. Furthermore, two versions (unsupervised and semi-supervised) of Parallel Graph-based Record Resolution (PGRR) algorithm are developed to effectively exploit the advantages of the large-scale server clusters comprising of more than 1,000 computing nodes. We empirically show superior performances of PGRR algorithms in a very challenging and sparse real data set containing 5.28 million nodes and 31.06 million edges from 2.15 billion access records compared to other state-of-the-arts methodologies.

We investigate the effectiveness of spectral methods in clustering multi-scale data, which is data whose clusters are of various sizes and densities. We review existing spectral methods that are designed to handle multi-scale data and propose an alternative approach that is orthogonal to existing methods. We put forward the algorithm ROSC, which computes an affinity matrix that takes into account both objects' feature similarity and reachability similarity. We perform extensive experiments comparing ROSC against 9 other methods on both real and synthetic datasets. Our results show that ROSC performs very well against the competitors. In particular, it is very robust in that it consistently performs well over all the datasets tested. Also, it outperforms others by wide margins for datasets that are highly multi-scale.

The problem of social event organization (SEO) rises with the advent of online web services and plays an important role in helping users discover new offline events. Existing work on SEO only assumes that different users have different preferences towards different events, ignoring the fact that each event (its organizer) may have a separate preference towards every user. In this paper, we investigate joint user- and event- driven SEO by simultaneously considering user preferences (towards events) and event preferences (towards users). A risen challenging problem is that this joint consideration may suffer instabilities between users and events which are NP-hard to handle in SEO. Stability is a desired property that needs to be maintained in SEO, otherwise participants will incline towards changing to other events and trust less the organizer.

Social recommendation has been an active research topic over the last decade, based on the assumption that social information from friendship networks is beneficial for improving recommendation accuracy, especially when dealing with cold-start users who lack sufficient past behavior information for accurate recommendation. However, it is nontrivial to use such information, since some of a person's friends may share similar preferences in certain aspects, but others may be totally irrelevant for recommendations. Thus one challenge is to explore and exploit the extend to which a user trusts his/her friends when utilizing social information to improve recommendations. On the other hand, most existing social recommendation models are non-interactive in that their algorithmic strategies are based on batch learning methodology, which learns to train the model in an offline manner from a collection of training data which are accumulated from users? historical interactions with the recommender systems. In the real world, new users may leave the systems for the reason of being recommended with boring items before enough data is collected for training a good model, which results in an inefficient customer retention. To tackle these challenges, we propose a novel method for interactive social recommendation, which not only simultaneously explores user preferences and exploits the effectiveness of personalization in an interactive way, but also adaptively learns different weights for different friends. In addition, we also give analyses on the complexity and regret of the proposed model. Extensive experiments on three real-world datasets illustrate the improvement of our proposed method against the state-of-the-art algorithms.

A heterogeneous information network (HIN) is one whose nodes model objects of different types and whose links model objects' relationships. In many applications, such as social networks and RDF-based knowledge bases, information can be modeled as HINs. To enrich its information content, objects (as represented by nodes) in an HIN are typically associated with additional attributes. We call such an HIN an Attributed HIN or AHIN. We study the problem of clustering objects in an AHIN, taking into account objects' similarities with respect to both object attribute values and their structural connectedness in the network. We show how supervision signal, expressed in the form of a must-link set and a cannot-link set, can be leveraged to improve clustering results. We put forward the SCHAIN algorithm to solve the clustering problem. We conduct extensive experiments comparing SCHAIN with other state-of-the-art clustering algorithms and show that SCHAIN outperforms the others in clustering quality.

Recent years have seen a surge of research on social recommendation techniques for improving recommender systems due to the growing influence of social networks to our daily life. The intuition of social recommendation is that users tend to show affinities with items favored by their social ties due to social influence. Despite the extensive studies, no existing work has attempted to distinguish and learn the personalized preferences between strong and weak ties, two important terms widely used in social sciences, for each individual in social recommendation. In this paper, we first highlight the importance of different types of ties in social relations originated from social sciences, and then propose anovel social recommendation method based on a new Probabilistic Matrix Factorization model that incorporates the distinction of strong and weak ties for improving recommendation performance. The proposed method is capable of simultaneously classifying different types of social ties in a social network w.r.t. optimal recommendation accuracy, and learning a personalized tie type preference for each user in addition to other parameters. We conduct extensive experiments on four real-world datasets by comparing our method with state-of-the-art approaches, and find encouraging results that validate the efficacy of the proposed method in exploiting the personalized preferences of strong and weak ties for social recommendation.

Twitter, together with other online social networks, such as Facebook, and Gowalla have begun to collect hundreds of millions of check-ins. Check-in data captures the spatial and temporal information of user movements and interests. To model and analyze the spatio-temporal aspect of check-in data and discover temporal topics and regions, we first propose a spatio-temporal topic model, i.e., Upstream Spatio-Temporal Topic Model (USTTM). USTTM can discover temporal topics and regions, i.e., a user's choice of region and topic is affected by time in this model. We use continuous time to model check-in data, rather than discretized time, avoiding the loss of information through discretization. In addition, USTTM captures the property that user's interests and activity space will change overtime, and users have different region and topic distributions at different times in USTTM. However, both USTTM and other related models capture “microscopic patterns” within a single city, where users share POIs, and cannot discover “macroscopic” patterns in a global area, where users check-in to different POIs. Therefore, we also propose a macroscopic spatio-temporal topic model, MSTTM, employing words of tweets that are shared between cities to learn the topics of user interests. We perform an experimental evaluation on Twitter and Gowalla data sets from New York City and on a Twitter US data set. In our qualitative analysis, we perform experiments with USTTM to discover temporal topics, e.g., how topic “tourist destinations” changes over time, and to demonstrate that MSTTM indeed discovers macroscopic, generic topics. In our quantitative analysis, we evaluate the effectiveness of USTTM in terms of perplexity, accuracy of POI recommendation, and accuracy of user and time prediction. Our results show that the proposed USTTM achieves better performance than the state-of-the-art models, confirming that it is more natural to model time as an upstream variable affecting the other variables. Finally, the performance of the macroscopic model MSTTM is evaluated on a Twitter US dataset, demonstrating a substantial improvement of POI recommendation accuracy compared to the microscopic models.

At SIGMOD 2015, an article was presented with the title “DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation” that won the conference’s best paper award. In this technical correspondence, we want to point out some inaccuracies in the way DBSCAN was represented, and why the criticism should have been directed at the assumption about the performance of spatial index structures such as R-trees and not at an algorithm that can use such indexes. We will also discuss the relationship of DBSCAN performance and the indexability of the dataset, and discuss some heuristics for choosing appropriate DBSCAN parameters. Some indicators of bad parameters will be proposed to help guide future users of this algorithm in choosing parameters such as to obtain both meaningful results and good performance. In new experiments, we show that the new SIGMOD 2015 methods do not appear to offer practical benefits if the DBSCAN parameters are well chosen and thus they are primarily of theoretical interest. In conclusion, the original DBSCAN algorithm with effective indexes and reasonably chosen parameter values performs competitively compared to the method proposed by Gan and Tao.

With the explosive growth of online social networks, it is now well understood that social information is highly helpful to recommender systems. Social recommendation methods are capable of battling the critical cold-start issue, and thus can greatly improve prediction accuracy. The main intuition is that through trust and influence, users are more likely to develop affinity toward items consumed by their social ties. Despite considerable work in social recommendation, little attention has been paid to the important distinctions between strong and weak ties, two well-documented notions in social sciences. In this work, we study the effects of distinguishing strong and weak ties in social recommendation. We use neighbourhood overlap to approximate tie strength and extend the popular Bayesian Personalized Ranking (BPR) model to incorporate the distinction of strong and weak ties. We present an EM-based algorithm that simultaneously classifies strong and weak ties in a social network w.r.t. optimal recommendation accuracy and learns latent feature vectors for all users and all items. We conduct extensive empirical evaluation on four real-world datasets and demonstrate that our proposed method significantly outperforms state-of-the-art pairwise ranking methods in a variety of accuracy metrics.

With email overload becoming a billion-level drag on the economy, personalized email prioritization is of urgent need to help predict the importance level of an email. Despite lots of previous effort on the topic, broadcast email, an important type of emails with its unique challenges and intriguing opportunities, has been overlooked. The most salient opportunity lies in that effective collaborative filtering can be exploited due to thousands of receivers of a typical broadcast email. However, every broadcast email is completely cold and it is very costly to obtain users' preference feedback. Fortunately, there exist up to million-level broadcast mailing lists in a real life email system. Similar mailing lists can provide useful extra information for broadcast email prioritization in a target mailing list. How to mine such useful extra information is a challenging problem that has never been touched. In this work, we propose the first broadcast email prioritization framework considering large numbers of mailing lists by formulating this problem as a cross domain recommendation problem. An optimization framework is proposed to select the optimal set of source domains considering multiple criteria including overlap of users, feedback pattern similarity and coverage of users. Our method is thoroughly evaluated on a real world industrial dataset from Samsung Electronics and is proved highly effective and outperforms all the baselines.

research-article Share on Collaborative Denoising Auto-Encoders for Top-N Recommender Systems Authors: Yao Wu Simon Fraser University, Burnaby, BC, Canada Simon Fraser University, Burnaby, BC, CanadaView Profile , Christopher DuBois Dato Inc., Seattle, WA, USA Dato Inc., Seattle, WA, USAView Profile , Alice X. Zheng Dato Inc., Seattle, WA, USA Dato Inc., Seattle, WA, USAView Profile , Martin Ester Simon Fraser University, Burnaby, BC, Canada Simon Fraser University, Burnaby, BC, CanadaView Profile Authors Info & Claims WSDM '16: Proceedings of the Ninth ACM International Conference on Web Search and Data MiningFebruary 2016Pages 153–162https://doi.org/10.1145/2835776.2835837Published:08 February 2016Publication History 551citation3,811DownloadsMetricsTotal Citations551Total Downloads3,811Last 12 Months393Last 6 weeks24 Get Citation Alerts

Collaborative Filtering (CF) is the most popular method for recommender systems. The principal idea of CF is that users might be interested in items that are favorited by similar users, and most of the existing CF methods measure users' preferences by their behaviours over all the items. However, users might have different interests over different topics, thus might share similar preferences with different groups of users over different sets of items. In this paper, we propose a novel and scalable method CCCF which improves the performance of CF methods via user-item co-clustering. CCCF first clusters users and items into several subgroups, where each subgroup includes a set of like-minded users and a set of items in which these users share their interests. Then, traditional CF methods can be easily applied to each subgroup, and the recommendation results from all the subgroups can be easily aggregated. Compared with previous works, CCCF has several advantages including scalability, flexibility, interpretability and extensibility. Experimental results on four real world data sets demonstrate that the proposed method significantly improves the performance of several state-of-the-art recommendation algorithms.

Email is one of the most important communication tools today, but email overload resulting from the large number of unimportant or irrelevant emails is causing trillion-level economy loss every year. Thus personalized email prioritization algorithms are of urgent need. Despite lots of previous effort on this topic, broadcast email, an important type of email, is overlooked in previous literature. Broadcast emails are significantly different from normal emails, introducing both new challenges and opportunities. On one hand, lack of real senders and limited user interactions invalidate the key features exploited by traditional email prioritization algorithms; on the other hand, thousands of receivers for one broadcast email bring us the opportunity to predict importance through collaborative filtering. However, broadcast emails face a severe cold-start problem which hinders the direct application of collaborative filtering. In this paper, we propose the first framework for broadcast email prioritization by designing a novel active learning model that considers the collaborative filtering, implicit feedback and time sensitive responsiveness features of broadcast emails. Our method is thoroughly evaluated on a large scale real world industrial dataset from Samsung Electronics. Our method is proved highly effective and outperforms state-of-the-art personalized email prioritization methods.

Advances in smartphone technology have promoted the rapid development of mobile apps. However, the availability of a huge number of mobile apps in application stores has imposed the challenge of finding the right apps to meet the user needs. Indeed, there is a critical demand for personalized app recommendations. Along this line, there are opportunities and challenges posed by two unique characteristics of mobile apps. First, app markets have organized apps in a hierarchical taxonomy. Second, apps with similar functionalities are competing with each other. Although there are a variety of approaches for mobile app recommendations, these approaches do not have a focus on dealing with these opportunities and challenges. To this end, in this article, we provide a systematic study for addressing these challenges. Specifically, we develop a structural user choice model (SUCM) to learn fine-grained user preferences by exploiting the hierarchical taxonomy of apps as well as the competitive relationships among apps. Moreover, we design an efficient learning algorithm to estimate the parameters for the SUCM model. Finally, we perform extensive experiments on a large app adoption dataset collected from Google Play. The results show that SUCM consistently outperforms state-of-the-art Top-N recommendation methods by a significant margin.

Twitter, together with other online social networks, such as Facebook, and Gowalla have begun to collect hundreds of millions of check-ins. Check-in data captures the spatial and temporal information of user movements and interests. To model and analyze the spatio-temporal aspect of check-in data and discover temporal topics and regions, we propose two spatio-temporal topic models: Downstream Spatio-Temporal Topic Model (DSTTM) and Upstream Spatio-Temporal Topic Model (USTTM). Both models can discover temporal topics and regions. We use continuous time to model check-in data, rather than discretized time, avoiding the loss of information through discretization. In order to capture the property that user's interests and activity space will change over time, we propose the USTTM, where users have different region and topic distributions at different times. We conduct experiments on Twitter and Gowalla data sets. In our quantitative analysis, we evaluate the effectiveness of our models by the perplexity, the accuracy of POI recommendations, and user prediction, demonstrating that our models achieve better performance than the state-of-the-art models.

Aspect-based opinion mining from online reviews has attracted a lot of attention recently. Given a set of reviews, the main task of aspect-based opinion mining is to extract major aspects of the items and to infer the latent aspect ratings from each review. However, users may have different preferences which might lead to different opinions on the same aspect of an item. Even if fine-grained aspect rating analysis is provided for each review, it is still difficult for a user to judge whether a specific aspect of an item meets his own expectation. In this paper, we study the problem of estimating personalized sentiment polarities on different aspects of the items. We propose a unified probabilistic model called Factorized Latent Aspect ModEl (FLAME), which combines the advantages of collaborative filtering and aspect based opinion mining. FLAME learns users' personalized preferences on different aspects from their past reviews, and predicts users' aspect ratings on new items by collective intelligence. Experiments on two online review datasets show that FLAME outperforms state-of-the-art methods on the tasks of aspect identification and aspect rating prediction.

Crime reduction and prevention strategies are vital for policymakers and law enforcement to face inevitable increases in urban crime rates as a side effect of the projected growth of urban population by the year 2030. Studies conclude that crime does not occur uniformly across urban landscapes but concentrates in certain areas. This phenomenon has drawn attention to spatial crime analysis, primarily focusing on crime hotspots, areas with disproportionally higher crime density. In this paper we present CRIMETRACER, a personalized random walk based approach to spatial crime analysis and crime location prediction outside of hotspots. We propose a probabilistic model of spatial behavior of known offenders within their activity space. Crime Pattern Theory concludes that offenders, rather than venture into unknown territory, frequently commit opportunistic crimes and serial violent crimes by taking advantage of opportunities they encounter in places they are most familiar with as part of their activity space. Our experiments on a large real-world crime dataset show that CRIMETRACER outperforms all other methods used for location recommendation we evaluate here.

In this paper, we address the problem of recommending Point-of-Interests (POIs) to users in a location-based social network. To the best of our knowledge, we are the first to propose the ST (Social Topic) model capturing both the social and topic aspects of user check-ins. We conduct experiments on real life data sets from Foursquare and Yelp. We evaluate the effectiveness of ST by evaluating the accuracy of top-k POI recommendation. The experimental results show that ST achieves better performance than the state-of-the-art models in the areas of social network-based recommender systems, and exploits the power of the location-based social network that has never been utilized before.

Crime reduction and prevention strategies are essential to increase public safety and reduce the crime costs to society. Law enforcement agencies have long realized the importance of analyzing co-offending networks---networks of offenders who have committed crimes together---for this purpose. Although network structure can contribute significantly to co-offence prediction, research in this area is very limited. Here we address this important problem by proposing a framework for co-offence prediction using supervised learning. Considering the available information about offenders, we introduce social, geographic, geo-social and similarity feature sets which are used for classifying potential negative and positive pairs of offenders. Similar to other social networks, co-offending networks also suffer from a highly skewed distribution of positive and negative pairs. To address the class imbalance problem, we identify three types of criminal cooperation opportunities which help to reduce the class imbalance ratio significantly, while keeping half of the co-offences. The proposed framework is evaluated on a large crime dataset for the Province of British Columbia, Canada. Our experimental evaluation of four different feature sets show that the novel geo-social features are the best predictors. Overall, we experimentally show the high effectiveness of the proposed co-offence prediction framework. We believe that our framework will not only allow law enforcement agencies to improve their crime reduction and prevention strategies, but also offers new criminological insights into criminal link formation between offenders.

Mobile networks enable users to post on social media services (e.g., Twitter) from anywhere and anytime. This new phenomenon led to the emergence of a new line of work of mining the behavior of mobile users taking into account the spatio-temporal aspects of their engagement with online social media. In this paper, we address the problem of recommending the right locations to users at the right time. We claim to propose the first comprehensive model, called STT (Spatio-Temporal Topic), to capture the spatio-temporal aspects of user check-ins in a single probabilistic model for location recommendation. Our proposed generative model does not only captures spatio-temporal aspects of check-ins, but also profiles users. We conduct experiments on real life data sets from Twitter, Go Walla, and Bright kite. We evaluate the effectiveness of STT by evaluating the accuracy of location recommendation. The experimental results show that STT achieves better performance than the state-of-the-art models in the areas of recommender systems as well as topic modeling.

No abstract available.

No abstract available.

Mobile networks enable users to post on social media services (e.g., Twitter) from anywhere. The activities of mobile users involve three major entities: user, post, and location. The interaction of these entities is the key to answer questions such as who will post a message where and on what topic? In this paper, we address the problem of profiling mobile users by modeling their activities, i.e., we explore topic modeling considering the spatial and textual aspects of user posts, and predict future user locations. We propose the first ST (Spatial Topic) model to capture the correlation between users' movements and between user interests and the function of locations. We employ the sparse coding technique which greatly speeds up the learning process. We perform experiments on two real life data sets from Twitter and Yelp. Through comprehensive experiments, we demonstrate that our proposed model consistently improves the average [email protected],5,10,15,20 for location recommendation by at least 50% (Twitter) and 300% (Yelp) against existing state-of-the-art recommendation algorithms and geographical topic models.

Aspect-based opinion mining from online reviews has attracted a lot of attention recently. The main goal of all of the proposed methods is extracting aspects and/or estimating aspect ratings. Recent works, which are often based on Latent Dirichlet Allocation (LDA), consider both tasks simultaneously. These models are normally trained at the item level, i.e., a model is learned for each item separately. Learning a model per item is fine when the item has been reviewed extensively and has enough training data. However, in real-life data sets such as those from Epinions.com and Amazon.com more than 90% of items have less than 10 reviews, so-called cold start items. State-of-the-art LDA models for aspect-based opinion mining are trained at the item level and therefore perform poorly for cold start items due to the lack of sufficient training data. In this paper, we propose a probabilistic graphical model based on LDA, called Factorized LDA (FLDA), to address the cold start problem. The underlying assumption of FLDA is that aspects and ratings of a review are influenced not only by the item but also by the reviewer. It further assumes that both items and reviewers can be modeled by a set of latent factors which represent their aspect and rating distributions. Different from state-of-the-art LDA models, FLDA is trained at the category level and learns the latent factors using the reviews of all the items of a category, in particular the non cold start items, and uses them as prior for cold start items. Our experiments on three real-life data sets demonstrate the improved effectiveness of the FLDA model in terms of likelihood of the held-out test set. We also evaluate the accuracy of FLDA based on two application-oriented measures.

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.

As social networking is moving into the web, the study and exploitation of social correlation has emerged as a hot research topic. Most of these work consider binary social relations, called "friendships". However, online users tend to establish many friendships of varying degree of strength, e.g., relatives, friends, co-workers, and acquaintances. We argue that, due to their different degree of strength, different friend relationships will have greatly varying degrees of correlation and should be distinguished. Besides, social correlation is not the only factor driving user behavior. In this paper, we address the problem of learning the strength of the social correlation, user, item, and sparsity factors in online social networks. We propose a probabilistic model, Factor Weight Model, for learning these strengths which maximize the joint probability of the observed user behavior, i.e., actions on items. Different from existing methods, our model considers not only social correlation, but it also considers the other factors affecting user behavior. We have conducted experiments on four real life data sets from Epinions, Flixster, Flickr, and Digg. Our experiments prove the superiority of our model over a state-of-the-art method in terms of action prediction. We also analyze the contributions of the various factors for the prediction performance.

In recent years, social media websites, such as Epinions, Twitter, and Google+, have gained in popularity and have become ubiquitous in our daily lives, where rich user-generated texts are propagated through social networks. Topic models, such as Latent Dirichlet Allocation (LDA), have been proposed and shown to be useful for text analysis. The existing topic models focus on traditional document collections, which consist of a relatively small number of long and high-quality documents. However, user-generated texts tend to be shorter and noisier than traditional content. Besides, the social networks have two novel features: context information on nodes, such as user features, and edges, such as relationship, which have not been considered by the existing topic models. In this paper, we pose the problem of finding user topics in large-scale collection of documents from online social networks. We propose a comprehensive Feature based and a Social based Topic model, taking into account the user features and social networks. We demonstrate that our models have better performance than a baseline LDA in the Epinions, Twitter, and Google+ data sets.

Aspect-based opinion mining, which aims to extract aspects and their corresponding ratings from customers reviews, provides very useful information for customers to make purchase decisions. In the past few years several probabilistic graphical models have been proposed to address this problem, most of them based on Latent Dirichlet Allocation (LDA). While these models have a lot in common, there are some characteristics that distinguish them from each other. These fundamental differences correspond to major decisions that have been made in the design of the LDA models. While research papers typically claim that a new model outperforms the existing ones, there is normally no "one-size-fits-all" model. In this paper, we present a set of design guidelines for aspect-based opinion mining by discussing a series of increasingly sophisticated LDA models. We argue that these models represent the essence of the major published methods and allow us to distinguish the impact of various design decisions. We conduct extensive experiments on a very large real life dataset from Epinions.com (500K reviews) and compare the performance of different models in terms of the likelihood of the held-out test set and in terms of the accuracy of aspect identification and rating prediction.

Assessing the significance of data mining results is an important step in the knowledge discovery process. While results might appear interesting at a first glance, they can often be explained by already known characteristics of the data. Randomization is an established technique for significance testing, and methods to assess data mining results on vector data or network data have been proposed. In many applications, however, both sources are simultaneously given. Since these sources are rarely independent of each other but highly correlated, naively applying existing randomization methods on each source separately is questionable. In this work, we present a method to assess the significance of mining results on graphs with binary features vectors. We propose a novel null model that preserves correlation information between both sources. Our randomization exploits an adaptive Metropolis sampling and interweaves attribute randomization and graph randomization steps. In thorough experiments, we demonstrate the application of our technique. Our results indicate that while simultaneously using both sources is beneficial, often one source of information is dominant for determining the mining results.

"What other people think" has always been an important piece of information for most of us during the decision-making process. Today people tend to make their opinions available to other people via the Internet. As a result, the Web has become an excellent source of consumer opinions. There are now numerous Web resources containing such opinions, e.g., product reviews forums, discussion groups, and blogs. But, it is really difficult for a customer to read all of the reviews and make an informed decision on whether to purchase the product. It is also difficult for the manufacturer of the product to keep track and manage customer opinions. Also, focusing on just user ratings (stars) is not a sufficient source of information for a user or the manufacturer to make decisions. Therefore, mining online reviews (opinion mining) has emerged as an interesting new research direction. Extracting aspects and the corresponding ratings is an important challenge in opinion mining. An aspect is an attribute or component of a product, e.g. 'zoom' for a digital camera. A rating is an intended interpretation of the user satisfaction in terms of numerical values. Reviewers usually express the rating of an aspect by a set of sentiments, e.g. 'great zoom'. In this tutorial we cover opinion mining in online product reviews with the focus on aspect-based opinion mining. This problem is a key task in the area of opinion mining and has attracted a lot of researchers in the information retrieval community recently. Several opinion related information retrieval tasks can benefit from the results of aspect-based opinion mining and therefore it is considered as a fundamental problem. This tutorial covers not only general opinion mining and retrieval tasks, but also state-of-the-art methods, challenges, applications, and also future research directions of aspect-based opinion mining.

Online reviews are valuable sources of information for a variety of decision-making processes such as purchasing products. As the number of online reviews is growing rapidly, it becomes increasingly difficult for users to identify those that are helpful. This has motivated research into the problem of identifying high quality and helpful reviews automatically. The current methods assume that the helpfulness of a review is independent from the readers of that review. However, we argue that the quality of a review may not be the same for different users. For example, a professional and an amateur photographer may rate the helpfulness of a review very differently. In this paper, we introduce the problem of predicting a personalized review quality for recommendation of helpful reviews. To address this problem, we propose a series of increasingly sophisticated probabilistic graphical models, based on Matrix Factorization and Tensor Factorization. We evaluate the proposed models using a database of 1.5 million reviews and more than 13 million quality ratings obtained from Epinions.com. The experiments demonstrate that the proposed latent factor models outperform the state-of-the art approaches using textual and social features. Finally, our experiments confirm that the helpfulness of a review is indeed not the same for all users and that there are some latent factors that affect a user's evaluation of the review quality.

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.

The problem of identifying high quality and helpful reviews automatically has attracted many attention recently. Current methods assume that the helpfulness of a review is independent from the readers of that review. However, we argue that the quality of a review may not be the same for different users. In this paper, we employ latent factor models to address this problem. We evaluate the proposed models using a real life database from Epinions.com. The experiments demonstrate that the latent factor models outperform the state-of-the-art approaches and confirms that the helpfulness of a review is indeed not the same for all users.

The rapidly increasing availability of online social networks and the well-known effect of social influence have motivated research on social-network based recommenders. Social influence and selection together lead to the formation of communities of like-minded and well connected users. Exploiting the clustering of users and items is one of the most important approaches for model-based recommendation. Users may belong to multiple communities or groups, but only a few clustering algorithms allow clusters to overlap. One of these algorithms is the probabilistic EM clustering method, which assumes that data is generated from a mixture of Gaussian models. The mixed membership stochastic block model (MMB) transfers the idea of EM clustering from conventional, non-relational data to social network data. In this paper, we introduce a generalized stochastic blockmodel (GSBM) that models not only the social relations but also the rating behavior. This model learns the mixed group membership assignments for both users and items in an SRN. GSBM can predict the future behavior of users, both the rating of items and creation of links to other users. We performed experiments on two real life datasets from Epinions.com and Flixster.com, demonstrating the accuracy of the proposed GSBM for rating prediction as well as link prediction.

Law enforcement and intelligence agencies have long realized that analysis of co-offending networks, networks of offenders who have committed crimes together, is invaluable for crime investigation, crime reduction and prevention. Investigating crime can be a challenging and difficult task, especially in cases with many potential suspects and inconsistent witness accounts or inconsistencies between witness accounts and physical evidence. We present here a novel approach to crime suspect recommendation based on partial knowledge of offenders involved in a crime incident and a known co-offending network. To solve this problem, we propose a random walk based method for recommending the top-K potential suspects. By evaluating the proposed method on a large crime dataset for the Province of British Columbia, Canada, we show experimentally that this method outperforms baseline random walk and association rule-based methods. Additionally, results obtained for public domain data from experiments for co-author recommendation on a DBLP co-authorship network are consistent with those on the crime dataset. Compared to the crime dataset, the performance of all competitors is much better on the DBLP dataset, confirming that crime suspect recommendation is an inherently harder task.

Today, more and more product reviews become available on the Internet, e.g., product review forums, discussion groups, and Blogs. However, it is almost impossible for a customer to read all of the different and possibly even contradictory opinions and make an informed decision. Therefore, mining online reviews (opinion mining) has emerged as an interesting new research direction. Extracting aspects and the corresponding ratings is an important challenge in opinion mining. An aspect is an attribute or component of a product, e.g. 'screen' for a digital camera. It is common that reviewers use different words to describe an aspect (e.g. 'LCD', 'display', 'screen'). A rating is an intended interpretation of the user satisfaction in terms of numerical values. Reviewers usually express the rating of an aspect by a set of sentiments, e.g. 'blurry screen'. In this paper we present three probabilistic graphical models which aim to extract aspects and corresponding ratings of products from online reviews. The first two models extend standard PLSI and LDA to generate a rated aspect summary of product reviews. As our main contribution, we introduce Interdependent Latent Dirichlet Allocation (ILDA) model. This model is more natural for our task since the underlying probabilistic assumptions (interdependency between aspects and ratings) are appropriate for our problem domain. We conduct experiments on a real life dataset, Epinions.com, demonstrating the improved effectiveness of the ILDA model in terms of the likelihood of a held-out test set, and the accuracy of aspects and aspect ratings.

A social rating network (SRN) is a social network in which edges represent social relationships and users (nodes) express ratings on some of the given items. Such networks play an increasingly important role in reviewing websites such as Epinions.com or online sharing websites like Flickr.com. In this paper, we first observe and analyze the temporal behavior of users in a social rating network, who express ratings and create social relations. Then, we model the temporal dynamics of an SRN based on our observations, using the bidirectional effects of ratings and social relations. While existing models for other types of social networks have captured some of the effects, our model is the first one to represent all four effects, i.e. social relations-on-ratings (social influence), social relations-on-social relations (transitivity), ratings-on-social relations (selection), and ratings-on-ratings (correlational influence). Existing works consider these effects as static and constant throughout the evolution of an SRN, however our observations reveal that these effects are actually dynamic. We propose a probabilistic generative model for SRNs, which models the strength and dynamics of each effect throughout the network evolution. This model can serve for the prediction of future links, ratings or community structures. Due to the sensitive nature of SRNs, another motivation for our work is the generation of synthetic SRN data sets for research purposes. Our experimental studies on two real life datasets (Epinions and Flickr) demonstrate that the proposed model produces social rating networks that agree with real world data on a comprehensive set of evaluation criteria.

We propose a pipelined supervised learning approach named SDOI to the task of interlinking the concepts mentioned within a document to the concepts within an ontology. Concept mention identification is performed by training a sequential tagging model. Each identified concept mention is then associated with a set of candidate ontology concepts along with a feature vector based on features proposed in the literature and novel ones based on new data sources, such as from the training corpus itself. An iterative algorithm is defined for handling collective features. We show a lift in performance over applicable baselines against the ability to identify the concept mentions within the 139 KDD-2009 conference paper abstracts, and to link these concept mentions to a domain-specific ontology for the field of data mining. Additional experiments of 22 ICDM-2009 abstracts suggest that the trained models are portable both in terms of accuracy and in their ability to reduce annotation time.

Mining customer reviews (opinion mining) has emerged as an interesting new research direction. Most of the reviewing websites such as Epinions.com provide some additional information on top of the review text and overall rating, including a set of predefined aspects and their ratings, and a rating guideline which shows the intended interpretation of the numerical ratings. However, the existing methods have ignored this additional information. We claim that using this information, which is freely available, along with the review text can effectively improve the accuracy of opinion mining. We propose an unsupervised method, called Opinion Digger, which extracts important aspects of a product and determines the overall consumer's satisfaction for each, by estimating a rating in the range from 1 to 5. We demonstrate the improved effectiveness of our methods on a real life dataset that we crawled from Epinions.com.

When a database system is extended with the skyline operator, it is important to determine the most efficient way to execute a skyline query across tables with join operations. This paper describes a framework for evaluating skylines in the presence of equijoins, including: (1) the development of algorithms to answer such queries over large input tables in a non-blocking, pipeline fashion, which significantly speeds up the entire query evaluation time. These algorithms are built on top of the traditional relational Nested-Loop and the Sort-Merge join algorithms, which allows easy implementation of these methods in existing relational systems; (2) a novel method for estimating the skyline selectivity of the joined table; (3) evaluation of skyline computation based on the estimation method and the proposed evaluation techniques; and (4) a systematic experimental evaluation to validate our skyline evaluation framework.

Recommender systems are becoming tools of choice to select the online information relevant to a given user. Collaborative filtering is the most popular approach to building recommender systems and has been successfully employed in many applications. With the advent of online social networks, the social network based approach to recommendation has emerged. This approach assumes a social network among users and makes recommendations for a user based on the ratings of the users that have direct or indirect social relations with the given user. As one of their major benefits, social network based approaches have been shown to reduce the problems with cold start users. In this paper, we explore a model-based approach for recommendation in social networks, employing matrix factorization techniques. Advancing previous work, we incorporate the mechanism of trust propagation into the model. Trust propagation has been shown to be a crucial phenomenon in the social sciences, in social network analysis and in trust-based recommendation. We have conducted experiments on two real life data sets, the public domain Epinions.com dataset and a much larger dataset that we have recently crawled from Flixster.com. Our experiments demonstrate that modeling trust propagation leads to a substantial increase in recommendation accuracy, in particular for cold start users.

Spatial classification is the task of learning models to predict class labels based on the features of entities as well as the spatial relationships to other entities and their features. Spatial data can be represented as multi-relational data, however it presents novel challenges not present in multi-relational problems. One such problem is that spatial relationships are embedded in space, unknown a priori, and it is part of the algorithm’s task to determine which relationships are important and what properties to consider. In order to determine when two entities are spatially related in an adaptive and non-parametric way, we propose a Voronoi-based neighbourhood definition upon which spatial literals can be built. Properties of these neighbourhoods also need to be described and used for classification purposes. Non-spatial aggregation literals already exist within the multi-relational framework, but are not sufficient for comprehensive spatial classification. A formal set of additions to the multi-relational data mining framework is proposed, to be able to represent spatial aggregations as well as spatial features and literals. These additions allow for capturing more complex interactions and spatial occurrences such as spatial trends. In order to more efficiently perform the rule learning and exploit powerful multi-processor machines, a scalable parallelized method capable of reducing the runtime by several factors is presented. The method is compared against existing methods by experimental evaluation on a real world crime dataset which demonstrate the importance of the neighbourhood definition and the advantages of parallelization.

Collaborative filtering is the most popular approach to build recommender systems and has been successfully employed in many applications. However, it cannot make recommendations for so-called cold start users that have rated only a very small number of items. In addition, these methods do not know how confident they are in their recommendations. Trust-based recommendation methods assume the additional knowledge of a trust network among users and can better deal with cold start users, since users only need to be simply connected to the trust network. On the other hand, the sparsity of the user item ratings forces the trust-based approach to consider ratings of indirect neighbors that are only weakly trusted, which may decrease its precision. In order to find a good trade-off, we propose a random walk model combining the trust-based and the collaborative filtering approach for recommendation. The random walk model allows us to define and to measure the confidence of a recommendation. We performed an evaluation on the Epinions dataset and compared our model with existing trust-based and collaborative filtering methods.

Top-N item recommendation is one of the important tasks of recommenders. Collaborative filtering is the most popular approach to building recommender systems which can predict ratings for a given user and item. Collaborative filtering can be extended for top-N recommendation, but this approach does not work accurately for cold start users that have rated only a very small number of items. In this paper we propose novel methods exploiting a trust network to improve the quality of top-N recommendation. The first method performs a random walk on the trust network, considering the similarity of users in its termination condition. The second method combines the collaborative filtering and trust-based approach. Our experimental evaluation on the Epinions dataset demonstrates that approaches using a trust network clearly outperform the collaborative filtering approach in terms of recall, in particular for cold start users.

With the advent of online social networks, the trust-based approach to recommendation has emerged which exploits the trust network among users and makes recommendations based on the ratings of trusted users in the network. In this paper, we introduce a two dimensional trust model which dynamically gets updated based on users's feedbacks, in contrast to static trust values in current trust models. Explorability measures the extent to which a user can rely on recommendations returned by the social network of a trusted user. Dependability represents the extent to which a user's own ratings can be trusted by users trusting him directly and indirectly. We propose a method to learn the values of explorability and dependability from raw trust data and feedback expressed by users on the recommendations they receive. Positive feedback will increase the trust and negative feedback will decrease the trust among users. We performed an evaluation on the Epinions dataset, demonstrating that exploiting user feedback results in lower prediction error compared to existing trust-based and collaborative filtering approaches.

The increasing availability of network data is creating a great potential for knowledge discovery from graph data. In many applications, feature vectors are given in addition to graph data, where nodes represent entities, edges relationships between entities, and feature vectors associated with the nodes represent properties of entities. Often features and edges contain complementary information. In such scenarios the simultaneous use of both data types promises more meaningful and accurate results. Along these lines, we introduce the novel problem of mining cohesive patterns from graphs with feature vectors, which combines the concepts of dense subgraphs and subspace clusters into a very expressive problem definition. A cohesive pattern is a dense and connected subgraph that has homogeneous values in a large enough feature subspace. We argue that this problem definition is natural in identifying small communities in social networks and functional modules in Protein-Protein interaction networks. We present the algorithm CoPaM (Cohesive Pattern Miner), which exploits various pruning strategies to efficiently find all maximal cohesive patterns. Our theoretical analysis proves the correctness of CoPaM, and our experimental evaluation demonstrates its effectiveness and efficiency.

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.

Most of the existing work on skyline query has been extensively used in decision support, recommending systems etc, and mainly focuses on the efficiency issue for a single table. However the data retrieved by users for the targeting skylines may often be stored in multiple tables, thus require to perform join operations among tables. As a result, the cost on computing skylines on the joined table will be increased dramatically due to its potentially increasing cardinality and dimensionality. In this paper, we systematically study the skyline operator on multi-relational databases, and propose solutions aiming to seamlessly integrating state-of-the-art join methods into skyline computation. Our experiments not only demonstrate that the proposed methods are efficient, but also show the promising applicability of extending skyline operator to other typical database operators such as join and aggregates.

Clustering with constraints is an emerging area of data mining research. However, most work assumes that the constraints are given as one large batch. In this paper we explore the situation where the constraints are incrementally given. In this way the user after seeing a clustering can provide positive and negative feedback via constraints to critique a clustering solution. We consider the problem of efficiently updating a clustering to satisfy the new and old constraints rather than reclustering the entire data set. We show that the problem of incremental clustering under constraints is NP-hard in general, but identify several sufficient conditions which lead to efficiently solvable versions. These translate into a set of rules on the types of constraints thatcan be added and constraint set properties that must be maintained. We demonstrate that this approach is more efficient than re-clustering the entire data set and has several other advantages.

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.

Clustering methods can be either data-driven or need-driven. Data-driven methods intend to discover the true structure of the underlying data while need-driven methods aims at organizing the true structure to meet certain application requirements. Thus, need-driven (e.g. constrained) clustering is able to find more useful and actionable clusters in applications such as energy aware sensor networks, privacy preservation, and market segmentation. However, the existing methods of constrained clustering require users to provide the number of clusters, which is often unknown in advance, but has a crucial impact on the clustering result. In this paper, we argue that a more natural way to generate actionable clusters is to let the application-specific constraints decide the number of clusters. For this purpose, we introduce a novel cluster model, Constraint-Driven Clustering (CDC), which finds an a priori unspecified number of compact clusters that satisfy all user-provided constraints. Two general types of constraints are considered, i.e. minimum significance constraints and minimum variance constraints, as well as combinations of these two types. We prove the NP-hardness of the CDC problem with different constraints. We propose a novel dynamic data structure, the CD-Tree, which organizes data points in leaf nodes such that each leaf node approximately satisfies the CDC constraints and minimizes the objective function. Based on CD-Trees, we develop an efficient algorithm to solve the new clustering problem. Our experimental evaluation on synthetic and real datasets demonstrates the quality of the generated clusters and the scalability of the algorithm.

In many applications, attribute and relationship data areavailable, carrying complementary information about real world entities. In such cases, a joint analysis of both types of data can yield more accurate results than classical clustering algorithms that either use only attribute data or only relationship (graph) data. The Connected k-Center (CkC) has been proposed as the first joint cluster analysis model to discover k clusters which are cohesive on both attribute and relationship data. However, it is well-known that prior knowledge on the number of clusters is often unavailable in applications such as community dentification and hotspot analysis. In this paper, we introduce and formalize the problem of discovering an a-priori unspecified number of clusters in the context of joint cluster analysis of attribute and relationship data, called Connected X Clusters (CXC) problem. True clusters are assumed to be compact and distinctive from their neighboring clusters in terms of attribute data and internally connected in terms of relationship data. Different from classical attribute-based clustering methods, the neighborhood of clusters is not defined in terms of attribute data but in terms of relationship data. To efficiently solve the CXC problem, we present JointClust, an algorithm which adopts a dynamic two-phase approach. In the first phase, we find so called cluster atoms. We provide a probability analysis for thisphase, which gives us a probabilistic guarantee, that each true cluster is represented by at least one of the initial cluster atoms. In the second phase, these cluster atoms are merged in a bottom-up manner resulting in a dendrogram. The final clustering is determined by our objective function. Our experimental evaluation on several real datasets demonstrates that JointClust indeed discovers meaningful and accurate clusterings without requiring the user to specify the number of clusters.

Recent studies on efficiently answering subspace skyline queries can be separated into two approaches. The first focused on pre-materializing a set of skylines points in various subspaces while the second focus on dynamically answering the queries by using a set of anchors to prune off skyline points through spatial reasoning. Despite effort to compress the pre-materialized subspace skylines through removal of redundancy, the storage space for the first approach remain exponential in the number of dimensions. The query time for the second approach on the other hand also grow substantially for data with higher dimensionality where the pruning power of anchors become much weaker. In this paper, we propose methods for answering subspace skyline query on high dimensional data such that both prematerialization storage and query time can be moderated. We propose novel notions of maximal partial-dominating space, maximal partial-dominated space and the maximal equality space between pairs of skyline objects in the full space and use these concepts as the foundation for answering subspace skyline queries for high dimensional data. Query processing involves mostly simple pruning operations while skyline computation is done only on a small subset of candidate skyline points in the subspace. We also develop a random sampling method to compute the subspace skyline in an on-line fashion. Extensive experiments have been conducted and demonstrated the efficiency and effectiveness of our methods.

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.

Projected clustering has emerged as a possible solution to the challenges associated with clustering in high dimensional data. A projected cluster is a subset of points together with a subset of attributes, such that the cluster points project onto a small range of values in each of these attributes, and are uniformly distributed in the remaining attributes. Existing algorithms for projected clustering rely on parameters whose appropriate values are difficult to set by the user, or are unable to identify projected clusters with few relevant attributes. In this paper, we present a robust algorithm for projected clustering that can effectively discover projected clusters in the data while minimizing the number of parameters required as input. In contrast to all previous approaches, our algorithm can discover, under very general conditions, the true number of projected clusters. We show through an extensive experimental evaluation that our algorithm: (1) significantly outperforms existing algorithms for projected clustering in terms of accuracy; (2) is effective in detecting very low-dimensional projected clusters embedded in high dimensional spaces; (3) is effective in detecting clusters with varying orientation in their relevant subspaces; (4) is scalable with respect to large data sets and high number of dimensions.

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.

Clustering is an important task in mining evolving data streams. Beside the limited memory and one-pass constraints, the nature of evolving data streams implies the following requirements for stream clustering: no assumption on the number of clusters, discovery of clusters with arbitrary shape and ability to handle outliers. While a lot of clustering algorithms for data streams have been proposed, they offer no solution to the combination of these requirements. In this paper, we present DenStream, a new approach for discovering clusters in an evolving data stream. The “dense” micro-cluster (named core-micro-cluster) is introduced to summarize the clusters with arbitrary shape, while the potential core-micro-cluster and outlier micro-cluster structures are proposed to maintain and distinguish the potential clusters and outliers. A novel pruning strategy is designed based on these concepts, which guarantees the precision of the weights of the micro-clusters with limited memory. Our performance study over a number of real and synthetic data sets demonstrates the effectiveness and efficiency of our method.

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.

Data summarization has been recognized as a fundamental operation in database systems and data mining with important applications such as data compression and privacy preservation. While the existing methods such as CF-values and DataBubbles may perform reasonably well, they cannot provide any guarantees on the quality of their results. In this paper, we introduce a summarization approach for numerical data based on discs formalizing the notion of quality. Our objective is to find a minimal set of discs, i.e. spheres satisfying a radius and a significance constraint, covering the given dataset. Since the proposed problem is NP-complete, we design two different approximation algorithms. These algorithms have a quality guarantee, but they do not scale well to large databases. However, the machinery from approximation algorithms allows a precise characterization of a further, heuristic algorithm. This heuristic, efficient algorithm exploits multi-dimensional index structures and can be well-integrated with database systems. The experiments show that our heuristic algorithm generates summaries that outperform the state-of-the-art data bubbles in terms of internal measures as well as in terms of external measures when using the data summaries as input for clustering methods

The skyline operator is important for multicriteria decision-making applications. Although many recent studies developed efficient methods to compute skyline objects in a given space, none of them considers skylines in multiple subspaces simultaneously. More importantly, the fundamental problem on the semantics of skylines remains open: Why and in which subspaces is (or is not) an object in the skyline? Practically, users may also be interested in the skylines in any subspaces. Then, what is the relationship between the skylines in the subspaces and those in the super-spaces? How can we effectively analyze the subspace skylines? Can we efficiently compute skylines in various subspaces and answer various analytical queries?In this article, we tackle the problem of multidimensional subspace skyline computation and analysis. We explore skylines in subspaces. First, we propose the concept of Skycube, which consists of skylines of all possible nonempty subspaces of a given full space. Once a Skycube is materialized, any subspace skyline queries can be answered online. However, Skycube cannot fully address the semantic concerns and may contain redundant information. To tackle the problem, we introduce a novel notion of skyline group which essentially is a group of objects that coincide in the skylines of some subspaces. We identify the decisive subspaces that qualify skyline groups in the subspace skylines. The new notions concisely capture the semantics and the structures of skylines in various subspaces. Multidimensional roll-up and drill-down analysis is introduced. We also develop efficient algorithms to compute Skycube, skyline groups and their decisive subspaces. A systematic performance study using both real data sets and synthetic data sets is reported to evaluate our approach.

The microeconomic framework for data mining [7] assumes that an enterprise chooses a decision maximizing the overall utility over all customers where the contribution of a customer is a function of the data available on that customer. In Catalog Segmentation, the enterprise wants to design k product catalogs of size r that maximize the overall number of catalog products purchased. However, there are many applications where a customer, once attracted to an enterprise, would purchase more products beyond the ones contained in the catalog. Therefore, in this paper, we investigate an alternative problem formulation, that we call Customer-Oriented Catalog Segmentation, where the overall utility is measured by the number of customers that have at least a specified minimum interest t in the catalogs. We formally introduce the Customer-Oriented Catalog Segmentation problem and discuss its complexity. Then we investigate two different paradigms to design efficient, approximate algorithms for the Customer-Oriented Catalog Segmentation problem, greedy (deterministic) and randomized algorithms. Since greedy algorithms may be trapped in a local optimum and randomized algorithms crucially depend on a reasonable initial solution, we explore a combination of these two paradigms. Our experimental evaluation on synthetic and real data demonstrates that the new algorithms yield catalogs of significantly higher utility compared to classical Catalog Segmentation algorithms.

The emergence of automated high-throughput sequencing technologies has resulted in a huge increase of the amount of DNA and protein sequences available in public databases. A promising approach for mining such biological sequence data is mining frequent subsequences. One way to limit the number of patterns discovered is to determine only the most specific frequent subsequences which subsume a large number of more general patterns. In the biological domain, a wealth of knowledge on the relationships between the symbols of the underlying alphabets (in particular, amino acids) of the sequences has been acquired, which can be represented in concept graphs. Using such concept graphs, much longer frequent patterns can be discovered which are more meaningful from a biological point of view. In this paper, we introduce the problem of mining most specific frequent patterns in biological data in the presence of concept graphs. While the well-known methods for frequent sequence mining typically follow the paradigm of bottom-up pattern generation, we present a novel top-down method (ToMMS) for mining such patterns. ToMMS (1) always generates more specific patterns before more general ones and (2) performs only minimal generalizations of infrequent candidate sequences. Due to these properties, the number of patterns generated and tested is minimized. Our experimental results demonstrate that ToMMS clearly outperforms state-of-the-art methods from the bioinformatics community as well as from the data mining community for reasonably low minimum support thresholds.

A number of medically important disease-causing bacteria (collectively called Gram-negative bacteria) are noted for the extra "outer" membrane that surrounds their cell. Proteins resident in this membrane (outer membrane proteins, or OMPs) are of primary research interest for antibiotic and vaccine drug design as they are on the surface of the bacteria and so are the most accessible targets to develop new drugs against. With the development of genome sequencing technology and bioinformatics, biologists can now deduce all the proteins that are likely produced in a given bacteria and have attempted to classify where proteins are located in a bacterial cell. However such protein localization programs are currently least accurate when predicting OMPs, and so there is a current need for the development of a better OMP classifier. Data mining research suggests that the use of frequent patterns has good performance in aiding the development of accurate and efficient classification algorithms. In this paper, we present two methods to identify OMPs based on frequent subsequences and test them on all Gram-negative bacterial proteins whose localizations have been determined by biological experiments. One classifier follows an association rule approach, while the other is based on support vector machines (SVMs). We compare the proposed methods with the state-of-the-art methods in the biological domain. The results demonstrate that our methods are better both in terms of accurately identifying OMPs and providing biological insights that increase our understanding of the structures and functions of these important proteins.

A major challenge in document clustering is the extremely high dimensionality. For example, the vocabulary for a document set can easily be thousands of words. On the other hand, each document often contains a small fraction of words in the vocabulary. These features require special handlings. Another requirement is hierarchical clustering where clustered documents can be browsed according to the increasing specificity of topics. In this paper, we propose to use the notion of frequent itemsets, which comes from association rule mining, for document clustering. The intuition of our clustering criterion is that each cluster is identified by some common words, called frequent itemsets, for the documents in the cluster. Frequent itemsets are also used to produce a hierarchical topic tree for clusters. By focusing on frequent items, the dimensionality of the document set is drastically reduced. We show that this method outperforms best existing methods in terms of both clustering accuracy and scalability.

Text clustering methods can be used to structure large sets of text or hypertext documents. The well-known methods of text clustering, however, do not really address the special problems of text clustering: very high dimensionality of the data, very large size of the databases and understandability of the cluster description. In this paper, we introduce a novel approach which uses frequent item (term) sets for text clustering. Such frequent sets can be efficiently discovered using algorithms for association rule mining. To cluster based on frequent term sets, we measure the mutual overlap of frequent sets with respect to the sets of supporting documents. We present two algorithms for frequent term-based text clustering, FTC which creates flat clusterings and HFTC for hierarchical clustering. An experimental evaluation on classical text documents as well as on web documents demonstrates that the proposed algorithms obtain clusterings of comparable quality significantly more efficiently than state-of-the- art text clustering algorithms. Furthermore, our methods provide an understandable description of the discovered clusters by their frequent term sets.

When automatically extracting information from the world wide web, most established methods focus on spotting single HTML-documents. However, the problem of spotting complete web sites is not handled adequately yet, in spite of its importance for various applications. Therefore, this paper discusses the classification of complete web sites. First, we point out the main differences to page classification by discussing a very intuitive approach and its weaknesses. This approach treats a web site as one large HTML-document and applies the well-known methods for page classification. Next, we show how accuracy can be improved by employing a preprocessing step which assigns an occurring web page to its most likely topic. The determined topics now represent the information the web site contains and can be used to classify it more accurately. We accomplish this by following two directions. First, we apply well established classification algorithms to a feature space of occurring topics. The second direction treats a site as a tree of occurring topics and uses a Markov tree model for further classification. To improve the efficiency of this approach, we additionally introduce a powerful pruning method reducing the number of considered web pages. Our experiments show the superiority of the Markov tree approach regarding classification accuracy. In particular, we demonstrate that the use of our pruning method not only reduces the processing time, but also improves the classification accuracy.

Collaborative filtering (CF) has become an important data mining technique to make personalized recommendations for books, web pages or movies, etc. One popular algorithm is the memory-based collaborative filtering, which predicts a user's preference based on his or her similarity to other users (instances) in the database. However, the tremendous growth of users and the large number of products, memory-based CF algorithms results in the problem of deciding the right instances to use during prediction, in order to reduce executive cost and excessive storage, and possibly to improve the generalization accuracy by avoiding noise and overfitting. In this paper, we focus our work on a typical user preference database that contains many missing values, and propose four novel instance reduction techniques called TURF1-TURF4 as a preprocessing step to improve the efficiency and accuracy of the memory-based CF algorithm. The key idea is to generate prediction from a carefully selected set of relevant instances. We evaluate the techniques on the well-known EachMovie data set. Our experiments showed that the proposed algorithms not just dramatically speed up the prediction, but also improved the accuracy.

Collaborative filtering uses a database about consumers' preferences to make personal product recommendations and is achieving widespread success in both E-Commerce and Information Filtering Applications nowadays. However, the traditional collaborative filtering algorithms do not scale well to the ever-growing number of consumers. The quality of the recommendation also needs to be improved in order to gain more trust from the consumers. In this paper, we present a novel method to improve the scalability and the accuracy of the collaborative filtering algorithm. We introduce an information theoretic approach to measure the relevance of a consumer (instance) for predicting the preference for the given product (target concept). The proposed method reduces the training data set by selecting only highly relevant instances. Our experimental evaluation on the well-known EachMovie data set shows that our method doesn't only significantly speed up the prediction, but also results in a better accuracy.

Metric databases are databases where a metric distance function is defined for pairs of database objects. In such databases, similarity queries in the form of range queries or k-nearest-neighbor queries are the most important query types. In traditional query processing, single queries are issued independently by different users. In many data mining applications, however, the database is typically explored by iteratively asking similarity queries for answers of previous similarity queries. We introduce a generic scheme for such data mining algorithms and we investigate two orthogonal approaches, reducing I/O cost as well as CPU cost, to speed-up the processing of multiple similarity queries. The proposed techniques apply to any type of similarity query and to an implementation based on an index or using a sequential scan. Parallelization yields an additional impressive speed-up. An extensive performance evaluation confirms the efficiency of our approach.

Metric databases are databases where a metric distance function is defined for pairs of database objects. In such databases, similarity queries in the form of range queries or k-nearest neighbor queries are the most important queries. In traditional query processing, single queries are issued independently by different users. In many data mining applications, however, the database is typically explored by iteratively asking similarity queries for answers of previous similarity queries. In this paper, we introduce a generic scheme for such data mining algorithms and we investigate two orthogonal approaches, reducing I/O cost as well as CPU cost, to speed-up the processing of multiple similarity queries. The proposed techniques apply to any type of similarity query and to an implementation based on an index or using a sequential scan. Parallelization yields an additional impressive speed-up. An extensive performance evaluation confirms the efficiency of our approach.

In a data warehouse, updates are typically collected and performed periodically in a batch mode, e.g., over night. This standard approach of bulk incremental updates to data warehouses has some drawbacks. First, the average runtime for a single update is small but the total runtime for the whole batch of updates may become rather large. Second, the contents of the data warehouse is not always up to date. We introduce the DC-tree, a fully dynamic index structure for data warehouses modeled as a data cube. This new index structure is designed for applications where the above drawbacks of the bulk update approach are critical. The DC-tree is a hierarchical index structure-similar to the X-tree-exploiting the concept hierarchies typically defined for the dimensions of a data cube. We conducted an extensive experimental performance evaluation using the TPC-D benchmark data. Our results demonstrate that the DC-tree yields a significant speed-up compared to the X-tree and the sequential search when processing general range queries on a data cube.

Decision trees have been successfully used for the task of classification. However, state-of-the-art algorithms do not incorporate the user in the tree construction process. This paper presents a new user-centered approach to this process where the user and the computer can both contribute their strengths: the user provides domain knowledge and evaluates intermediate results of the algorithm, the computer automatically creates patterns satisfying user constraints and generates appropriate visualizations of these patterns. In this cooperative approach, domain knowledge of the user can direct the search of the algorithm. Additionally, by providing adequate data and knowledge visualizations, the pattern recognition capabilities of the human can be used to increase the effectivity of decision tree construction. Furthermore, the user gets a deeper understanding of the decision tree than just obtaining it as a result of an algorithm. To achieve the intended level of cooperation, we introduce a new visualization of data with categorical and numerical attributes. A novel technique for visualizing decision trees is presented which provides deep insights into the process of decision tree construction. As a key contribution, we integrate a state-of-the-art algorithm for decision tree construction such that many different styles of cooperation- ranging from completely manual over combined to completely automatic classification- are supported. An experimental performance evaluation demonstrates that our cooperative approach yields an efficient construction of decision trees that have a small size, but a high accuracy. 1.

Article Free Access Share on Visual classification: an interactive approach to decision tree construction Authors: Mihael Ankerst Institute for Computer Science, University of Munich, Oettingenstr. 67, D-80538 München, Germany Institute for Computer Science, University of Munich, Oettingenstr. 67, D-80538 München, GermanyView Profile , Christian Elsen Institute for Computer Science, University of Munich, Oettingenstr. 67, D-80538 München, Germany Institute for Computer Science, University of Munich, Oettingenstr. 67, D-80538 München, GermanyView Profile , Martin Ester Institute for Computer Science, University of Munich, Oettingenstr. 67, D-80538 München, Germany Institute for Computer Science, University of Munich, Oettingenstr. 67, D-80538 München, GermanyView Profile , Hans-Peter Kriegel Institute for Computer Science, University of Munich, Oettingenstr. 67, D-80538 München, Germany Institute for Computer Science, University of Munich, Oettingenstr. 67, D-80538 München, GermanyView Profile Authors Info & Claims KDD '99: Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data miningAugust 1999 Pages 392–396https://doi.org/10.1145/312129.312298Published:01 August 1999Publication History 108citation1,861DownloadsMetricsTotal Citations108Total Downloads1,861Last 12 Months173Last 6 weeks20 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The problem of detecting clusters of points belonging to a spatial point process arises in many applications. In this paper, we introduce the new clustering algorithm DBCLASD (Distribution-Based Clustering of LArge Spatial Databases) to discover clusters of this type. The results of experiments demonstrate that DBCLASD, contrary to partitioning algorithms such as CLARANS (Clustering Large Applications based on RANdomized Search), discovers clusters of arbitrary shape. Furthermore, DBCLASD does not require any input parameters, in contrast to the clustering algorithm DBSCAN (Density-Based Spatial Clustering of Applications with Noise) requiring two input parameters, which may be difficult to provide for large databases. In terms of efficiency, DBCLASD is between CLARANS and DBSCAN, close to DBSCAN. Thus, the efficiency of DBCLASD on large spatial databases is very attractive when considering its nonparametric nature and its good quality for clusters of arbitrary shape.