Rough Sets, Granular Computing and Evidence Handling

Introduction and Context

Real-world data rarely provide complete, precise, and consistently measured knowledge. Medical records may contain missing observations, industrial sensors may produce conflicting readings, and customer data may describe the same individual at different levels of detail. Conventional statistical and machine-learning methods often address uncertainty through probability, fuzzy membership, or explicit assumptions about data-generating processes. Rough-set theory offers a different perspective: uncertainty may arise because the available attributes cannot distinguish between objects.

Rough sets, granular computing, and evidence-handling methods form a useful family of approaches for knowledge discovery from imperfect information. Rough sets identify what can definitely be inferred and what is only possibly inferred. Granular computing represents knowledge at multiple resolutions, ranging from broad categories to detailed observations. Evidence theories, especially Dempster–Shafer theory, represent support assigned to sets of hypotheses rather than forcing premature commitment to a single hypothesis.

These methods are particularly relevant to feature selection, interpretable rule extraction, decision support, anomaly analysis, and hybrid AI systems. Their value is greatest when interpretability, uncertainty representation, and reduction of redundant information are important.

Learning Objectives

After studying this chapter, the reader should be able to:

1. Define information systems, indiscernibility relations, equivalence classes, and decision tables.
2. Compute lower and upper approximations of a concept.
3. Explain boundary regions, accuracy, and roughness.
4. Derive and interpret reducts, cores, and dependency measures.
5. Extract interpretable decision rules from data.
6. Explain information granules and multilevel granular computing.
7. Distinguish rough-set uncertainty from probabilistic and fuzzy uncertainty.
8. Apply belief functions and evidence combination cautiously.
9. Evaluate feature-selection and knowledge-discovery applications.
10. Identify methodological, ethical, and governance limitations.

1. Information Systems and Indiscernibility

A finite information system is represented as S = (U, A), where U is a non-empty finite universe of objects and A is a set of attributes. Each attribute a ∈ A is a function a: U → V_a, where V_a is the set of permitted values for a.

For supervised decision analysis, attributes are divided into condition attributes C and a decision attribute d. The resulting structure DT = (U, C ∪ {d}) is called a decision table.

For any subset B ⊆ A, the indiscernibility relation induced by B is:

This relation assumes exact symbolic equality for the selected attributes. It is reflexive, symmetric, and transitive; therefore, it is an equivalence relation. The equivalence class of x is:

Objects in the same class cannot be distinguished using attributes in B. Thus, an equivalence class is an information granule: a group treated as identical at a particular resolution.

If attributes are numerical, exact equality may be inappropriate. Practical systems may discretize values into intervals, use tolerance relations, or define similarity-based neighborhoods. These adaptations change the relation and must be justified because they directly affect the resulting approximations and rules.

Illustrative decision table

Using condition attributes {Temperature, Vibration, Pressure}, objects 1 and 4 are indiscernible, and objects 2 and 6 are indiscernible. In this table, each equivalence class has a single decision value, so the condition attributes consistently determine the decision.

2. Lower and Upper Approximations

Let X ⊆ U be a target concept, such as the set of machines classified as faulty. Given an equivalence relation IND(B), the lower and upper approximations of X are defined as follows.

The lower approximation contains objects that certainly belong to X because their entire equivalence class is inside X. The upper approximation contains objects that possibly belong to X because their class has at least one member in X.

The boundary region is:

Objects in the boundary cannot be classified decisively using B. The negative region is:

These objects certainly do not belong to X.

A concept is exact, or crisp with respect to B, when its boundary is empty. It is rough when the boundary is non-empty.

Worked example

Suppose U = {1, 2, 3, 4, 5, 6}, and the equivalence classes induced by B are:

[1]_B = {1,4}, [2]_B = {2,6}, [3]_B = {3}, and [5]_B = {5}.

Let X = {2, 3, 5, 6}, representing faulty machines.

• Class {1,4} has no member in X, so it belongs to the negative region.
• Class {2,6} is entirely contained in X, so it belongs to the lower approximation.
• Classes {3} and {5} are also entirely contained in X.

Therefore:

B_*(X) = {2,3,5,6} and B^*(X) = {2,3,5,6}.

The boundary is empty, so X is exactly definable using B.

