Incomplete decision contexts: Approximate concept construction,rule acquisition and knowledge reduction

Incomplete decision contexts are a kind of decision formal contexts in which information about the relationship between some objects and attributes is not available or is lost. Knowledge discovery in incomplete decision contexts is of interest because such databases are frequently encountered in the real world. This paper mainly focuses on the issues of approximate concept construction, rule acquisition and knowledge reduction in incomplete decision contexts. We propose a novel method for building the approximate concept lattice of an incomplete context. Then, we present the notion of an approximate decision rule and an approach for extracting non-redundant approximate decision rules from an incomplete decision context. Furthermore, in order to make the rule acquisition easier and the extracted approximate decision rules more compact, a knowledge reduction framework with a reduction procedure for incomplete decision contexts is formulated by constructing a discernibility matrix and its associated Boolean function. Finally, some numerical experiments are conducted to assess the efficiency of the proposed method.     

Bi-criteria optimization problems for decision rules

We consider bi-criteria optimization problems for decision rules and rule systems relative to length and coverage. We study decision tables with many-valued decisions in which each row is associated with a set of decisions as well as single-valued decisions where each row has a single decision. Short rules are more understandable; rules covering more rows are more general. Both of these problems—minimization of length and maximization of coverage of rules are NP-hard. We create dynamic programming algorithms which can find the minimum length and the maximum coverage of rules, and can construct the set of Pareto optimal points for the corresponding bi-criteria optimization problem. This approach is applicable for medium-sized decision tables. However, the considered approach allows us to evaluate the quality of various heuristics for decision rule construction which are applicable for relatively big datasets. We can evaluate these heuristics from the point of view of (i) single-criterion—we can compare the length or coverage of rules constructed by heuristics; and (ii) bi-criteria—we can measure the distance of a point (length, coverage) corresponding to a heuristic from the set of Pareto optimal points. The presented results show that the best heuristics from the point of view of bi-criteria optimization are not always the best ones from the point of view of single-criterion optimization.     

EMPIRICAL BAYES TEST PROBLEMS OF VARIANCE COMPONENTS IN RANDOM EFFECTS MODEL

Bayes decision rule of variance components for one-way random effects model is derived and empirical Bayes (EB) decision rules are constructed by kernel estimation method. Under suitable conditions, it is shown that the proposed EB decision rules are asymptotically optimal with convergence rates near O(n^-1/2). Finally, an example concerning the main result is given.     

Uncertain agency models with multi-dimensional incomplete information based on confidence level

This paper discusses a principal–agent problem with multi-dimensional incomplete information between a principal and an agent. Firstly, how to describe the incomplete information in such agency problem is a challenging issue. This paper characterizes the incomplete information by uncertain variable, because it has been an appropriate tool to depict subjective assessment and model human uncertainty. Secondly, the relevant literature often used expected-utility-maximization to measure the two participators’ goals. However, Ellsberg paradox indicates that expected utility criterion is not always appropriate to be regarded as decision rule. For this reason, this paper presents another decision rule based on confidence level. Instead of expected-utility-maximization, the principal’s aim is to maximize his potential income under the acceptable confidence level, and the agent’s aim depends on whether he has private information about his efforts. According to the agent’s different decision rules, three classes of uncertain agency (UA) models and their respective optimal contracts are presented. Finally, a portfolio selection problem is studied to demonstrate the modeling idea and the viability of the proposed UA models.     

“限时服务规则”下的复线船闸多目标调度优化

针对现有船舶过闸排队规则的欠缺,基于“限时服务规则”,构建复线船闸多目标双层优化调度模型:上层模型用于获得两个闸室安全区域的船舶排布可行方案;下层模型用于获得不同船舶排布可行方案的优化闸次数。下层模型分两个阶段完成:对符合“限时服务规则”的船舶,构建以闸次最少为目标的0-1规划模型,获得此类船舶安排的闸次;对其余船舶按照“先到先服务规则”,构建以闸次最少、闸室利用率最大为目标的多目标决策模型,获得不同船舶排布可行方案应该安排的频次。以位于江苏省干线航道上的某复线船闸某日24小时内过闸船舶的数据为例,计算结果表明:采用本文优化模型获得的优化方案与“经验编排方式”相比,两座船闸各节约2个闸次,两个船闸的平均闸室利用率分别提高了3.66和4.72个百分点。     

Rough set based rule induction from two decision tables

We study rule induction from two decision tables as a basis of rough set analysis of more than one decision tables. We regard the rule induction process as enumerating minimal conditions satisfied with positive examples but unsatisfied with negative examples and/or with negative decision rules. From this point of view, we show that seven kinds of rule induction are conceivable for a single decision table. We point out that the set of all decision rules from two decision tables can be split in two levels: a first level decision rule is positively supported by a decision table and does not have any conflict with the other decision table and a second level decision rule is positively supported by both decision tables. To each level, we propose rule induction methods based on decision matrices. Through the discussions, we demonstrate that many kinds of rule induction are conceivable.     

