Entity Mining Extraction Using Sequential Rules
A comparative sentence expresses an ordering relation between two sets of entities with respect to some common features. For example, the comparative sentence "Canon's optics are better than those of Sony and Nikon" expresses the comparative relation Comparing one thing with another is a typical part of human decision making process. However, it is not always easy to know what to compare and what are the alternatives. To address this difficulty, we present a new way for automatically extracting comparable entities from comparative questions based on the pattern. We propose new techniques based on these two types of sequential rules to perform the tasks. Introduction Comparing alternative options is one of the essential things in decision making that we carry out every day. Example, if someone is interested in certain products such as digital cameras, he or she would want to know what the different alternatives we have and compare different cameras before making a purchase. This type of comparison activity is very common in our daily life but requires high knowledge skill. And Magazines such as Consumer Reports and PC Magazine and online media such as CNet.com strive in providing editorial comparison content and surveys to satisfy this need. In World Wide Web, a comparison activity typically involves: search for relevant web pages containing information about the targeted products, find competing products, read reviews, and identify pros and cons. In this paper, we focus on finding a set of comparable entities given a users input entity. For example, given an entity, Nokia N95 (a cellphone) we want to find comparable entities such as Nokia N82, iPhone and so on. In general, it is difficult to decide if two entities are comparable or not since people do compare apples and oranges for various reasons. For example, "Ford" and "BMW" might be comparable as "car manufacturers" or as "market segments that their products are targeting" but we rarely see people comparing "Ford Focus" (car model) and "BMW 328i" Things also get more complicated when an entity has several functionalities. For example, one might compare "iPhone" and "PSP" as "portable game player" while compare "iPhone" and "Nokia N95" as "mobile phone" Fortunately, plenty of comparative questions are posted online, which provide evidences for what people want to compare, e.g. "Which to buy, iPod or iPhone?" We call "iPod" and "iPhone" in this example as comparators. In this paper, we define comparative questions and comparators as: Comparative question: A question that intends to compare two or more entities and it has to mention these entities explicitly in the question. Comparator: An entity which is a target of comparison in a comparative question. Comparisons can be subjective or objective. For example, a typical opinion sentence is "The picture quality of camera x is great" A subjective comparison is "the picture quality of camera x is better than that of camera y." An objective comparison is "car x is 2 feet longer than car y" We can see that comparative sentences use different language constructs from typical opinion sentences (although the first comparative sentence above is also an opinion) In this paper, we study the problem of comparative sentence mining. It has two tasks: 1. Given a set of evaluative texts, identify comparative sentences from them, and classify the identified comparative sentences into different types (or classes) 2. Extract comparative relations from the identified sentences. This involves the extraction of entities and their features that are being compared, and comparative keywords. The relation is expressed with <relationWord> <features> <entityS1> <entityS2> Proceedings of The Intl. Conf. on Information, Engineering, Management and Security 2014 [ICIEMS 2014] 225 ICIEMS 2014 ISBN 978 81 925233 3 0 www.edlib.asdf.res.in www.iciems.in D ow lo ad ed fro m w w w .e dl ib .a sd f.r es .in For example, we have the comparative sentence "Canon's optics is better than those of Sony and Nikon." The extracted relation is: (better, {optics} {Canon} {Sony, Nikon} Both tasks are very challenging. Although we see that the above sentences all contain some indicators i.e. "better" "longer" many sentences that contain such words are not comparatives, e.g. "I cannot agree with you more" The second step is a difficult information extraction problem. For the first task, we present an approach that integrates class sequential rules (CSR) and naive Bayesian classification to perform the task. This task is studied in detail in (Jindal Liu 2006) We include it for completeness. For the second task, a new type of rules called label sequential rules (LSR) is proposed for extraction. Our results show that LSRs outperform Conditional Random Fields (CRF) (Lafferty, McCallum Pereira 2001) which is perhaps the most effective extraction method so far (Mooney Bunescu 2005) Types of Sequential Rules We now start to present the proposed techniques, which are based on two types of sequential rules. Mining of such rules is related to mining of sequential patterns (SPM) (Agrawal and Srikant 1994) Given a set of input sequences, SPM finds all subsequences (called sequential patterns) that satisfy a user specified minimum support threshold. Below, we first explain some notations, and then define the two new types of rules, Class sequential rules (CSR) used in classification of sentences, and label sequential rules (LSR) used in relation item extraction. For more details about these types of rules and their mining algorithms, please see (Liu 2006) Let I {i1, i2, in} be a set of items. A sequence is an ordered list of itemsets. An itemset X is a non empty set of items. We denote a sequence s by (a1a2..ar) where ai is an itemset, also called an element of s. We denote an element of a sequence by {x1, x2, xk} where xj is an item. An item can occur only once in an element of a sequence, but can occur multiple times in different elements. A sequence s1 (a1a2..ar) is a subsequence of another sequence s2 (b1b2..bm) or s2 is a supersequence of s1, if there exist integers 1 j1 j2 jr 1 jr such that a1 bj1 a2 bj2, ar bjr. We also say that s2 contains s1. Class Sequential Rules Let S be a set of data sequences. Each sequence is labeled with a class y. Let Y be the set of all classes, I Y O. Thus, the input data D for mining is represented with D (s1, y1) (s2, y2) (sn, yn) where si is a sequence and yi Y is its class. A class sequential rule (CSR) is an implication of the form X y, where X is a sequence, and y Y. A data instance (si, yi) in D is said to cover the CSR if X is a subsequence of si. A data instance (si, yi) is said to satisfy a CSR if X is a subsequence of si and yi y. The support (sup) of the rule is the fraction of total instances in D that satisfies the rule. The confidence (conf) of the rule is the proportion of instances in D that covers the rule also satisfies the rule. Given a labeled sequence data set D, a minimum support (minsup) and a minimum confidence (minconf) threshold, CSR mining finds all class sequential rules in D. Label Sequential Rules A label sequential rule (LSR) is of the following form,