Now suppose the class {2,6} contains object 2 labelled faulty and object 6 labelled non-faulty. Then this class intersects X but is not contained in X. It belongs to the upper approximation but not to the lower approximation. The boundary would contain both objects in that class, reflecting unresolved classification.

Accuracy and quality of approximation

For a non-empty target set X, the accuracy of approximation is:

where |·| denotes set cardinality. The value lies between 0 and 1 when the upper approximation is non-empty. A value of 1 indicates an exact concept. A lower value indicates greater boundary uncertainty.

A commonly used roughness measure is:

This measure is applicable under the same finite, non-empty-upper-approximation assumptions. Accuracy measures definability relative to the chosen attributes and granulation; it is not a universal measure of predictive accuracy.

3. Dependency, Reducts and the Core

A decision D depends totally on condition attributes B, written B → D, if every equivalence class induced by B is contained in a single decision class. In practical terms, no two objects that are indiscernible under B receive conflicting decisions.

For a decision partition U/D, the positive region is:

The dependency degree is:

Here U/D denotes the set of decision classes. γ_B(D) = 1 means that every object can be classified consistently using B. A value below 1 indicates that some objects lie in boundary regions of decision classes.

Reducts

A reduct is a minimal subset R ⊆ C that preserves a selected property of the full condition set C. In classical rough-set feature selection, a common requirement is:

and no proper subset R′ ⊂ R satisfies the same equality. A reduct is therefore an inclusion-minimal, not necessarily minimum-cardinality, subset. Several different reducts may exist.

The core is the intersection of all reducts:

An attribute in the core is indispensable under the chosen dependency criterion. An empty core does not mean that the data lack useful attributes; it means that no single attribute is present in every reduct.

Discernibility matrix

For objects x_i and x_j with different decisions, define the discernibility set:

The discernibility function is formed as a conjunction over pairs and a disjunction within each discernibility set:

A minimal satisfying attribute set corresponds to a reduct. In implementation, Boolean minimization, greedy search, integer programming, or heuristic optimization may be used. The exact problem can become computationally difficult as the number of attributes and objects increases.

4. Rule Extraction

A rough-set decision rule commonly has the form:

IF condition 1 AND condition 2 AND … THEN decision.

For example:

IF vibration = High AND pressure = High THEN fault = Yes.

Rules may be certain or possible. A rule is certain when all objects satisfying its condition part belong to the same decision class. A possible rule has a mixed decision outcome.

For a rule with premise P and decision class Y, support can be expressed as:

Confidence, also called certainty in some rule-mining contexts, is:

provided |P| > 0. These definitions must not be confused with statistical confidence intervals. A rule with high confidence may still have low support if it applies to very few objects.

Rule quality should be evaluated using training and validation data. A rule extracted from a small or biased table may be perfectly consistent in-sample but unreliable in deployment. Discretization thresholds, missing-value treatment, class imbalance, and sampling design strongly influence the rule set.

5. Granular Computing

Granular computing studies problem solving through information granules: collections of objects grouped because they are similar, indistinguishable, functionally related, or treated together for a task. A granule can be a rough-set equivalence class, a fuzzy set, a cluster, an interval, a category, or a knowledge-graph neighborhood.

Granulation has two complementary effects:

• It reduces complexity by replacing many individual observations with meaningful groups.
• It introduces abstraction and therefore may hide distinctions relevant to a particular decision.

A granular representation is often described through three operations:

1. Granulation: divide or group information into granules.
2. Organization: arrange granules by abstraction, inclusion, similarity, or dependency.
3. Computing with granules: reason, classify, search, or make decisions using the granules.

Multilevel granularity

A system may contain a hierarchy from coarse to fine granules. For example, temperature can be represented as {low, medium, high}, or at a finer level as numerical intervals of 5 °C. Coarse granules support rapid reasoning and robust generalization; fine granules support precision but may increase noise and computational cost.

A granulation should be selected according to the task. A diagnostic system may need fine distinctions near a clinical threshold, whereas a strategic planning system may require only broad risk categories. Granularity is therefore a modelling decision, not merely a data-preprocessing step.

6. Rough Sets Compared with Other Uncertainty Models