An interval set model for learning rules from incomplete information table

A novel interval set approach is proposed in this paper to induce classification rules from incomplete information table, in which an interval-set-based model to represent the uncertain concepts is presented. The extensions of the concepts in incomplete information table are represented by interval sets, which regulate the upper and lower bounds of the uncertain concepts. Interval set operations are discussed, and the connectives of concepts are represented by the operations on interval sets. Certain inclusion, possible inclusion, and weak inclusion relations between interval sets are presented, which are introduced to induce strong rules and weak rules from incomplete information table. The related properties of the inclusion relations are proved. It is concluded that the strong rules are always true whatever the missing values may be, while the weak rules may be true when missing values are replaced by some certain known values. Moreover, a confidence function is defined to evaluate the weak rule. The proposed approach presents a new view on rule induction from incomplete data based on interval set.     

不完备直觉模糊信息系统的属性约简

利用优势关系,可对完备直觉模糊信息系统与决策信息表进行属性约简.将优势关系改进为广义优势关系,在此基础上构建了不完备直觉模糊信息系统与决策信息表的辨识矩阵,得到了求解属性约简与相对约简的具体方法.     

Multi-confidence rule acquisition and confidence-preserved attribute reduction in interval-valued decision systems

Rule acquisition is one of the most important objectives in the analysis of decision systems. Because of the interference of errors, a real-world decision system is generally inconsistent, which can lead to the consequence that some rules extracted from the system are not certain but possible rules. In practice, however, the possible rules with high confidence are also useful in making decision. With this consideration, we study how to extract from an interval-valued decision system the compact decision rules whose confidences are not less than a pre-specified threshold. Specifically, by properly defining a binary relation on an interval-valued information system, the concept of interval-valued granular rules is presented for the interval-valued decision system. Then, an index is introduced to measure the confidence of an interval-valued granular rule and an implication relationship is defined between the interval-valued granular rules whose confidences are not less than the threshold. Based on the implication relationship, a confidence-preserved attribute reduction approach is proposed to extract compact decision rules and a combinatorial optimization-based algorithm is developed to compute all the reducts of an interval-valued decision system. Finally, some numerical experiments are conducted to evaluate the performance of the reduction approach and the gain of using the possible rules in making decision.     

Rough set theory: a novel approach for extraction of robust decision rules based on incremental attributes

Rough set theory is a new data mining approach to manage vagueness. It is capable to discover important facts hidden in the data. Literature indicate the current rough set based approaches can’t guarantee that classification of a decision table is credible and it is not able to generate robust decision rules when new attributes are incrementally added in. In this study, an incremental attribute oriented rule-extraction algorithm is proposed to solve this deficiency commonly observed in the literature related to decision rule induction. The proposed approach considers incremental attributes based on the alternative rule extraction algorithm (AREA), which was presented for discovering preference-based rules according to the reducts with the maximum of strength index (SI), specifically the case that the desired reducts are not necessarily unique since several reducts could include the same value of SI. Using the AREA, an alternative rule can be defined as the rule which holds identical preference to the original decision rule and may be more attractive to a decision-maker than the original one. Through implementing the proposed approach, it can be effectively operating with new attributes to be added in the database/information systems. It is not required to re-compute the updated data set similar to the first step at the initial stage. The proposed algorithm also excludes these repetitive rules during the solution search stage since most of the rule induction approaches generate the repetitive rules. The proposed approach is capable to efficiently and effectively generate the complete, robust and non-repetitive decision rules. The rules derived from the data set provide an indication of how to effectively study this problem in further investigations.     

Comparison of selection rules for ordinal optimization

The evaluation of performance of a design for complex discrete event systems through simulation is usually very time consuming. Optimizing the system performance becomes even more computationally infeasible. Ordinal optimization (OO) is a technique introduced to attack this difficulty in system design by looking at “order” in performances among designs instead of “value” and providing a probability guarantee for a good enough solution instead of the best for sure. The selection rule, known as the rule to decide which subset of designs to select as the OO solution, is a key step in applying the OO method. Pairwise elimination and round robin comparison are two selection rule examples. Many other selection rules are also frequently used in the ordinal optimization literature. To compare selection rules, we first identify some general facts about selection rules. Then we use regression functions to quantify the efficiency of a group of selection rules, including some frequently used rules. A procedure to predict good selection rules is proposed and verified by simulation and by examples. Selection rules that work well most of the time are recommended.     

随机效应模型中方差分量的经验Bayes检验问题

给出了双向分类随机效应模型中方差分量的Bayes检验的判决函数,利用核估计的方法,构造了相应的经验Bayes(EB)检验的判决函数．在适当的条件下证明了EB判决函数是渐近最优的且有收敛速度．给出了模型的特例和推广．最后,举出一个满足定理条件的例子．     

