32553213
Integrating rules and constraints
Constraint satisfaction problem (CSP) is a deductive problem of a special kind, while rule-based systems are the practical programs that have implemented many of the ideas and techniques of deductive systems. Incorporating CSP into a rule-based system allows the rule-based system to exploit the power of CSP techniques in handling this special class of problems. This paper shows how constraints and rules can be integrated. This integration also helps to deal with the problems of disjunctions, which are not handled satisfactorily in the current rule-based systems.<<ETX>>
6193650
Dealing with different distributions in learning from
In the problem of learning with positive and unlabeled examples, existing research all assumes that positive examples P and the hidden positive examples in the unlabeled set U are generated from the same distribution. This assumption may be violated in practice. In such cases, existing methods perform poorly. This paper proposes a novel technique A-EM to deal with the problem. Experimental results with product page classification demonstrate the effectiveness of the proposed technique.
8786674
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.
2182731
Speed-up iterative frequent itemset mining with constraint changes
Mining of frequent itemsets is a fundamental data mining task. Past research has proposed many efficient algorithms for this purpose. Recent work also highlighted the importance of using constraints to focus the mining process to mine only those relevant itemsets. In practice, data mining is often an interactive and iterative process. The user typically changes constraints and runs the mining algorithm many times before being satisfied with the final results. This interactive process is very time consuming. Existing mining algorithms are unable to take advantage of this iterative process to use previous mining results to speed up the current mining process. This results in an enormous waste of time and computation. In this paper, we propose an efficient technique to utilize previous mining results to improve the efficiency of current mining when constraints are changed. We first introduce the concept of tree boundary to summarize useful information available from previous mining. We then show that the tree boundary provides an effective and efficient framework for the new mining. The proposed technique has been implemented in the context of two existing frequent itemset mining algorithms, FP-tree and tree projection. Experiment results on both synthetic and real-life datasets show that the proposed approach achieves a dramatic saving of computation.
61155076
Opinion Mining
Описанл процедуру формування інтегрального показника об’єкта згідно з відгуками користувачів під час застосування методів оцінювання опінії текстової інформації у web-документах. Запропоновано використання лінгвістичних змінних та застосування вагових коефіцієнтів для достовірнішого результату оцінювання емоційного забарвлення текстової інформації. Ключові слова: опінія, емоційне забарвлення, об’єкт, інтегральний показник, лінгвістична змінна, ваговий коефіцієнт.
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.
18763296
A Scalable Peer-to-Peer Overlay for Applications with Time Constraints
With the development of Internet, p2p is increasingly receiving attention in research. Recently, a class of p2p applications with time constraints appear. These applications require a short time to locate the resource and(or) a low transit delay between the resource user and the resource holder, such as Skype, MSN. In this paper we propose a scalable p2p overlay for applications with time constraints. Our system provides supports for just two operations for uplayered p2p applications: (1) Given a resource key and the node's IP who holds the resource, it registers the resource information to the associated node in at most two overlay hops; and (2) Given a resource key and a time constraint(0 for no constraint), it returns if possible a path(one or two overlay hops) to the resource holder, and the transit delay of the path is lower than the time constraint. Results from theoretical analysis and simulations show that our system is viable and scalable.
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.
6366342
ECO: an empirical-based compilation and optimization system
In this paper, we describe a compilation system that automates much of the process of performance tuning that is currently done manually by application programmers interested in high performance. Due to the growing complexity of accurate performance prediction, our system incorporates empirical techniques to execute variants of code segments with representative data on the target architecture. In this paper, we discuss how empirical techniques and performance modeling can be effectively combined. We also discuss the role of historical information from prior runs, and programmer specifications supporting run-time adaptation. These techniques can be employed to alleviate some of the performance problems that lead to inefficiencies in key applications today: register pressure, cache conflict misses, and the trade-off between synchronization, parallelism and locality in SMPs.
21860578
An Effective PSO-Based Memetic Algorithm for Flow Shop Scheduling
This paper proposes an effective particle swarm optimization (PSO)-based memetic algorithm (MA) for the permutation flow shop scheduling problem (PFSSP) with the objective to minimize the maximum completion time, which is a typical non-deterministic polynomial-time (NP) hard combinatorial optimization problem. In the proposed PSO-based MA (PSOMA), both PSO-based searching operators and some special local searching operators are designed to balance the exploration and exploitation abilities. In particular, the PSOMA applies the evolutionary searching mechanism of PSO, which is characterized by individual improvement, population cooperation, and competition to effectively perform exploration. On the other hand, the PSOMA utilizes several adaptive local searches to perform exploitation. First, to make PSO suitable for solving PFSSP, a ranked-order value rule based on random key representation is presented to convert the continuous position values of particles to job permutations. Second, to generate an initial swarm with certain quality and diversity, the famous Nawaz-Enscore-Ham (NEH) heuristic is incorporated into the initialization of population. Third, to balance the exploration and exploitation abilities, after the standard PSO-based searching operation, a new local search technique named NEH_1 insertion is probabilistically applied to some good particles selected by using a roulette wheel mechanism with a specified probability. Fourth, to enrich the searching behaviors and to avoid premature convergence, a simulated annealing (SA)-based local search with multiple different neighborhoods is designed and incorporated into the PSOMA. Meanwhile, an effective adaptive meta-Lamarckian learning strategy is employed to decide which neighborhood to be used in SA-based local search. Finally, to further enhance the exploitation ability, a pairwise-based local search is applied after the SA-based search. Simulation results based on benchmarks demonstrate the effectiveness of the PSOMA. Additionally, the effects of some parameters on optimization performances are also discussed
5256099
Intrusion detection system for high-speed network
The increasing network throughput challenges the current Network Intrusion Detection Systems (NIDS) to have compatible high-performance data processing. In this paper, we describe an in-depth research on the related techniques of high-performance network intrusion detection and an implementation of a Rule-based High-performance Network Intrusion Detection System (RHPNIDS) for high-speed networks. By integrating several performance optimizing methods, the performance of RHPNIDS is very impressive compared with the popular open source NIDS Snort.