These approaches are not interchangeable. A rough-set boundary does not mean that an object has a probability equal to its boundary proportion. Likewise, a fuzzy membership of 0.7 is not automatically a probability of 0.7. Hybrid systems can combine methods, but their semantics must remain explicit.

7. Evidence Handling with Belief Functions

Dempster–Shafer theory represents evidence over a frame of discernment Θ, whose elements are mutually exclusive and collectively exhaustive hypotheses. A basic probability assignment, or mass function, is:

with:

A mass may be assigned to a set A containing multiple hypotheses. This represents support for the set without choosing among its members. The belief and plausibility functions are:

where Ā is the complement of A in Θ. Bel(A) is committed support for A; Pl(A) is the maximum support A could receive given the evidence. The interval [Bel(A), Pl(A)] represents residual ignorance or imprecision.

Dempster’s rule of combination

For two independent sources with mass functions m₁ and m₂, the unnormalized conjunctive mass is:

The conflict is:

If K < 1, normalized Dempster combination for non-empty A is:

This rule assumes that the sources are sufficiently independent and that normalization of conflict is appropriate. High conflict can make the result unstable or counterintuitive. In such cases, preserving the conflict, discounting unreliable sources, or using an alternative combination rule may be preferable.

A sensor reliability factor r ∈ [0,1] can be applied through discounting:

Discounting transfers unsupported confidence to Θ, representing ignorance rather than assigning it to a particular hypothesis.

8. Integrated Feature Selection and Uncertain Knowledge Discovery

A practical pipeline may combine rough-set reduction with evidence handling:

1. Define the universe, condition attributes, and decision classes.
2. Clean and document missing, noisy, and inconsistent values.
3. Select a granulation strategy, such as discretization or tolerance neighbourhoods.
4. Compute indiscernibility classes and dependency measures.
5. Generate candidate reducts using discernibility analysis or heuristic search.
6. Extract rules from reducts.
7. Treat each rule, sensor, or model as a source of evidence.
8. Combine compatible evidence while monitoring conflict.
9. Validate predictive performance, stability, calibration, and interpretability.
10. Deploy with monitoring, human oversight, and an audit trail.

This pipeline separates two questions that are often confused: which attributes are necessary for a decision, and how should multiple uncertain sources be fused? Rough-set analysis primarily addresses the first question; evidence theory addresses the second.

9. Illustrative Case: Predictive Maintenance in a Manufacturing Plant

Background

A plant monitors motors using temperature, vibration, lubricant condition, and load. Engineers want an interpretable system that identifies imminent bearing failure while handling incomplete sensor readings.

Problem

The original system uses all sensor variables in a black-box classifier. Maintenance staff report that the model is difficult to audit, and two sensors sometimes produce conflicting indications.

Analysis

The historical maintenance table is discretized into domain-approved categories. Rough-set analysis shows that several reducts preserve the same decision dependency. One reduct uses vibration, lubricant condition, and load; another uses temperature, vibration, and lubricant condition. Temperature is absent from the core, indicating that it is not indispensable across all reducts, although it may still improve robustness.

The extracted rules include:

• IF vibration = high AND lubricant = poor THEN failure risk = high.
• IF vibration = low AND lubricant = good AND load = normal THEN failure risk = low.
• IF vibration = high AND lubricant = good THEN failure risk = uncertain.

The last rule is intentionally not forced into a definite class because historical objects with that condition have mixed outcomes.

A vibration sensor assigns mass 0.70 to high risk and 0.30 to Θ. A lubricant sensor assigns mass 0.60 to low risk and 0.40 to Θ. These sources strongly disagree. Applying Dempster’s rule produces a high conflict value because the focal sets high risk and low risk intersect trivially. The engineering team therefore avoids presenting a single overconfident result. Instead, it reports the conflict, requests a sensor check, and uses a conservative maintenance policy.

Outcome

The resulting system uses fewer attributes, produces readable rules, and explicitly distinguishes certain, possible, and conflicting evidence. It does not eliminate human judgement; it makes the basis for that judgement more visible.

Learning points

• Reducing features can improve interpretability without guaranteeing higher predictive accuracy.
• A boundary region is valuable information, not merely a modelling failure.
• Evidence conflict should be reported rather than hidden through automatic normalization.
• Domain-approved discretization and validation are essential for industrial deployment.

