29560725
Guest Editors' Introduction: Special Section on Mining and Searching the Web
WITH the phenomenal growth of the Web, there is an ever-increasing volume of information being published on numerous Web sites. This vast amount of accessible information has raised many new opportunities and challenges for knowledge discovery and data engineering researchers. For programs that seek to analyze Web content, the heterogeneity in authorship and the consequent lack of structure are formidable hurdles. Discovering and extracting novel and useful knowledge from Web sources call for innovative approaches that draw from a wide range of fields spanning data mining, machine learning, statistics, databases, information retrieval, artificial intelligence, and natural language processing. In Web search, although general-purpose search engines are very useful, finding specific or targeted information can still be a frustrating experience. Highly effective, domainspecific, and personalized search techniques are not yet mainstream. In e-commerce, a whole range of online techniques are also needed to support such applications. For example, in online shopping, there are no human shop assistants to help customers. Instead, automated techniques are needed to learn from the behaviors of users in order to provide effective recommendations and assistance. Mining, extracting, and integrating Web information are challenging problems as well because there is still no mature technique to integrate information from structured (stored database), ad hoc structured (shopping sites), and unstructured (product reviews) sources. Clearly, format standards for semistructured data will not solve all of these problems. This special issue of IEEE Transactions on Knowledge and Data Engineering brings together some of the latest research results in the field. It presents seven papers which deal with a wide range of problems. All of the accepted papers propose some novel and/or principled techniques to solve these problems. Of the seven papers, three focus on domain specific and personalized Web search, one proposes a principled technique for collaborative filtering, one studies Web page cleaning for identifying informative structures and content blocks in Web pages, one studies classification of Web pages based on positive and unlabeled training examples, and one studies the clustering of XML data for efficient storage and querying of such data. The first paper by Michelangelo Diligenti, Marco Gori, and Marco Maggini studies Web page scoring for Web search and resource discovery. Current methods for the purpose are mainly based on the analysis of hyperlinks. The structure of the hyperlinks is the result of collaborative activities of the community of Web authors. Web authors usually like to link resources they consider authoritative, and authority emerges from the dynamics of popularity of the resources on the Web. This paper proposes a general probabilistic framework based on random walk of links for Web page scoring that incorporates and extends many existing models. Their results show that the proposed framework is effective and is particularly suited for focused or vertical search. The second paper by Satoshi Oyama, Takashi Kokubo, and Toru Ishida describes an interesting technique for domain specific Web search. The basic idea is to find a set of domain specific keywords (which the authors call keyword spices) that can be used as the context of the search queries in the domain. A nice algorithm based on text classification is given for identifying a reasonably complete set of such keyword spices. To perform text classification, it collects training pages from the Web through a search using an initial set of keywords of the domain. The main advantage of the proposed method is that it does not need to collect and index domain specific pages as most domain specific search engines do. The work is also related to research in query expansion and modification, but deals with a slightly different problem and offers different approaches. The third paper by Fang Liu, Clement Yu, and Weiyi Meng also studies Web search, more specifically, personalized Web search. Since general-purpose search engines do not consider user’s interests, their search results may not be interesting to a specific user. Personalized search aims at carrying out search for each user incorporating his/her interests. In this paper, the authors propose to employ a user profile and a general profile to constrain the search. The user profile is learned from the user’s search history, which contains the user interested categories and weighted terms in the categories. The general profile is built using the categories from the Open Directory Project. The key advance of the technique is that it maps each user query to some categories. At the search time, the system first uses the profiles to infer the categories of the search terms in question. Then, the search terms are augmented with each category as the context to perform search. The search results are then merged to produce a single result ranking. A comprehensive experimental evaluation is described in the paper. The fourth paper by Hung-Yu Kao, Shian-Hua Liu, JanMing Ho, and Ming-Syan Chen focuses on the cleaning of 2 IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL. 16, NO. 1, JANUARY 2004
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.
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.
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.
61155076
Opinion Mining
Описанл процедуру формування інтегрального показника об’єкта згідно з відгуками користувачів під час застосування методів оцінювання опінії текстової інформації у web-документах. Запропоновано використання лінгвістичних змінних та застосування вагових коефіцієнтів для достовірнішого результату оцінювання емоційного забарвлення текстової інформації. Ключові слова: опінія, емоційне забарвлення, об’єкт, інтегральний показник, лінгвістична змінна, ваговий коефіцієнт.
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.
410427
Database and location management schemes for mobile communications
Signaling traffic incurred in tracking mobile users and delivering enhanced services causes an additional load in the network. Efficient database and location management schemes are needed to meet the challenges from high density and mobility of users, and various service features. In this paper, the general location control and management function is treated as the combination of two parts, the global and local scope. New schemes and methods are proposed, and improvements achieved over established basic schemes are shown by using simulations.
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.
10223976
A combinational feature selection and ensemble neural network method for classification of gene expression data
BackgroundMicroarray experiments are becoming a powerful tool for clinical diagnosis, as they have the potential to discover gene expression patterns that are characteristic for a particular disease. To date, this problem has received most attention in the context of cancer research, especially in tumor classification. Various feature selection methods and classifier design strategies also have been generally used and compared. However, most published articles on tumor classification have applied a certain technique to a certain dataset, and recently several researchers compared these techniques based on several public datasets. But, it has been verified that differently selected features reflect different aspects of the dataset and some selected features can obtain better solutions on some certain problems. At the same time, faced with a large amount of microarray data with little knowledge, it is difficult to find the intrinsic characteristics using traditional methods. In this paper, we attempt to introduce a combinational feature selection method in conjunction with ensemble neural networks to generally improve the accuracy and robustness of sample classification.ResultsWe validate our new method on several recent publicly available datasets both with predictive accuracy of testing samples and through cross validation. Compared with the best performance of other current methods, remarkably improved results can be obtained using our new strategy on a wide range of different datasets.ConclusionsThus, we conclude that our methods can obtain more information in microarray data to get more accurate classification and also can help to extract the latent marker genes of the diseases for better diagnosis and treatment.
8632899
Accessible image search
There are about 8% of men and 0.8% of women suffering from colorblindness. We show that the existing image search techniques cannot provide satisfactory results for these users, since many images will not be well perceived by them due to the loss of color information. In this paper, we introduce a scheme named Accessible Image Search (AIS) to accommodate these users. Different from the general image search scheme that aims at returning more relevant results, AIS further takes into account the colorblind accessibilities of the returned results, i.e., the image qualities in the eyes of colorblind users. The scheme includes two components: accessibility assessment and accessibility improvement. For accessibility assessment, we introduce an analysisbased method and a learning-based method. Based on the measured accessibility scores, different reranking methods can be performed to prioritize the images with high accessibilities. In accessibility improvement component, we propose an efficient recoloring algorithm to modify the colors of the images such that they can be better perceived by colorblind users. We also propose the Accessibility Average Precision (AAP) for AIS as a complementary performance evaluation measure to the conventional relevance-based evaluation methods. Experimental results with more than 60,000 images and 20 anonymous colorblind users demonstrate the effectiveness and usefulness of the proposed scheme.
17229395
Region-of-interest coding of 3D mesh based on wavelet transform
A scheme for the region of interest (ROI) coding of 3D meshes is proposed for the first time. The ROI is encoded with higher fidelity than the rest region, and the "priority" of ROI relative to the rest region (background, BG) can be specified by encoder or decoder (user). Wavelet transform is used on 3D mesh and zerotrees are adopted to organize the coefficients. The wavelet coefficients of ROI are scaled up and encoded with a modified set partitioning in hierarchical trees (SPIHT) algorithm. In additional, a fast algorithm is proposed for creating the ROI mask. Once the quality of reconstructed ROI becomes high enough, the transmission can be intermitted and much transmission bandwidth and storage space will be saved consequently.