Rough sets by reflexive relations and their algebras

1. Problemstellung und Motivation

Das Paper untersucht die algebraische Struktur der Menge der Rough Sets (Rohmengen), die durch eine reflexive Relation $R$ auf einer Grundmenge $U$ induziert werden.

• Hintergrund: In der klassischen Rough-Set-Theorie (nach Pawlak) wird Wissen durch eine Äquivalenzrelation modelliert. Die resultierende Menge der Rough Sets bildet einen regulären doppelten Stone-Algebra.
• Verallgemeinerung: Viele Anwendungen erfordern schwächere Relationen, wie Quasiordnungen (reflexiv und transitiv) oder Toleranzrelationen (reflexiv und symmetrisch). Für diese Fälle ist die Struktur der Rough Sets oft komplexer; sie bilden nicht immer vollständige Verbände oder spezifische Algebren.
• Das spezifische Problem: Für eine beliebige reflexive Relation (die weder transitiv noch symmetrisch sein muss) ist die geordnete Menge der Rough Sets $RS$ nicht notwendigerweise ein Verband. Um die algebraischen Eigenschaften zu analysieren, greifen die Autoren auf die Dedekind-MacNeille-Vervollständigung $DM(RS)$ zurück.
• Ziel: Die Autoren wollen die Bedingungen identifizieren, unter denen $DM(RS)$ für reflexive Relationen spezifische algebraische Strukturen bildet, insbesondere:
  • Reguläre pseudokomplementierte Kleene-Algebren.
  • Vollständig distributive doppelte Stone-Algebren.
  • Reguläre doppelte Stone-Algebren (eine Verallgemeinerung des Äquivalenzfalles).

2. Methodik

Die Arbeit kombiniert Methoden aus der Gittertheorie, der Rough-Set-Theorie und der Universalalgebra.

• Dedekind-MacNeille-Vervollständigung: Da $RS$ für allgemeine reflexive Relationen kein vollständiger Verband sein muss, wird $DM(RS)$ als der kleinste vollständige Verband, der $RS$ enthält, untersucht. Die Elemente von $DM(RS)$ werden als Paare $(A, B)$ aus unteren und oberen Approximationen charakterisiert, die bestimmte Schnittbedingungen erfüllen.
• Algebraische Charakterisierung: Die Autoren analysieren die Eigenschaften von $DM(RS)$ unter der Annahme, dass es ein räumlicher (spatial) und vollständig distributiver Verband ist. Dies erlaubt die Nutzung von Eigenschaften vollständig join-irreduzibler Elemente.
• Kernkonzepte (Core): Ein zentrales Werkzeug ist die Definition des „Kerns" (core) einer Nachbarschaft $R(x)$:
  $$\text{core}_R(x) := \{w \in R(x) \mid w \in R(y) \implies R(x) \subseteq R(y)\}$$
  Diese Konstruktion wird genutzt, um Pseudokomplemente in $DM(RS)$ explizit zu berechnen.
• Strukturelle Analyse: Die Autoren leiten notwendige und hinreichende Bedingungen für die Regularität und die Stone-Eigenschaften her, indem sie die Hierarchie der join-irreduziblen Elemente in $DM(RS)$ und deren Beziehung zu den Atomen in den Verbänden der Approximationen ($\wp(U)^\blacktriangle$) untersuchen.

3. Wichtige Beiträge und Ergebnisse

A. Pseudokomplemente und Kleene-Algebren

Die Autoren zeigen, dass wenn der Verband der oberen Approximationen $\wp(U)^\blacktriangle$ pseudokomplementiert ist, auch $DM(RS)$ pseudokomplementiert ist.

• Sie leiten eine explizite Formel für das Pseudokomplement $(A, B)^*$ her:
  $$(A, B)^* = (B^{*\blacktriangledown\blacktriangle}, B^*)$$
  wobei $B^*$ das Pseudokomplement von $B$ in $\wp(U)^\blacktriangle$ ist.
• Ergebnis: Wenn $\wp(U)^\blacktriangle$ vollständig distributiv ist, bildet $DM(RS)$ eine pseudokomplementierte Kleene-Algebra.

B. Regularität und die „zwei-Niveau"-Bedingung

Ein Hauptbeitrag ist die Charakterisierung der Regularität (im Sinne der Kongruenz-Regularität).

• Theorem 5.3: $DM(RS)$ ist eine reguläre, räumliche, vollständig distributive pseudokomplementierte Kleene-Algebra genau dann, wenn $\wp(U)^\blacktriangle$ ein atomarer Boolescher Verband ist.
• Dies bedeutet, dass die join-irreduziblen Elemente von $DM(RS)$ höchstens zwei „Niveaus" haben dürfen (d.h., es gibt keine Ketten der Länge 3 in der Menge der join-irreduziblen Elemente).

