waashk/dblp huggingface dataset:
improving data mining utility with projective sampling. overall performance of the data mining process depends not just on the value of the induced knowledge but also on various costs of the process itself such as the cost of acquiring and pre-processing training examples, the cpu cost of model induction, and the cost of committed errors. recently, several progressive sampling strategies for maximizing the overall data mining utility have been proposed. all these strategies are based on repeated acquisitions of additional training examples until a utility decrease is observed. in this paper, we present an alternative, projective sampling strategy, which fits functions to a partial learning curve and a partial run-time curve obtained from a small subset of potentially available data and then uses these projected functions to analytically estimate the optimal training set size. the proposed approach is evaluated on a variety of benchmark datasets using the rapidminer environment for machine learning and data mining processes. the results show that the learning and run-time curves projected from only several data points can lead to a cheaper data mining process than the common progressive sampling methods.
entity discovery and assignment for opinion mining applications. opinion mining became an important topic of study in recent years due to its wide range of applications. there are also many companies offering opinion mining services. one problem that has not been studied so far is the assignment of entities that have been talked about in each sentence. let us use forum discussions about products as an example to make the problem concrete. in a typical discussion post, the author may give opinions on multiple products and also compare them. the issue is how to detect what products have been talked about in each sentence. if the sentence contains the product names, they need to be identified. we call this problem entity discovery. if the product names are not explicitly mentioned in the sentence but are implied due to the use of pronouns and language conventions, we need to infer the products. we call this problem entity assignment. these problems are important because without knowing what products each sentence talks about the opinion mined from the sentence is of little use. in this paper, we study these problems and propose two effective methods to solve the problems. entity discovery is based on pattern discovery and entity assignment is based on mining of comparative sentences. experimental results using a large number of forum posts demonstrate the effectiveness of the technique. our system has also been successfully tested in a commercial setting.
applying syntactic similarity algorithms for enterprise information management. for implementing content management solutions and enabling new applications associated with data retention, regulatory compliance, and litigation issues, enterprises need to develop advanced analytics to uncover relationships among the documents, e.g., content similarity, provenance, and clustering. in this paper, we evaluate the performance of four syntactic similarity algorithms. three algorithms are based on broder's "shingling" technique while the fourth algorithm employs a more recent approach, "content-based chunking". for our experiments, we use a specially designed corpus of documents that includes a set of "similar" documents with a controlled number of modifications. our performance study reveals that the similarity metric of all four algorithms is highly sensitive to settings of the algorithms' parameters: sliding window size and fingerprint sampling frequency. we identify a useful range of these parameters for achieving good practical results, and compare the performance of the four algorithms in a controlled environment. we validate our results by applying these algorithms to finding near-duplicates in two large collections of hp technical support documents.
query result clustering for object-level search. query result clustering has recently attracted a lot of attention to provide users with a succinct overview of relevant results. however, little work has been done on organizing the query results for object-level search. object-level search result clustering is challenging because we need to support diverse similarity notions over object-specific features (such as the price and weight of a product) of heterogeneous domains. to address this challenge, we propose a hybrid subspace clustering algorithm called hydra. algorithm hydra captures the user perception of diverse similarity notions from millions of web pages and disambiguates different senses using feature-based subspace locality measures. our proposed solution, by combining wisdom of crowds and wisdom of data, achieves robustness and efficiency over existing approaches. we extensively evaluate our proposed framework and demonstrate how to enrich user experiences in object-level search using a real-world product search scenarios.
scalable graph clustering using stochastic flows: applications to community discovery. algorithms based on simulating stochastic flows are a simple and natural solution for the problem of clustering graphs, but their widespread use has been hampered by their lack of scalability and fragmentation of output. in this article we present a multi-level algorithm for graph clustering using flows that delivers significant improvements in both quality and speed. the graph is first successively coarsened to a manageable size, and a small number of iterations of flow simulation is performed on the coarse graph. the graph is then successively refined, with flows from the previous graph used as initializations for brief flow simulations on each of the intermediate graphs. when we reach the final refined graph, the algorithm is run to convergence and the high-flow regions are clustered together, with regions without any flow forming the natural boundaries of the clusters. extensive experimental results on several real and synthetic datasets demonstrate the effectiveness of our approach when compared to state-of-the-art algorithms.
network science: an introduction to recent statistical approaches. network science focuses on relationships between social entities. it is used widely in the social and behavioral sciences, as well as in political science, economics, organizational science, and industrial engineering. the social network perspective has been developed over the last sixty years by researchers in psychology, sociology, and anthropology, and morerecently, to a lesser extent, in physics. network science is gaining recognition and standing in the general social and behavioral science communities as the theoretical basis for examining social structures. this basis has been clearly defined by many theorists, and the paradigm convincingly applied to important substantive problems. however, the paradigm requires a new and different set of concepts and analytic tools, beyond those provided by standard quantitative (particularly, statistical) methods. these concepts and tools are the topics of this talk.
heterogeneous source consensus learning via decision propagation and negotiation. nowadays, enormous amounts of data are continuously generated not only in massive scale, but also from different, sometimes conflicting, views. therefore, it is important to consolidate different concepts for intelligent decision making. for example, to predict the research areas of some people, the best results are usually achieved by combining and consolidating predictions obtained from the publication network, co-authorship network and the textual content of their publications. multiple supervised and unsupervised hypotheses can be drawn from these information sources, and negotiating their differences and consolidating decisions usually yields a much more accurate model due to the diversity and heterogeneity of these models. in this paper, we address the problem of "consensus learning" among competing hypotheses, which either rely on outside knowledge (supervised learning) or internal structure (unsupervised clustering). we argue that consensus learning is an np-hard problem and thus propose to solve it by an efficient heuristic method. we construct a belief graph to first propagate predictions from supervised models to the unsupervised, and then negotiate and reach consensus among them. their final decision is further consolidated by calculating each model's weight based on its degree of consistency with other models. experiments are conducted on 20 newsgroups data, cora research papers, dblp author-conference network, and yahoo! movies datasets, and the results show that the proposed method improves the classification accuracy and the clustering quality measure (nmi) over the best base model by up to 10%. furthermore, it runs in time proportional to the number of instances, which is very efficient for large scale data sets.
seven pitfalls to avoid when running controlled experiments on the web. controlled experiments, also called randomized experiments and a/b tests, have had a profound influence on multiple fields, including medicine, agriculture, manufacturing, and advertising. while the theoretical aspects of offline controlled experiments have been well studied and documented, the practical aspects of running them in online settings, such as web sites and services, are still being developed. as the usage of controlled experiments grows in these online settings, it is becoming more important to understand the opportunities and pitfalls one might face when using them in practice. a survey of online controlled experiments and lessons learned were previously documented in controlled experiments on the web: survey and practical guide (kohavi, et al., 2009). in this follow-on paper, we focus on pitfalls we have seen after running numerous experiments at microsoft. the pitfalls include a wide range of topics, such as assuming that common statistical formulas used to calculate standard deviation and statistical power can be applied and ignoring robots in analysis (a problem unique to online settings). online experiments allow for techniques like gradual ramp-up of treatments to avoid the possibility of exposing many customers to a bad (e.g., buggy) treatment. with that ability, we discovered that it's easy to incorrectly identify the winning treatment because of simpson's paradox.
pskip: estimating relevance ranking quality from web search clickthrough data. in this article, we report our efforts in mining the information encoded as clickthrough data in the server logs to evaluate and monitor the relevance ranking quality of a commercial web search engine. we describe a metric called pskip that aims to quantify the ranking quality by estimating the probability of users encountering non relevant results that cost them the efforts to read and skip. a search engine with a lower pskip is regarded as having a better ranking quality. a key design goal of pskip is to integrate the findings from two sets of user studies that utilize eye-tracking devices to track users' browsing patterns on the search result pages, and that use specially instrumented browsers to actively solicit users' explicit judgments on their search activities. we present the derivation of the maximum likelihood estimation of pskip and demonstrate its efficacy in describing the user study data. the mathematical properties of pskip are further analyzed and compared with several objective metrics as well as the cumulated gain method that uses subjective judgments. experimental data show that pskip can measure aspects of the search quality that these existing metrics are not designed or fail to address, such as identifying the real search intents expressed in the ambiguous queries. although effective and superior in many ways, we also report a series of experiments that show pskip may be influenced by system issues that are not directly related to relevance ranking, suggesting that measurements complementary to pskip are still needed in order to form a holistic and accurate characterization of the ranking quality.
collusion-resistant anonymous data collection method. the availability and the accuracy of the data dictate the success of a data mining application. increasingly, there is a need to resort to on-line data collection to address the problem of data availability. however, participants in on-line data collection applications are naturally distrustful of the data collector as well as their peer respondents, resulting in inaccurate data collected as the respondents refuse to provide truthful data in fear of collusion attacks. the current anonymity-preserving solutions for on-line data collection are unable to adequately resist such attacks in a scalable fashion. in this paper, we present an efficient anonymous data collection protocol for a malicious environment such as the internet. the protocol employs cryptographic and random shuffling techniques to preserve participants' anonymity. the proposed method is collusion-resistant and guarantees that an attacker will be unable to breach an honest participant's anonymity unless she controls all n-1 participants. in addition, our method is efficient and achieved 15-42% communication overhead reduction in comparison to the prior state-of-the-art methods.
a viewpoint-based approach for interaction graph analysis. recent innovations have resulted in a plethora of social applications on the web, such as blogs, social networks, and community photo and video sharing applications. such applications can typically be represented as evolving interaction graphs with nodes denoting entities and edges representing their interactions. the study of entities and communities and how they evolve in such large dynamic graphs is both important and challenging. while much of the past work in this area has focused on static analysis, more recently researchers have investigated dynamic analysis. in this paper, in a departure from recent efforts, we consider the problem of analyzing patterns and critical events that affect the dynamic graph from the viewpoint of a single node, or a selected subset of nodes. defining and extracting a relevant viewpoint neighborhood efficiently, while also quantifying the key relationships among nodes involved are the key challenges we address. we also examine the evolution of viewpoint neighborhoods for different entities over time to identify key structural and behavioral transformations that occur.
enabling analysts in managed services for crm analytics. data analytics tools and frameworks abound, yet rapid deployment of analytics solutions that deliver actionable insights from business data remains a challenge. the primary reason is that on-field practitioners are required to be both technically proficient and knowledgeable about the business. the recent abundance of unstructured business data has thrown up new opportunities for analytics, but has also multiplied the deployment challenge, since interpretation of concepts derived from textual sources require a deep understanding of the business. in such a scenario, a managed service for analytics comes up as the best alternative. a managed analytics service is centered around a business analyst who acts as a liaison between the business and the technology. this calls for new tools that assist the analyst to be efficient in the tasks that she needs to execute. also, the analytics needs to be repeatable, in that the delivered insights should not depend heavily on the expertise of specific analysts. these factors lead us to identify new areas that open up for kdd research in terms of 'time-to-insight' and repeatability for these analysts. we present our analytics framework in the form of a managed service offering for crm analytics. we describe different analyst-centric tools using a case study from real-life engagements and demonstrate their effectiveness.
finding a team of experts in social networks. given a task t, a pool of individuals x with different skills, and a social network g that captures the compatibility among these individuals, we study the problem of finding x, a subset of x, to perform the task. we call this the team formation problem. we require that members of x' not only meet the skill requirements of the task, but can also work effectively together as a team. we measure effectiveness using the communication cost incurred by the subgraph in g that only involves x'. we study two variants of the problem for two different communication-cost functions, and show that both variants are np-hard. we explore their connections with existing combinatorial problems and give novel algorithms for their solution. to the best of our knowledge, this is the first work to consider the team formation problem in the presence of a social network of individuals. experiments on the dblp dataset show that our framework works well in practice and gives useful and intuitive results.
parallel community detection on large networks with propinquity dynamics. graphs or networks can be used to model complex systems. detecting community structures from large network data is a classic and challenging task. in this paper, we propose a novel community detection algorithm, which utilizes a dynamic process by contradicting the network topology and the topology-based propinquity, where the propinquity is a measure of the probability for a pair of nodes involved in a coherent community structure. through several rounds of mutual reinforcement between topology and propinquity, the community structures are expected to naturally emerge. the overlapping vertices shared between communities can also be easily identified by an additional simple postprocessing. to achieve better efficiency, the propinquity is incrementally calculated. we implement the algorithm on a vertex-oriented bulk synchronous parallel(bsp) model so that the mining load can be distributed on thousands of machines. we obtained interesting experimental results on several real network data.
the offset tree for learning with partial labels. we present an algorithm, called the offset tree, for learning to make decisions in situations where the payoff of only one choice is observed, rather than all choices. the algorithm reduces this setting to binary classification, allowing one to reuse any existing, fully supervised binary classification algorithm in this partial information setting. we show that the offset tree is an optimal reduction to binary classification. in particular, it has regret at most (k-1) times the regret of the binary classifier it uses (where k is the number of choices), and no reduction to binary classification can do better. this reduction is also computationally optimal, both at training and test time, requiring just o(log2 k) work to train on an example or make a prediction. experiments with the offset tree show that it generally performs better than several alternative approaches.
mind the gaps: weighting the unknown in large-scale one-class collaborative filtering. one-class collaborative filtering (occf) is a task that naturally emerges in recommender system settings. typical characteristics include: only positive examples can be observed, classes are highly imbalanced, and the vast majority of data points are missing. the idea of introducing weights for missing parts of a matrix has recently been shown to help in occf. while existing weighting approaches mitigate the first two problems above, a sparsity preserving solution that would allow to efficiently utilize data sets with e.g., hundred thousands of users and items has not yet been reported. in this paper, we study three different collaborative filtering frameworks: low-rank matrix approximation, probabilistic latent semantic analysis, and maximum-margin matrix factorization. we propose two novel algorithms for large-scale occf that allow to weight the unknowns. our experimental results demonstrate their effectiveness and efficiency on different problems, including the netflix prize data.
coa: finding novel patents through text analysis. in recent years, the number of patents filed by the business enterprises in the technology industry are growing rapidly, thus providing unprecedented opportunities for knowledge discovery in patent data. one important task in this regard is to employ data mining techniques to rank patents in terms of their potential to earn money through licensing. availability of such ranking can substantially reduce enterprise ip (intellectual property) management costs. unfortunately, the existing software systems in the ip domain do not address this task directly. through our research, we build a patent ranking software, named coa (claim originality analysis) that rates a patent based on its value by measuring the recency and the impact of the important phrases that appear in the "claims" section of a patent. experiments show that coa produces meaningful ranking when comparing it with other indirect patent evaluation metrics--citation count, patent status, and attorney's rating. in reallife settings, this tool was used by beta-testers in the ibm ip department. lawyers found it very useful in patent rating, specifically, in highlighting potentially valuable patents in a patent cluster. in this article, we describe the ranking techniques and system architecture of coa. we also present the results that validate its effectiveness.
causality quantification and its applications: structuring and modeling of multivariate time series. time series prediction is an important issue in a wide range of areas. there are various real world processes whose states vary continuously, and those processes may have influences on each other. if the past information of one process x improves the predictability of another process y, x is said to have a causal influence on y. in order to make good predictions, it is necessary to identify the appropriate causal relationships. in addition, the processes to be modeled may include symbolic data as well as numerical data. therefore, it is important to deal with symbolic and numerical time series seamlessly when attempting to detect causality. in this paper, we propose a new method for quantifying the strength of the causal influence from one time series to another. the proposed method can represent the strength of causality as the number of bits, whether each of two time series is symbolic or numerical. the proposed method can quantify causality even from a small number of samples. in addition, we propose structuring and modeling methods for multivariate time series using causal relationships of two time series. our structuring and modeling methods can also deal with data sets which include both types of time series. experimental results demonstrate that our methods can perform well even if the number of samples is small.