基于粗糙集的突发事件属性约简方法

针对突发事件不完备信息系统中的原始数据存在大量属性冗余的问题,提出一种基于粗糙集的不完备信息系统属性约简方法,以剔除冗余属性,提高知识清晰度。首先对缺失、冗余、噪声以及连续型数据进行预处理;然后进行属性分类,将属性分为条件属性与决策属性,进而建立决策表;最后根据决策表的特征,结合有序加权平均算子的思想,提出一种基于属性重要度的启发式属性约简算法。文末,通过实例验证了方法的正确性与有效性,并利用该方法实现了火灾数据的属性约简。     

Rough sets for pattern classification using pairwise-comparison-based tables

Rough set theory is a useful mathematical tool to deal with vagueness and uncertainty in available information. The results of a rough set approach are usually presented in the form of a set of decision rules derived from a decision table. Because using the original decision table is not the only way to implement a rough set approach, it could be interesting to investigate possible improvement in classification performance by replacing the original table with an alternative table obtained by pairwise comparisons among patterns. In this paper, a decision table based on pairwise comparisons is generated using the preference relation as in the Preference Ranking Organization Methods for Enrichment Evaluations (PROMETHEE) methods, to gauges the intensity of preference for one pattern over another pattern on each criterion before classification. The rough-set-based rule classifier (RSRC) provided by the well-known library for the Rough Set Exploration System (RSES) running under Windows as been successfully used to generate decision rules by using the pairwise-comparisons-based tables. Specifically, parameters related to the preference function on each criterion have been determined using a genetic-algorithm-based approach. Computer simulations involving several real-world data sets have revealed that of the proposed classification method performs well compared to other well-known classification methods and to RSRC using the original tables.     

随机截尾试验变量抽样接收方案的贝叶斯决策

本运用Bayes决策理论研究指数分布和随机截尾试验的抽样接收方案的一般模型,我们证明了最优Bayes法则具有单调性,并对二个特殊的决策损失函数给出了最优Bayes法则和Bayes风险的具体表达式。     

On the risk-equivalence of two methods of randomization in statistics

For statistical decision problems, there are two well-known methods of randomization: on the one hand, randomization by means of mixtures of nonrandomized decision functions (randomized decision rules) in the game “statistician against nature,” on the other hand, randomization by means of randomized decision functions. In this paper, we consider the problem of risk-equivalence of these two procedures, i.e., imposing fairly general conditions on a nonsequential decision problem, it is shown that to each randomized decision rule, there is a randomized decision function with uniformly the same risk, and vice versa. The crucial argument is based on rewriting risk-equivalence in terms of Choquet's integral representation theorem. It is shown, in addition, that for certain special cases that do not fulfill the assumptions of the Main Theorem, risk-equivalence holds at least partially.     

不完备序区间值决策系统中的可信规则获取

以不完备序区间值决策系统为研究对象,其中不仅包含遗漏型未知区间值,而且属性值域为全序集.给出了未知区间值的三种形式及其填充式区间值的定义,引入灰的白化方法用以构建一个新的填充式不完备序白化值决策系统,并讨论其在优势和弱势关系下的可信规则获取.进一步研究了优势和弱势对象的约简以及其决策类的相对约简问题,给出了相应的判定定理与区分函数,为最终从不完备序区间值决策系统中获取最优可信决策规则提供了新的理论基础与操作手段.、     

基于属性关联的不完全风险偏好信息大群体应急决策方法

针对特大突发事件应急决策中大群体专家存在偏好信息不完全的问题,本文提出一种新的不完全风险性信息大群体应急决策方法。首先,利用最优离散拟合方法对决策者的风险偏好因子进行测度并据此对专家聚类;其次,根据不完全偏好矩阵进行属性关联测度,提出了基于风险偏好和属性关联的新的补值模型,得到完全偏好信息矩阵;然后,运用主成分分析方法提取属性主成分,并结合属性权重进行信息集结和方案择优;最后,通过台风“天鸽”事件验证所提方法的可行性和有效性。     

An empirical study of the complexity and randomness of prediction error sequences

We investigate a population of binary mistake sequences that result from learning with parametric models of different order. We obtain estimates of their error, algorithmic complexity and divergence from a purely random Bernoulli sequence. We study the relationship of these variables to the learner’s information density parameter which is defined as the ratio between the lengths of the compressed to uncompressed files that contain the learner’s decision rule. The results indicate that good learners have a low information density ρ while bad learners have a high ρ. Bad learners generate mistake sequences that are atypically complex or diverge stochastically from a purely random Bernoulli sequence. Good learners generate typically complex sequences with low divergence from Bernoulli sequences and they include mistake sequences generated by the Bayes optimal predictor. Based on the static algorithmic interference model of [18] the learner here acts as a static structure which “scatters” the bits of an input sequence (to be predicted) in proportion to its information density ρ thereby deforming its randomness characteristics.