Rough Sets Rebuilt: New Model Gives Meaning to Decisions Made With Missing Data

When a database is missing values, most machine learning systems either guess or throw the record away. A new theoretical study argues that both habits rest on shaky ground, and it offers a mathematically cleaner way to reason about what we know, what we do not know, and what we can only suspect. Writing in Applied Intelligence, Yiyu Yao and Qiaoyi Li of the University of Regina and Junfang Luo of Southwestern University of Finance and Economics present a formal model for rough set theory under incomplete information, grounding a family of widely used techniques in semantics that many researchers had previously left informal.

Rough set theory, introduced by Zdzisław Pawlak in 1982, is one of the quiet workhorses of data analysis. Its central idea is deceptively simple: given a table of objects described by attributes, objects with identical attribute values are considered indistinguishable, and any concept, meaning any subset of objects, can be approximated from below and above by sets that are definitely in the concept and sets that possibly belong to it. The gap between those two approximations is the rough set itself, a precise way of expressing uncertainty without assigning probabilities. The theory has powered applications from feature selection to rule mining for four decades.

Problems arise when the table is incomplete. If some attribute values are unknown, the tidy equivalence relation that groups objects into crisp blocks breaks down. Since the late 1990s, researchers have responded by replacing equivalence with various similarity relations, declaring two objects comparable when their known values agree or when missing values are treated as wildcards. Kryszkiewicz’s tolerance relation, Stefanowski and Tsoukias’s valued tolerance approach, maximal consistent blocks, and limited tolerance relations all sprang from this impulse. Each proposal encoded an intuition about what missing data means, but, as the new paper points out, most were defined by intuition alone.

That is the gap the Canadian-Chinese team set out to close. Their complaint is not that similarity-based rough sets fail to compute, but that nobody has fully explained what the resulting approximations mean. Without a sound semantics, different similarity relations produce different answers to the same question, and there is no principled way to choose among them or to detect when a model is being misused. The authors describe their work as an effort to interpret and construct concept-based granular rough sets under incomplete information with a direct reference to the main purpose of rough set theory: data analysis and concept formation.

The foundation of their model is the conjunctive concept space, an idea with deep roots. Concepts here are conjunctions of attribute-value conditions, in the spirit of formal concept analysis developed by Rudolf Wille and of Tom Mitchell’s classic version spaces from Stanford in 1979. Every object in a table satisfies a bundle of attribute-value pairs, and the most specific conjunctive concept an object instantiates is simply the conjunction of all the values recorded for it. In a complete table, that concept pins the object down exactly. In an incomplete table, it cannot, and that is where the trouble, and the opportunity, begins.

To handle the uncertainty, the authors revive a semantic framework proposed by Witold Lipski in 1979 for incomplete information databases. Lipski’s insight was that an incomplete table does not describe a single reality but a set of possible ones: every way of filling in the missing values yields a possible world, a complete table that is consistent with what is observed. Under this possible world semantics, a concept acquires not one extension but two. The lower extension, or positive region, contains the objects that are instances of the concept in every possible world, the ones we know for sure. The upper extension contains objects that are instances in at least one possible world, the ones that might be. The pair of sets brackets the truth, and everything between them is genuinely undecided.

The paper’s central technical result is that these two extensions are not exotic constructs at all. The authors prove that the set of objects definitely satisfying a concept and the set of possibly satisfying it are exactly the neighborhoods induced by two similarity relations, which they call the certain and possible similarity relations. In other words, the similarity relations that researchers have been inventing ad hoc for twenty-five years can be derived, rather than postulated, from a principled account of what missing values mean. The certain relation holds between two objects when they agree on all attributes known for the first; the possible relation additionally allows agreement when a known value of one object falls within the set of possible values of the other. The derivation gives similarity relations a formal and sound semantics for the first time in this setting, and the authors show the certain relation is reflexive and transitive while the possible relation is reflexive, properties that follow from the semantics rather than being assumed.

The same machinery illuminates three-way decision, a framework Yao himself has championed, which generalizes the binary accept-reject logic of classification into accept, reject, and defer. In rough set terms, the positive region supports acceptance, the negative region supports rejection, and the boundary region demands further evidence before commitment. Under incomplete information, the granular rough set model supplies structured approximations for each object’s most specific concept, so the three-way verdicts inherit a clear meaning: accept only when an object is an instance in all possible worlds, reject only when it is an instance in none, and otherwise withhold judgment. The authors connect this to a long line of recent work on three-way models for incomplete systems, including interval-set-based rule learning and regret-theoretic and fuzzy variants, and show how the semantic foundation can discipline them all.

The investigation is not purely celebratory. By forcing every existing method through the lens of possible world semantics, the authors expose difficulties with several of them. Similarity relations defined purely by intuition can conflate objects that should remain distinguishable in some completions of the table, or blur the line between what is certainly true and what is merely possible. Some neighborhood-based approximations in the literature, they argue, lack a defensible interpretation of what their positive and boundary regions actually assert about the data. The paper’s conclusion is a call to arms: semantics-related issues deserve far more study, and the results should guide future research and prevent misuse of models of incomplete information.

Why should anyone outside the rough set community care? Because incomplete information is the normal condition of real data, from medical records with unrecorded tests to sensor networks with dropout to survey data with refusals. The distinction between knowing that something is false and merely not knowing that it is true is one of the oldest problems in logic and database theory, and it is the difference between a system that makes defensible decisions and one that silently fabricates certainty. By deriving similarity, granularity, and three-way decision from a single semantic source, this work offers the field something rare in applied mathematics: a theory that explains not just how to compute with missing data, but what those computations are actually claiming about the world.

Subject of Research: A formal semantics for rough set theory and three-way decision making under incomplete information

Article Title: Rough sets under incomplete information: Concept formation and three-way decision perspectives

Article References: Rough sets under incomplete information: Concept formation and three-way decision perspectives. (n.d.). https://doi.org/10.1007/s10489-026-07518-1

Image Credits: AI Generated

DOI: 10.1007/s10489-026-07518-1

Keywords: rough sets, incomplete information, three-way decision, possible world semantics, similarity relations, concept formation, conjunctive concept space, granular computing, Pawlak rough sets, interval sets, data analysis, Applied Intelligence