Actionable Three-Way Decisions

Abstract

In this thesis, we analyze both the trisecting and acting aspects of three-way decisions. In an evaluation based model of three-way decisions, there are two steps: trisecting and acting. The trisecting step constructs three regions based on an evaluation func- tion and a pair of thresholds. The acting step adopts proper strategies to deal with objects in these regions. For the trisecting step, this thesis examines statistical interpretations for the con- struction of three regions. The interpretations rely on an understanding that the middle region consists of normal or typical instances in a population, while two side regions consist of, abnormal or atypical instances. By using statistical information such as median, mean, percentiles, and standard deviation, two interpretations are discussed. One is based on non-numeric values and the other is based on numeric values. For non-numeric values, median and percentiles are used to construct three pair-wise disjoint regions. For numeric values, mean and standard deviation are used. The interpretations provide a solid statistical basis of three-way decisions for appli- cations. This thesis analyzes a chi-square statistic as a measure for searching for the optimal pair of thresholds for trisecting. An optimization based method for determining the pair of thresholds is to minimize or maximize an objective function that quanti es the quality, cost, or bene t of a trisection. We use the chi-square statistic to interpret and establish an objective function in the context of classi cation. The maximization of the chi-square statistic searches for a strong correlation between the trisection and the classi cation. For the acting step, this thesis introduces actionable strategies to three-way de- cision. We present a general framework of actionable three-way decisions with four change-based actionable models according to action bene t and action cost. Two of the four models provide the bounds of the cost and bene t and the other two models quantify the maximum bene t under limited cost and the minimum cost for a desired bene t, respectively. We design and analyze algorithms for these models. To reduce action cost and increase bene t, we introduce the R4 reduction frame- work for actionable three-way decision. The framework consists of reductions of attributes, attribute-value pairs, classi cation rules, and actions for creating more bene t and reducing cost. The rst three types of reductions are rede ned for the context of three-way decisions and the action reduction is proposed. Attribute reduc- tion removes some attributes from all classi cation rules to reduce the action cost. Attribute-value pair reduction shortens the left hand side of a rule to reduce the ac- tion cost without sacri cing any classi cation power or action bene t. Rule reduction and action reduction remove redundant classi cation rules and actions, respectively, to reduce computational cost. The Addition strategy for reduction is adapted and its correctness is proven. Based on this strategy, an algorithm for attribute and attribute-value pair reductions is designed. Finally, we report experimental results to support the proposed four actionable three-way decision models and the R4 reduction framework.