10. Limitations, Governance and Best Practices

Rough-set methods are sensitive to representation. Small changes in discretization, missing-value imputation, or noise can change equivalence classes and reducts. Multiple reducts may make feature selection unstable. Exact algorithms may become expensive for large datasets. Classical rough sets also assume crisp equality, which is often unrealistic for continuous measurements.

Evidence combination has its own risks. Dempster’s rule may behave unexpectedly under high conflict, and independence assumptions are frequently difficult to verify. Assigning masses is not automatically objective; elicitation procedures, calibration studies, and source-reliability estimates are needed.

In high-stakes AI, governance should include:

• documentation of attribute definitions and granulation choices;
• provenance for every evidence source;
• separate validation for subgroups and operating conditions;
• monitoring of data drift and rule stability;
• disclosure of uncertainty and conflict to decision-makers;
• human review for consequential actions;
• privacy protection and access control;
• versioning of tables, reducts, rules, and evidence-combination policies.

Fairness requires particular care. An apparently minimal reduct may retain proxy variables for protected characteristics. Removing an explicit sensitive attribute does not guarantee non-discrimination. Feature selection must therefore be evaluated together with fairness, not only dependency or predictive performance.

11. Contemporary Developments

Current research extends rough sets through variable-precision models, dominance-based rough sets for ordered preferences, covering-based and neighborhood rough sets, fuzzy-rough sets, dynamic rough sets for streaming data, and probabilistic rough sets. These variants address numerical data, noise, preferences, evolving concepts, and graded similarity.

Granular computing is increasingly connected with hierarchical clustering, concept lattices, knowledge graphs, multiresolution learning, and explainable AI. In streaming environments, adaptive granules can be updated as distributions change. In multimodal systems, evidence-handling methods can combine text, sensor, image, and expert evidence, although dependence and calibration remain central concerns.

A strong postgraduate research direction is to evaluate not only accuracy but also reduct stability, rule comprehensibility, uncertainty calibration, conflict sensitivity, computational cost, and downstream decision quality.

Chapter Summary

Rough-set theory models uncertainty caused by insufficient distinctions in available data. An indiscernibility relation partitions objects into equivalence classes, which act as information granules. Lower approximations contain objects certainly belonging to a concept, upper approximations contain objects possibly belonging to it, and the boundary identifies unresolved cases.

Dependency measures quantify how well condition attributes determine decisions. Reducts are minimal attribute subsets preserving a chosen property, while the core contains attributes common to every reduct. Discernibility matrices support systematic reduct computation, and reducts provide a foundation for interpretable rule extraction.

Granular computing treats abstraction and multiresolution representation as central computational principles. Dempster–Shafer evidence theory represents support for hypotheses and sets of hypotheses through mass, belief, and plausibility. Its combination rules require careful attention to source independence and conflict.

In applied AI, these methods support feature selection, interpretable discovery, sensor fusion, decision support, and uncertainty-aware governance. Their limitations—including representation sensitivity, computational cost, unstable reducts, and conflict-management problems—must be addressed through validation, documentation, monitoring, and human oversight.

Key Terms

Indiscernibility relation: Relation that groups objects having identical values on a selected attribute set.

Information system: Formal structure consisting of a universe of objects and attributes describing them.

Decision table: Information system containing condition attributes and a decision attribute.

Equivalence class: Set of objects indiscernible under a selected attribute subset.

Information granule: Group of objects treated as a unit at a particular resolution.

Lower approximation: Objects whose entire equivalence class belongs to a target concept.

Upper approximation: Objects whose equivalence class intersects a target concept.

Boundary region: Difference between upper and lower approximations.

Positive region: Objects certainly classifiable into decision classes using selected attributes.

Dependency degree: Proportion of objects in the positive region.

Reduct: Inclusion-minimal attribute subset preserving a specified property.

Core: Intersection of all reducts.

Discernibility matrix: Structure recording attributes that distinguish object pairs.

Decision rule: Conditional statement mapping attribute patterns to conclusions.

Granular computing: Computing through groups, abstractions, or information granules.

Frame of discernment: Set of mutually exclusive and exhaustive hypotheses.

