12241191
Finding Actionable Knowledge via Automated Comparison
The problem of finding interesting and actionable patterns is a major challenge in data mining. It has been studied by many data mining researchers. The issue is that data mining algorithms often generate too many patterns, which make it very hard for the user to find those truly useful ones. Over the years many techniques have been proposed. However, few have made it to real-life applications. At the end of 2005, we built a data mining system for Motorola (called Opportunity Map) to enable the user to explore the space of a large number of rules in order to find actionable knowledge. The approach is based on the concept of rule cubes and operations on rule cubes. A rule cube is similar to a data cube, but stores rules. Since its deployment, some issues have also been identified during the regular use of the system in Motorola. One of the key issues is that although the operations on rule cubes are flexible, each operation is primitive and has to be initiated by the user. Finding a piece of actionable knowledge typically involves many operations and intense visual inspections, which are labor-intensive and time-consuming. From interactions with our users, we identified a generic problem that is crucial for finding actionable knowledge. The problem involves extensive comparison of sub-populations and identification of the cause of their differences. This paper first defines the problem and then proposes an effective method to solve the problem automatically. To the best of our knowledge, there is no reported study of this problem. The new method has been added to the Opportunity Map system and is now in daily use in Motorola.
207156058
Editorial: special issue on web content mining
With the phenomenal growth of the Web, there is an everincreasing volume of data and information published in numerous Web pages. The research in Web mining aims to develop new techniques to effectively extract and mine useful knowledge or information from these Web pages [8]. Due to the heterogeneity and lack of structure of Web data, automated discovery of targeted or unexpected knowledge/information is a challenging task. It calls for novel methods that draw from a wide range of fields spanning data mining, machine learning, natural language processing, statistics, databases, and information retrieval. In the past few years, there was a rapid expansion of activities in the Web mining field, which consists of Web usage mining, Web structure mining, and Web content mining. Web usage mining refers to the discovery of user access patterns from Web usage logs. Web structure mining tries to discover useful knowledge from the structure of hyperlinks. Web content mining aims to extract/mine useful information or knowledge from Web page contents. For this special issue, we focus on Web content mining.
207576208
Clustering through decision tree construction
Clustering aims to find the intrinsic structure of data by organizing data objects into similarity groups or clusters. It is often called unsupervised learning as no class labels denoting an a priori partition of the objects are given. This is in contrast with supervised learning (e.g., classification) for which the data objects are already labeled with known classes. Past research in clustering has produced many algorithms. However, these algorithms have some major shortcomings. In this paper, we propose a novel clustering technique, which is based on a supervised learning technique called decision tree construction. The new technique is able to overcome many of these shortcomings. The key idea is to use a decision tree to partition the data space into cluster and empty (sparse) regions at different levels of details. The technique is able to find "natural" clusters in large high dimensional spaces eff iciently. It is suitable for clustering in the full dimensional space as well as in subspaces. It also provides comprehensible descriptions of clusters. Experiment results on both synthetic data and real-li fe data show that the technique is effective and also scales well for large high dimensional datasets.
10447403
Extracting Web Data Using Instance-Based Learning
This paper studies structured data extraction from Web pages, e.g., online product description pages. Existing approaches to data extraction include wrapper induction and automatic methods. In this paper, we propose an instance-based learning method, which performs extraction by comparing each new instance (or page) to be extracted with labeled instances (or pages). The key advantage of our method is that it does not need an initial set of labeled pages to learn extraction rules as in wrapper induction. Instead, the algorithm is able to start extraction from a single labeled instance (or page). Only when a new page cannot be extracted does the page need labeling. This avoids unnecessary page labeling, which solves a major problem with inductive learning (or wrapper induction), i.e., the set of labeled pages may not be representative of all other pages. The instance-based approach is very natural because structured data on the Web usually follow some fixed templates and pages of the same template usually can be extracted using a single page instance of the template. The key issue is the similarity or distance measure. Traditional measures based on the Euclidean distance or text similarity are not easily applicable in this context because items to be extracted from different pages can be entirely different. This paper proposes a novel similarity measure for the purpose, which is suitable for templated Web pages. Experimental results with product data extraction from 1200 pages in 24 diverse Web sites show that the approach is surprisingly effective. It outperforms the state-of-the-art existing systems significantly.
11669811
Multi-level organization and summarization of the discovered rules
Many existing data mining techniques often p roduce a large number of rules, which make it very difficult for manual inspection o f the rules to identify those interesting ones. This problem represents a major gap between the results of data mining and the understanding and use of the mining results. In this paper, we a rgue that t he key problem is not with the large number of rules because if there are indeed many rules that exist in data, they should b e discovered. The main p roblem is with ou r inability to organize, summarize and present the rules in such a way that they can b e ea sily analyzed b y the user. In this paper, we propose a technique to intuitively organize a nd summarize the discovered rules. With this organization, the discovered rules can b e presented to the user in the way as we think and talk about knowledge in ou r daily lives. This organization also allows the user to view the discovered rules at different levels of details, and to focus his/her attention on those interesting aspects. This paper presents this technique a nd u ses it t o o rganize, summarize a nd present t he knowledge e mbedded in a decision tree, and a set of association rules. Experiment results and p ractical applications show that the technique is both intuitive and effective.
10204389
Experimental studies of the universal chemical key (UCK) algorithm on the NCI database of chemical compounds
We have developed an algorithm called the universal chemical key (UCK) algorithm that constructs a unique key for a molecular structure. The molecular structures are represented as undirected labeled graphs with the atoms representing the vertices of the graph and the bonds representing the edges. The algorithm was tested on 236,917 compounds obtained from the National Cancer Institute (NCI) database of chemical compounds. In this paper we present the algorithm, some examples and the experimental results on the NCI database. On the NCI database, the UCK algorithm provided distinct unique keys for chemicals with different molecular structures.
32302868
Non-linear Correlation Techniques in Educational Data Mining
There is such an increasing interest in data mining and educational systems currently that has made educational data mining as a new growing research community. This paper explores how to develope new methods for discovering knowledge of data from educational context. The non-linear correlation technology was introduced and applied in the mining process in the whole knowledge achieved. Meanwhile, we have applied these methods in the real course management datasets and found correspondent results for the educators.
14885080
An Efficient and Accurate Method for 3D-Point Reconstruction from Multiple Views
In this paper we consider the problem of finding the position of a point in space given its projections in multiple images taken by cameras with known calibration and pose. Ideally the 3D point can be obtained as the intersection of multiple known rays in space. However, with noise the rays do not meet at a single point generally. Therefore, it is necessary to find a best point of intersection. In this paper we propose a modification of the method (Ma et al., 2001. Journal of Communications in Information and Systems, (1):51–73) based on the multiple-view epipolar constraints. The solution is simple in concept and straightforward to implement. It includes generally two steps: first, image points are corrected through approximating the error model to the first order, and then the 3D point can be reconstructed from the corrected image points using any generic triangulation method. Experiments are conducted both on simulated data and on real data to test the proposed method against previous methods. It is shown that results obtained with the proposed method are consistently more accurate than those of other linear methods. When the measurement error of image points is relatively small, its results are comparable to those of maximum likelihood estimation using Newton-type optimizers; and when processing image-point correspondences cross a small number of views, the proposed method is by far more efficient than the Newton-type optimizers.
42790149
Dynamic Complexities in a Lotka-volterra Predator-prey Model Concerning impulsive Control Strategy
Based on the classical Lotka–Volterra predator–prey system, an impulsive differential equation to model the process of periodically releasing natural enemies and spraying pesticides at different fixed times for pest control is proposed and investigated. It is proved that there exists a globally asymptotically stable pest-eradication periodic solution when the impulsive period is less than some critical value. Otherwise, the system can be permanent. We observe that our impulsive control strategy is more effective than the classical one if we take chemical control efficiently. Numerical results show that the system we considered has more complex dynamics including period-doubling bifurcation, symmetry-breaking bifurcation, period-halving bifurcation, quasi-periodic oscillation, chaos and nonunique dynamics, meaning that several attractors coexist. Finally, a pest–predator stage-structured model for the pest concerning this kind of impulsive control strategy is proposed, and we also show that there exists a ...
26305172
Hybrid Particle Swarm Optimization for Flow Shop Scheduling with Stochastic Processing Time
The stochastic flow shop scheduling with uncertain processing time is a typical NP-hard combinatorial optimization problem and represents an important area in production scheduling, which is difficult because of inaccurate objective estimation, huge search space, and multiple local minima. As a novel evolutionary technique, particle swarm optimization (PSO) has gained much attention and wide applications for both function and combinatorial problems, but there is no research on PSO for stochastic scheduling cases. In this paper, a class of PSO approach with simulated annealing (SA) and hypothesis test (HT), namely PSOSAHT is proposed for stochastic flow shop scheduling with uncertain processing time with respect to the makespan criterion (i.e. minimizing the maximum completion time). Simulation results demonstrate the feasibility, effectiveness and robustness of the proposed hybrid algorithm. Meanwhile, the effects of noise magnitude and number of evaluation on searching performances are also investigated.
8396998
Consensus in Networks of Multiagents With Cooperation and Competition Via Stochastically Switching Topologies
In this brief, we provide some theoretical analysis of the consensus for networks of agents via stochastically switching topologies. We consider both discrete-time case and continuous-time case. The main contribution of this brief is that the underlying graph topology is more general in both cases than those appeared in previous papers. The weight matrix of the coupling graph is not assumed to be nonnegative or Metzler. That is, in the model discussed here, the off-diagonal entries of the weight matrix of the coupling graph may be negative. This means that sometimes, the coupling may not benefit, but may prevent the consensus of the coupled agents. In the continuous-time case, the switching time intervals also take a more general form of random variables than those appeared in previous works. We focus our study on such networks and give sufficient conditions that ensure almost sure consensus in both discrete-time case and continuous-time case. As applications, we give several corollaries under more specific assumptions, i.e., the switching can be some independent and identically distributed (i.i.d.) random variable series or a Markov chain. Numerical examples are also provided in both discrete-time and continuous-time cases to demonstrate the validity of our theoretical results.