C. Stone-Algebren und die Bedingung (St1)

Die Autoren charakterisieren, wann $DM(RS)$ eine Stone-Algebra ist (d.h. $x^* \vee x^{**} = 1$).

• Sie führen die Bedingung (St1) ein: Wenn $\{x\}^\blacktriangle, \{y\}^\blacktriangle \subseteq \{p\}^\blacktriangle$, dann existiert ein $z \in U$, sodass $\{z\}^\blacktriangle \subseteq \{x\}^\blacktriangle$ und $\{z\}^\blacktriangle \subseteq \{y\}^\blacktriangle$.
• Theorem 6.4: Unter der Annahme, dass $DM(RS)$ räumlich und vollständig distributiv ist, ist $DM(RS)$ genau dann eine Stone-Algebra, wenn (St1) gilt.
• Im Fall atomarer Verbände ist dies äquivalent dazu, dass jedes $\{p\}^\blacktriangle$ genau ein Atom enthält.

D. Reguläre doppelte Stone-Algebren und „Clinker-Äquivalenzen"

Der bedeutendste theoretische Fortschritt ist die Identifizierung einer neuen Klasse von Relationen, die zu regulären doppelten Stone-Algebren führen.

• Theorem 7.2: $DM(RS)$ bildet eine reguläre doppelte Stone-Algebra genau dann, wenn die Relation $R$ die Bedingung (rSt) erfüllt: Für jedes $x \in U$ ist $\{x\}^\blacktriangle$ ein Atom in $\wp(U)^\blacktriangle$ und $\text{core}_{\check{R}}(x) \neq \emptyset$.
• Neue Definition: Die Autoren definieren eine Clinker-Äquivalenz (clinker equivalence) als eine reflexive Relation, bei der die Familie $\{\{x\}^\blacktriangle \mid x \in U\}$ eine irredundante Überdeckung von $U$ bildet.
• Proposition 7.6: $DM(RS)$ ist eine reguläre doppelte Stone-Algebra genau dann, wenn $R$ eine Clinker-Äquivalenz ist.
• Dies stellt eine echte Verallgemeinerung der Äquivalenzrelation dar. Ein Äquivalenzrelation ist ein Spezialfall einer Clinker-Äquivalenz, aber es gibt Clinker-Äquivalenzen, die nicht transitiv oder symmetrisch sind (siehe Beispiel 7.7 im Paper).

4. Signifikanz und Implikationen

1. Erweiterung der Theorie: Das Paper erweitert die algebraische Theorie der Rough Sets über den klassischen Fall der Äquivalenzrelationen hinaus. Es zeigt, dass auch für nicht-transitive und nicht-symmetrische reflexive Relationen starke algebraische Strukturen (wie reguläre doppelte Stone-Algebren) existieren können.
2. Neue Relationenklasse: Die Einführung der Clinker-Äquivalenzen bietet ein neues mathematisches Werkzeug zur Modellierung von Ähnlichkeitsrelationen, die in der Praxis häufiger vorkommen als strikte Äquivalenzen (z.B. in der Datenanalyse mit Unsicherheit oder in der linguistischen Ähnlichkeit, wie im Introduction durch Tversky's Zitate angedeutet).
3. Konstruktive Methode: Die Autoren liefern eine konstruktive Methode (Remark 7.8), um solche Algebren zu generieren: Man beginnt mit einer irredundanten Überdeckung und definiert die Relation so, dass die Nachbarschaften den Elementen der Überdeckung entsprechen.
4. Verbindung zur Vollständigkeit: Die Arbeit klärt den Zusammenhang zwischen der Struktur der Approximationsverbände ($\wp(U)^\blacktriangle$) und der Struktur der Vervollständigung $DM(RS)$. Sie zeigt, dass die algebraischen Eigenschaften von $DM(RS)$ stark von der atomaren Struktur der oberen Approximationen abhängen.

Fazit:
Die Autoren haben erfolgreich die Bedingungen identifiziert, unter denen die Vervollständigung der Rough Sets für reflexive Relationen eine reguläre doppelte Stone-Algebra bildet. Dies führt zur Entdeckung der „Clinker-Äquivalenzen", einer neuen, allgemeineren Klasse von Relationen, die die Äquivalenzrelationen als Spezialfall enthalten und dennoch die gewünschten algebraischen Eigenschaften bewahren. Dies ist ein wichtiger Schritt hin zu einer allgemeineren algebraischen Theorie von Rough Sets für unsymmetrische und nicht-transitive Daten.