Solution Manual for Data Mining Chapter 12

Chapter 12 Outlier Detection 12.1 Exercises 1. Give an application example where global outliers, contextual outliers and collective outliers are all interesting. What are the attributes, and what are the contextual and behavioral attributes? How is the relationship among objects modeled in collective outlier detection? Answer: A credit card company often maintains a profile for each customer. Suppose a profile has the following attributes: name, age, job, address, annual-income, annual-expense, average-balance, credit-limit. Global outliers, contextual outliers, and collective outliers are all interesting. • A global outlier is interesting, since it may be a customer who are very different from the majority of customers of the company. The significant difference may call for special service or monitoring by the company. • Consider annual-income and annual-expense as the contextual attributes, and average-balance as the behavior attribute. A contextual outlier is interesting, since its usage of the credit card is dramatically different from the other customers in the same group. Such an outlier customer, for example, may either spend much less or much more than the others in the same contextual group. If the outlier customer spends much less, than the company can try to promote services to the customer. On the other hand, if the customer spends much more, than the company can either introduce special service to encourage even more spending, or apply special monitoring to prevent from frauds or bad credit behaviors, depending on the nature of the spending. Please note that a contextual outlier’s average balance may still within the normal range for all customers, and thus is not a global outlier. • Suppose the credit card company finds a group of customers from a geographically proximate area (through the attribute address) have very low annual-income but very high annual-expense, which is substantially different from the other customers. This forms a group of collective outliers. This is interesting to the company, since this group of customers may need to be monitored closely and their credit limits may need to be controlled firmly. 2. Give an application example of where the border between “normal objects” and outliers is often unclear, so that the degree to which an object is an outlier has to be well estimated. Answer: A credit card company has to monitor credit card transactions. However, the border between “normal transactions” and outliers, such as frauds, is often unclear, because the distinction between the two often depends on many other factors not included in the transactions themselves. Therefore, a good fraud detection system in a credit card company, which is essentially an outlier detection system, has to estimate the degree to which a transaction is an outlier. 3. Adapt a simple semi-supervised method for outlier detection. Discuss the scenario where you have i) only some labeled examples of “normal objects”, and ii) only some labeled examples of outliers. Answer: When only some labeled examples are available, we can take use those examples to learn a model for the normal objects. For example, we may use a density-based approach to find dense areas that contain at least one normal objects. The objects falling into those areas can be regarded as normal. The objects that are far away from any normal objects are candidates of outliers. When only some labeled examples of outliers are available, we may use those examples to extract the features that can distinguish outliers. That is, we may extract a minimal set of features such that, according to those features, the labeled outlier examples are far away from most of the unlabeled objects, and most of the unlabeled objects form clusters. Then, those unlabeled objects falling into clusters can be regarded as normal, and the objects far away from those clusters are candidates of outliers. 4. Using an equi-depth histogram, design a way to assign an object an outlier score. Answer: We observe that in an equi-depth histogram, a narrower bucket contains points that are more similar to each other than a wider bucket. Based on this observation, a possible way to assign an object an outlier score is as follows. For each bucket Bi , denote by li the width of the bucket. Then, for an object falling into the bucket Bi , we assign the outlier score li . The larger the outlier score, the more likely the object is an outlier. 5. Consider the nested loop approach to mining distance-based outliers (Figure ??). Suppose the objects in a data set are arranged randomly, that is, each object has the same probability to appear in a position. Show that when the number of outlier objects is small with respect to the total number of objects in the whole data set, the expected number of distance calculations is linear to the number of objects. Answer: Please refer to [BS03]. 6. In the density-based outlier detection method of Section ??, the definition of local reachability density has a potential problem: lrdk (o) = ∞ may occur. Explain why this may occur and propose a fix to the issue. Answer: For an object o, if there are another k objects located at the same position, then lrdk (o) = ∞. To fix this problem, we can use a parameter ϵ > 0 and set dist(o, o′ ) = max{d(o, o′ ), ϵ}, where d(o, o′ ) gives the distance between o and o′ . o Figure 12.1: Outlier o cannot be detected by the angle-based method. 7. Because clusters may form a hierarchy, outliers may belong to different levels of granularity. Propose a clustering-based outlier detection method that can find outliers at different levels. Answer: A possible method is to use probabilistic hierarchical clustering to learn a hierarchy of clusters. At each cluster in the hierarchy, we can calculate the probability of each sub-cluster and use this probability as the outlier score – the lower the probability, the more likely it is an outlier. As another example, we may use density-based clustering method. At the global level, we can use a large radius or a small neighborhood density threshold to form clusters. At a lower level, we can use a smaller radius or a larger neighborhood density threshold to find subclusters within a higher level cluster. Once a hierarchy of clusters is formed, we can then apply the density-based outlier detection method to find outliers within each cluster. The parameters should be set properly according to the parameter values used to find those clusters. 8. In outlier detection by semi-supervised learning, what is the advantage of using objects without labels in the training data set? Answer: Since semi-supervised outlier detection methods assume that only some of the normal objects and outliers are labeled, or in some cases even no outliers are labeled, they are more widely applicable than supervised outlier detection methods. Semi-supervised outlier detection methods can make good use of the available unlabeled data, and build a more reliable model when the amount of labeled data is small. 9. To understand why angle-based outlier detection is a heuristic method, give an example where it does not work well. Can you come up with a method to overcome this issue? Answer: Consider the situation as shown in Figure 12.1. The angle-based outlier factor of o is big, however, it is an outlier.