Social Media Mining: An Introduction

P1: Sqe Trim: 6.125in×9.25in Top: 0.5in Gutter: 0.75in
CUUS2079-05 CUUS2079-Zafarani 978 1 107 01885 3 January 13, 2014 19:23

116 Data Mining Essentials

Decision trees classify examples based on their feature values. Each non-

leaf node in a decision tree represents a feature, and each branch represents

a value that the feature can take. Instances are classified by following a path

that starts at the root node and ends at a leaf by following branches based on

instance feature values. The value of the leaf determines the class attribute

value predicted for the instance (see Figure5.3).

Decision trees are constructed recursively from training data using a

top-down greedy approach in which features are sequentially selected. In

Figure5.3(a), the feature selected for the root node isCelebrity. After

selecting a feature for each node, based on its values, different branches

are created: For Figure5.3(a), since theCelebrityfeature can only take

eitherYesorNo, two branches are created: one labeledYesand one labeled

No. The training set is then partitioned into subsets based on the feature

values, each of which fall under the respective feature value branch; the

process is continued for these subsets and other nodes. In Figure5.3(a),

instances 1, 4, and 9 from Table5.1represent the subset that falls under the

Celebrity=Yesbranch, and the other instances represent the subset that

falls under theCelebrity=Nobranch.

When selecting features, we prefer features that partition the set of

instances into subsets that are morepure. A pure subset has instances

that all have the same class attribute value. In Figure5.3(a), the instances

that fall under the left branch of the root node (Celebrity=Yes)form

a pure subset in which all instances have the same class attribute value

Influential?=No. When reaching pure subsets under a branch, the deci-

sion tree construction process no longer partitions the subset, creates a leaf

under the branch, and assigns the class attribute value for subset instances

as the leaf’s predicted class attribute value. In Figure5.3(a), the instances

that fall under the right branch of the root node form an impure dataset;

therefore, further branching is required to reach pure subsets. Purity of

subsets can be determined with different measures. A common measure of

purity isentropy. Over a subset of training instances,T, with a binary class

attribute (values∈{+,−}), the entropy ofTis defined as

entropy(T)=−p+logp+−p−logp−, (5.15)

wherep+is the proportion of instances with+class attribute value inT

andp−is the proportion of instances with – class attribute value.

Example 5.3.Assume that there is a subset T , containing 10 instances.

Seven instances have a positive class attribute value, and three instances