Mass function: Assignment of evidence to subsets of a hypothesis frame.

Belief: Total committed support for a proposition.

Plausibility: Maximum support compatible with available evidence.

Conflict: Evidence assigned to mutually exclusive hypotheses during combination.

Review Questions

Short Answer Questions

1. What is an indiscernibility relation, and why is it an equivalence relation?
2. Distinguish lower approximation from upper approximation.
3. Define a reduct and explain why reducts may not be unique.
4. What does the boundary region represent?
5. Why can a mass function assign evidence to the whole frame of discernment?

Long Answer Questions

1. Explain rough-set approximations, positive regions, dependency, and their role in feature selection.
2. Describe the discernibility-matrix approach to reduct computation, including its assumptions and limitations.
3. Compare rough sets, fuzzy sets, probability, and Dempster–Shafer theory as models of uncertainty.
4. Explain granular computing and discuss how changing granularity affects generalization and interpretability.
5. Present the assumptions, equations, and limitations of Dempster’s rule of combination.

Analytical / Application Questions

1. Construct the equivalence classes, lower approximation, upper approximation, and boundary for a target decision class in a small decision table of your own design.
2. Given a decision table with at least five condition attributes, identify two candidate reducts and explain whether each preserves decision dependency.
3. Design an evidence-fusion policy for two conflicting industrial sensors. Specify how reliability, conflict, human review, and auditability will be handled.

Multiple Choice Questions with Answers

Question 1

Which set contains objects that certainly belong to a target concept X under attribute set B?

A. The lower approximation B_*(X)

B. The upper approximation B^*(X)

C. The negative region only

D. The discernibility matrix

Correct Answer: A. The lower approximation B_*(X)

Question 2

A reduct is best described as:

A. The complete set of condition attributes

B. An inclusion-minimal subset preserving a specified property

C. The set of all decision attributes

D. The set of boundary objects

Correct Answer: B. An inclusion-minimal subset preserving a specified property

Question 3

What does a non-empty boundary region indicate?

A. Every object is classified with certainty

B. No object belongs to the target concept

C. Some objects cannot be decisively classified using the selected attributes

D. The decision attribute is continuous

Correct Answer: C. Some objects cannot be decisively classified using the selected attributes

Question 4

The dependency degree γ_B(D) is calculated as:

A. |U| ÷ |POS_B(D)|

B. |POS_B(D)| ÷ |U|

C. |B^(X)| ÷ |B_(X)|

D. |B_(X)| − |B^(X)|

Correct Answer: B. |POS_B(D)| ÷ |U|

Question 5

The core of a decision system is:

A. The union of all decision classes

B. The intersection of all reducts

C. The upper approximation of every concept

D. The set of inconsistent objects

Correct Answer: B. The intersection of all reducts

Question 6

In Dempster–Shafer theory, m(Θ) commonly represents:

A. Certain evidence for one specific hypothesis

B. Evidence assigned to the empty set

C. Uncommitted evidence or ignorance over the frame

D. The conflict between two sources

Correct Answer: C. Uncommitted evidence or ignorance over the frame

Question 7

For a proposition A, plausibility is defined as:

A. The sum of masses of all subsets of A

B. The sum of masses of sets intersecting A

C. The mass assigned only to A

D. One minus the mass of Θ

Correct Answer: B. The sum of masses of sets intersecting A

Question 8

If an equivalence class is partly inside and partly outside X, it contributes to:

A. The lower approximation only

B. The negative region only

C. The boundary region

D. The core

Correct Answer: C. The boundary region

Question 9

Which statement about rough-set accuracy is correct?

A. It is always a probability of class membership

B. It equals |B_(X)| divided by |B^(X)| when the upper approximation is non-empty

C. It is defined only when the boundary is non-empty

D. It measures sensor reliability

Correct Answer: B. It equals |B_(X)| divided by |B^(X)| when the upper approximation is non-empty

Question 10

A major concern when applying normalized Dempster combination is:

A. It cannot represent ignorance

B. It requires all hypotheses to be continuous

C. High conflict can produce unstable or counterintuitive results

D. It always discards source reliability

Correct Answer: C. High conflict can produce unstable or counterintuitive results