Подход приблизительного набора на основе доминирования

редактировать

Подход приблизительного набора на основе доминирования (DRSA ) расширение теории приблизительных множеств для многокритериального анализа решений (MCDA), представленное Греко, Матараццо и Словински. Основным изменением по сравнению с классическими грубыми наборами является замена отношения неразличимости отношением доминирования, что позволяет иметь дело с несоответствиями, типичными для рассмотрения критериев и предпочтения. -упорядоченные классы решений .

Содержание

1 Многокритериальная классификация (сортировка)
2 Представление данных
- 2.1 Таблица решений
- 2.2 Отношение выигрыша
- 2.3 Классы решений и объединения классов
3 Основные концепции
- 3.1 Доминирование
- 3.2 Грубые приближения
- 3.3 Качество приближения и редукции
4 Правила принятия решений
5 Пример
6 Расширения
- 6.1 Многокритериальный выбор и задачи ранжирования
- 6.2 Переменная -согласованность DRSA
- 6.3 Стохастический DRSA
7 Программное обеспечение
8 См. также
9 Ссылки
10 Внешние ссылки

Многокритериальная классификация (сортировка)

Многокритериальная классификация () - одна из проблем, рассматриваемых в MCDA, и ее можно сформулировать следующим образом: при заданном наборе объектов оценивается связанных набором (атрибутов с доменами порядка предпочтений), назначьте эти объекты некоторым предопределенным и упорядоченным по предпочтениям классам решений, так что каждый объект будет назначен ровно одному классу. За счет упорядочения предпочтений улучшение оценок объекта по критериям не должно ухудшать присвоение ему класса. Проблема сортировки очень похожа на проблему классификации, однако в последнем случае объекты оцениваются с помощью обычных атрибутов, а классы решений не обязательно упорядочены по предпочтениям. Проблема многокритериальной классификации также упоминается и часто возникает в реальных приложениях, когда свойства порядковый и монотонный вытекают из знания предметной области о проблеме.

В качестве наглядного примера рассмотрим задачу оценивания в средней школе. Директор школы хочет распределить учащихся (предметы) по трем классам: плохой, средний и хороший (обратите внимание, что хороший класс предпочтительнее среднего, а средний предпочтительнее плохого). Каждый учащийся описывается по трем критериям: уровень физики, математики и литературы, каждый из которых принимает одно из трех возможных значений: плохой, средний и хороший. Критерии упорядочены по предпочтениям, и повышение уровня по одному из предметов не должно приводить к ухудшению общей оценки (класса).

В качестве более серьезного примера рассмотрим классификацию клиентов банка с точки зрения риска банкротства на классы безопасных и рискованных. Это может включать такие характеристики, как «рентабельность капитала (ROE)», «рентабельность инвестиций (ROI)» и «рентабельность продаж (ROS)».. Домены этих атрибутов не просто упорядочены, но включают порядок предпочтений, поскольку с точки зрения менеджеров банка, более высокие значения ROE, ROI или ROS лучше для клиентов, анализируемых на предмет риска банкротства. Таким образом, эти атрибуты являются критериями. Пренебрежение этой информацией в knowledge discovery может привести к неверным выводам.

Представление данных

Таблица решений

В DRSA данные часто представляются с использованием определенной формы таблицы решений. Формально таблица решений DRSA представляет собой кортеж из 4 элементов $S = ⟨U, Q, V, f⟩ {\ displaystyle S = \ langle U, Q, V, f \ rangle}$ $S=\langle U,Q,V,f\rangle$ , где $U {\ displaystyle U \, \!}$ ${\ displaystyle U \, \!}$ - конечный набор объектов, $Q {\ displaystyle Q \, \!}$ $Q\,\!$ - конечный набор критерии, $V = ⋃ q ∈ QV q {\ displaystyle V = \ bigcup {} _ {q \ in Q} V_ {q}}$ ${\ displaystyle V = \ bigcup {} _ {q \ in Q} V_ {q}}$ где $V q {\ displaystyle V_ { q} \, \!}$ ${\ displaystyle V_ {q} \, \!}$ - это область определения критерия $q {\ displaystyle q \, \!}$ $q \, \!$ и $f: U × Q → V { \ displaystyle f \ двоеточие U \ times Q \ to V}$ ${\ displaystyle f \ двоеточие U \ times Q \ to V}$ - это информационная функция, такая что $f (x, q) ∈ V q {\ displaystyle f (x, q) \ in V_ { q}}$ $f(x,q)\in V_{q}$ для каждого $(x, q) ∈ U × Q {\ displaystyle (x, q) \ in U \ times Q}$ $(x,q)\in U\times Q$ . Набор $Q {\ displaystyle Q \, \!}$ $Q\,\!$ разделен на критерии условия (набор $C ≠ ∅ {\ displaystyle C \ neq \ emptyset}$ ${\ displaystyle C \ neq \ emptyset}$ ) и критерий решения (класс) $d {\ displaystyle d \, \!}$ $d \, \!$ . Обратите внимание, что $f (x, q) {\ displaystyle f (x, q) \, \!}$ ${\ displaystyle f (x, q) \, \!}$ - это оценка объекта $x {\ displaystyle x \, \!}$ $x \, \!$ по критерию $q ∈ C {\ displaystyle q \ in C}$ ${ \ displaystyle q \ in C}$ , а $f (x, d) {\ displaystyle f (x, d) \, \!}$ ${\ displaystyle f (x, d) \, \!}$ - присвоение класса (значение решения) объекта. Пример таблицы решений показан в таблице 1 ниже.

Отношение выигрыша

Предполагается, что область критерия $q ∈ Q {\ displaystyle q \ in Q}$ $q \ in Q$ полностью предварительно упорядочена на $⪰ q {\ displaystyle \ successq _ {q}}$ $\succeq _{q}$ ; $x ⪰ qy {\ displaystyle x \ successq _ {q} y}$ $x\succeq _{q}y$ означает, что $x { \ displaystyle x \, \!}$ $x \, \!$ по крайней мере так же хорошо, как (превосходит) $y {\ displaystyle y \, \!}$ $y\,\!$ по критерию $д {\ Displaystyle д \, \!}$ $q \, \!$ . Без ограничения общности, мы предполагаем, что область $q {\ displaystyle q \, \!}$ $q \, \!$ является подмножеством реалов, $V q ⊆ R { \ displaystyle V_ {q} \ substeq \ mathbb {R}}$ ${\ displaystyle V_ {q} \ substeq \ mathbb {R}}$ , и что соотношение выигрышей представляет собой простой порядок между действительными числами $≥ {\ displaystyle \ geq \, \!}$ ${\ displaystyle \ geq \, \!}$ такое, что выполняется следующее соотношение: $x ⪰ qy ⟺ f (x, q) ≥ f (y, q) {\ displaystyle x \ successq _ {q} y \ iff f (x, q) \ geq f (y, q)}$ $x\succeq _{q}y\iff f(x,q)\geq f(y,q)$ . Это соотношение является прямым для критерия типа усиления («чем больше, тем лучше»), например прибыль компании. Для критерия типа затрат («чем меньше, тем лучше»), например цена продукта, это соотношение может быть удовлетворено путем отрицания значений из $V q {\ displaystyle V_ {q} \, \!}$ ${\ displaystyle V_ {q} \, \!}$ .

Классы решений и объединения классов

Пусть $T = {1,…, n} {\ displaystyle T = \ {1, \ ldots, n \} \, \!}$ ${\ displaystyle T = \ {1, \ ldots, n \} \, \!}$ . Область критерия решения, $V d {\ displaystyle V_ {d} \, \!}$ $V_{d}\,\!$ состоит из $n {\ displaystyle n \, \!}$ $n \, \!$ элементы (без ограничения общности мы предполагаем $V d = T {\ displaystyle V_ {d} = T \, \!}$ ${\ displaystyle V_ {d} = T \, \ !}$ ) и индуцирует разделение $U {\ displaystyle U \, \!}$ ${\ displaystyle U \, \!}$ в $n {\ displaystyle n \, \!}$ $n \, \!$ классы $Cl = {C lt, t ∈ T} {\ displaystyle {\ textbf {Cl}} = \ {Cl_ {t}, t \ in T \}}$ ${\textbf {Cl}}=\{Cl_{t},t\in T\}$ , где $C lt = {x ∈ U: f (x, d) = t} {\ displaystyle Cl_ {t} = \ {x \ in U \ двоеточие f (x, d) = t \}}$ ${\ displaystyle Cl_ { t} = \ {x \ in U \ двоеточие f (x, d) = t \}}$ . Каждому объекту $x ∈ U {\ displaystyle x \ in U}$ $x \ in U$ присвоен один и только один класс $C lt, t ∈ T {\ displaystyle Cl_ {t}, t \ in Т}$ $Cl_{t},t\in T$ . Классы упорядочены по предпочтениям в соответствии с возрастающим порядком индексов классов, т.е. для всех $r, s ∈ T {\ displaystyle r, s \ in T}$ $r,s\in T$ таких, что $r ≥ s {\ displaystyle r \ geq s \, \!}$ ${\ displaystyle r \ geq s \, \!}$ , объекты из $C lr {\ displaystyle Cl_ {r} \, \!}$ ${\ displaystyle Cl_ {r} \, \!}$ строго предпочтительнее объекты из $C ls {\ displaystyle Cl_ {s} \, \!}$ $Cl_{s}\,\!$ . По этой причине мы можем рассматривать восходящие и нисходящие объединения классов, определяемые соответственно как:

C lt ≥ = ⋃ s ≥ t C ls C lt ≤ = ⋃ s ≤ t C lst ∈ T {\ displaystyle Cl_ {t} ^ {\ geq} = \ bigcup _ {s \ geq t} Cl_ {s} \ qquad Cl_ {t} ^ {\ leq} = \ bigcup _ {s \ leq t} Cl_ { s} \ qquad t \ in T}

Cl_{t}^{\geq }=\bigcup _{s\geq t}Cl_{s}\qquad Cl_{t}^{\leq }=\bigcup _{s\leq t}Cl_{s}\qquad t\in T

Основные понятия

Доминирование

Мы говорим, что $x {\ displaystyle x \, \!}$ $x \, \!$ доминирует $y {\ displaystyle y \, \!}$ $y\,\!$ относительно $P ⊆ C {\ displaystyle P \ substeq C}$ $P\subseteq C$ , обозначается $x D py {\ displaystyle xD_ {p} y \, \!}$ $xD_{p}y\,\!$ , если $x {\ displaystyle x \, \!}$ $x \, \!$ лучше, чем $y {\ displaystyle y \, \!}$ $y\,\!$ по каждому критерию из $P {\ displaystyle P \, \!}$ $P\,\!$ , $x ⪰ qy, ∀ q ∈ P {\ displaystyle x \ successq _ {q } y, \, \ forall q \ в P}$ ${\ displaystyle x \ successq _ {q} y, \, \ forall q \ in P}$ . Для каждого $P ⊆ C {\ displaystyle P \ substeq C}$ $P\subseteq C$ отношение доминирования $DP {\ displaystyle D_ {P} \, \!}$ ${\ displaystyle D_ {P} \, \!}$ равно рефлексивный и транзитивный, то есть это частичный предварительный заказ. Для $P ⊆ C {\ displaystyle P \ substeq C}$ $P\subseteq C$ и $x ∈ U {\ displaystyle x \ in U}$ $x \ in U$ , пусть

DP + ( х) = {y ∈ U: y D px} {\ displaystyle D_ {P} ^ {+} (x) = \ {y \ in U \ двоеточие yD_ {p} x \}}

D_{P}^{+}(x)=\{y\in U\colon yD_{p}x\}

DP - (x) = {y ∈ U: x D py} {\ displaystyle D_ {P} ^ {-} (x) = \ {y \ in U \ двоеточие xD_ {p} y \}}

D_{P}^{-}(x)=\{y\in U\colon xD_{p}y\}

представляют P -доминирующий набор и P-доминирующий набор по отношению к $x ∈ U {\ displaystyle x \ in U}$ $x \ in U$ соответственно.

Грубые приближения

Ключевая идея философии приблизительного набора - это приближение одного знания другим знанием. В DRSA аппроксимируемые знания представляют собой совокупность восходящих и нисходящих объединений классов решений, а «гранулы знания», используемые для аппроксимации, являются P-доминирующими и P-доминирующими множествами.

P-нижнее и P-верхнее приближение из $C lt ≥, t ∈ T {\ displaystyle Cl_ {t} ^ {\ geq }, t \ in T}$ $Cl_{t}^{\geq },t\in T$ в отношении $P ⊆ C {\ displaystyle P \ substeq C}$ $P\subseteq C$ , обозначается как $P _ (C lt ≥) { \ displaystyle {\ underline {P}} (Cl_ {t} ^ {\ geq})}$ ${\ displaystyle {\ underline {P}} (Cl_ {т } ^ {\ geq})}$ и $P ¯ (C lt ≥) {\ displaystyle {\ overline {P}} (Cl_ {t} ^ {\ geq})}$ ${\overline {P}}(Cl_{t}^{\geq })$ соответственно определяются как:

P _ (C lt ≥) = {x ∈ U: DP + (x) ⊆ C lt ≥} { \ displaystyle {\ underline {P}} (Cl_ {t} ^ {\ geq}) = \ {x \ in U \ двоеточие D_ {P} ^ {+} (x) \ substeq Cl_ {t} ^ {\ geq } \}}

{\underline {P}}(Cl_{t}^{\geq })=\{x\in U\colon D_{P}^{+}(x)\subseteq Cl_{t}^{\geq }\}

P ¯ (C lt ≥) = {x ∈ U: DP - (x) ∩ C lt ≥ ≠ ∅} {\ displaystyle {\ overline {P}} (Cl_ {t} ^ {\ geq}) = \ {x \ in U \ двоеточие D_ {P} ^ {-} (x) \ cap Cl_ {t} ^ {\ geq} \ neq \ emptyset \}}

{\ displaystyle {\ overline {P}} (Cl_ {t} ^ {\ geq}) = \ {x \ in U \ двоеточие D_ {P} ^ {-} (x) \ cap Cl_ {t} ^ {\ geq} \ neq \ emptyset \}}

Аналогично, P-нижний и P-верхнее приближение $C lt ≤, t ∈ T {\ displaystyle Cl_ {t} ^ {\ leq}, t \ in T}$ $Cl_{t}^{\leq },t\in T$ относительно $P ⊆ C {\ displaystyle P \ substeq C}$ $P\subseteq C$ , обозначается как $P _ (C lt ≤) {\ displaystyle {\ un derline {P}} (Cl_ {t} ^ {\ leq})}$ ${\ displaystyle {\ underline {P}} (Cl_ {t} ^ {\ leq})}$ и $P ¯ (C lt ≤) {\ displaystyle {\ overline {P}} (Cl_ {t} ^ {\ leq})}$ ${\overline {P}}(Cl_{t}^{\leq })$ соответственно определяются как:

P _ (C lt ≤) = {x ∈ U: DP - (x) ⊆ C lt ≤} {\ displaystyle {\ подчеркивание {P}} (Cl_ {t} ^ {\ leq}) = \ {x \ in U \ двоеточие D_ {P} ^ {-} (x) \ substeq Cl_ {t} ^ {\ leq} \}}

{\ displaystyle {\ underline {P}} (Cl_ {t} ^ {\ leq}) = \ {x \ in U \ двоеточие D_ {P} ^ {-} (x) \ substeq Cl_ {t } ^ {\ leq} \}}

п ¯ (C lt ≤) знак равно {x ∈ U: DP + (x) ∩ C lt ≤ ≠ ∅} {\ displaystyle {\ overline {P}} (Cl_ {t} ^ {\ leq}) = \ {x \ in U \ двоеточие D_ {P} ^ {+} (x) \ cap Cl_ {t} ^ {\ leq} \ neq \ emptyset \}}

{\ displaystyle {\ overline {P}} (Cl_ {t} ^ {\ leq}) = \ {x \ in U \ двоеточие D_ {P} ^ {+} (x) \ cap Cl_ {t} ^ {\ leq} \ neq \ emptyset \}}

Нижние приближения группируют объекты, которые определенно принадлежат классу объединение $C lt ≥ {\ displaystyle Cl_ {t} ^ {\ geq}}$ $Cl_{t}^{\geq }$ (соответственно $C lt ≤ {\ displaystyle Cl_ {t} ^ {\ leq}}$ ${\ displaystyle Cl_ {t} ^ {\ leq}}$ ). Эта уверенность исходит из того факта, что объект $x ∈ U {\ displaystyle x \ in U}$ $x \ in U$ принадлежит к нижнему приближению $P _ (C lt ≥) {\ displaystyle {\ underline {P}} (Cl_ {t} ^ {\ geq})}$ ${\ displaystyle {\ underline {P}} (Cl_ {т } ^ {\ geq})}$ (соответственно $P _ (C lt ≤) {\ displaystyle {\ underline {P}} (Cl_ {t} ^ {\ leq})}$ ${\ displaystyle {\ underline {P}} (Cl_ {t} ^ {\ leq})}$ ), если никакой другой объект в $U {\ displaystyle U \, \!}$ ${\ displaystyle U \, \!}$ не противоречит этому утверждению, т.е. каждый объект $y ∈ U {\ displaystyle y \ in U}$ $y \in U$ , который P-доминирует $x {\ displaystyle x \, \!}$ $x \, \!$ , также принадлежит к объединению классов $C lt ≥ {\ displaystyle Cl_ {t} ^ {\ geq}}$ $Cl_{t}^{\geq }$ (соответственно $C lt ≤ {\ displaystyle Cl_ {t} ^ {\ leq}}$ ${\ displaystyle Cl_ {t} ^ {\ leq}}$ ). Верхнее приближение группирует объекты, которые могут принадлежать $C lt ≥ {\ displaystyle Cl_ {t} ^ {\ geq}}$ $Cl_{t}^{\geq }$ (соответственно $C lt ≤ {\ displaystyle Cl_ {t} ^ {\ leq}}$ ${\ displaystyle Cl_ {t} ^ {\ leq}}$ ), поскольку объект $x ∈ U {\ displaystyle x \ in U}$ $x \ in U$ принадлежит к верхнему приближению $P ¯ (C lt ≥) {\ displaystyle {\ overline {P}} (Cl_ {t} ^ {\ geq})}$ ${\overline {P}}(Cl_{t}^{\geq })$ (соответственно $P ¯ (C lt ≤) {\ displaystyle {\ overline {P}} (Cl_ {t} ^ {\ leq})}$ ${\overline {P}}(Cl_{t}^{\leq })$ ), если существует другой объект $y ∈ U {\ displaystyle y \ in U}$ $y \in U$ с преобладанием P $x {\ displaystyle x \, \!}$ $x \, \!$ из объединения классов $C lt ≥ {\ displaystyle Cl_ {t} ^ {\ geq}}$ $Cl_{t}^{\geq }$ (соответственно $C lt ≤ {\ displaystyle Cl_ {t} ^ {\ leq}}$ ${\ displaystyle Cl_ {t} ^ {\ leq}}$ ).

Аппроксимации P-нижний и P-верхний, определенные как выше, удовлетворяют следующим свойствам для всех $t ∈ T {\ displaystyle t \ in T}$ $t \ in T$ и для любого $П ⊆ C {\ Displaystyle P \ substeq C}$ $P\subseteq C$ :

P _ (C lt ≥) ⊆ C lt ≥ ⊆ P ¯ (C lt ≥) {\ displaystyle {\ underline {P}} (Cl_ {t} ^ { \ geq}) \ substeq Cl_ {t} ^ {\ geq} \ substeq {\ overline {P}} (Cl_ {t} ^ {\ geq})}

{\ displaystyle {\ underline {P}} (Cl_ {t} ^ {\ geq}) \ substeq Cl_ {t} ^ {\ geq} \ substeq {\ overline {P}} (Cl_ {t} ^ {\ geq})}

P _ (C lt ≤) ⊆ C lt ≤ ⊆ п ¯ (C lt ≤) {\ displaystyle {\ underline {P}} (Cl_ {t} ^ {\ leq}) \ substeq Cl_ {t} ^ {\ leq} \ substeq {\ overline {P}} ( Cl_ {t} ^ {\ leq})}

{\underline {P}}(Cl_{t}^{\leq })\subseteq Cl_{t}^{\leq }\subseteq {\overline {P}}(Cl_{t}^ {\leq })

P-границы (P-сомнительные области) $C lt ≥ {\ displaystyle Cl_ {t} ^ {\ geq}}$ $Cl_{t}^{\geq }$ и $C lt ≤ {\ displaystyle Cl_ {t} ^ {\ leq}}$ ${\ displaystyle Cl_ {t} ^ {\ leq}}$ определяются как:

B n P (C lt ≥) = P ¯ (C lt ≥) - P _ (C lt ≥) {\ Displaystyle Bn_ {P} (Cl_ {t} ^ {\ geq}) = {\ overline {P}} (Cl_ {t} ^ {\ geq}) - {\ подчеркивание {P}} (Cl_ {t} ^ {\ geq})}

{\ displaystyle Bn_ {P} (Cl_ {t} ^ {\ geq}) = {\ overline {P}} (Cl_ {t} ^ {\ geq}) - {\ underline {P}} (Cl_ {t} ^ {\ geq})}

B n P (C lt ≤) = P ¯ (C lt ≤) - P _ (C lt ≤) {\ displaystyle Bn_ {P} (Cl_ {t} ^ {\ leq}) = {\ overline {P}} (Cl_ {t} ^ {\ leq }) - {\ underline {P}} (Cl_ {t} ^ {\ leq})}

{\ displaystyle Bn_ {P} (Cl_ {t} ^ {\ leq}) = {\ overline {P}} (Cl_ {t} ^ {\ leq}) - {\ underline {P}} (Cl_ {t} ^ {\ leq})}

Качество приближения и понижает

Отношение

γ P (Cl) = | U - ((t ∈ T B n P (C l t ≥)) ∪ (⋃ t ∈ T B n P (C l t ≤))) | | U | {\ displaystyle \ gamma _ {P} ({\ textbf {Cl}}) = {\ frac {\ left | U- \ left (\ left (\ bigcup _ {т \ in T} Bn_ {P} (Cl_ { t} ^ {\ geq}) \ right) \ cup \ left (\ bigcup _ {t \ in T} Bn_ {P} (Cl_ {t} ^ {\ leq}) \ right) \ right) \ right |} {| U |}}}

{\ displaystyle \ gamma _ {P} ({\ textbf {Cl }}) = {\ frac {\ left | U- \ left (\ left (\ bigcup _ {t \ in T} Bn_ {P} (Cl_ {t} ^ {\ geq}) \ right) \ cup \ left (\ bigcup _ {t \ in T} Bn_ {P} (Cl_ {t} ^ {\ leq}) \ right) \ right) \ right |} {| U |}}}

определяет качество приближения раздела $Cl {\ displaystyle {\ textbf {Cl}} \, \!}$ ${\textbf {Cl}}\,\!$ в классы с помощью набора критериев $P {\ displaystyle P \, \!}$ $P\,\!$ . Это соотношение выражает отношение между всеми P-правильно классифицированными объектами и всеми объектами в таблице.

Каждое минимальное подмножество $P ⊆ C {\ displaystyle P \ substeq C}$ $P\subseteq C$ такое, что $γ P (C l) = γ C (C l) {\ displaystyle \ gamma _ {P} (\ mathbf {Cl}) = \ gamma _ {C} (\ mathbf {Cl}) \, \!}$ $\gamma _{P}(\mathbf {Cl})=\gamma _{C}(\mathbf {Cl})\,\!$ называется reduct из $C {\ displaystyle C \, \!}$ $C\,\!$ и обозначается $REDC l (P) {\ displaystyle RED _ {\ mathbf {Cl}} (P) }$ $RED_{\mathbf {Cl} }(P)$ . Таблица решений может иметь более одного сокращения. Пересечение всех редуктов называется ядром.

Правила принятия решений

На основе приближений, полученных с помощью отношений доминирования, можно вызвать обобщенное описание предпочтительной информации, содержащейся в таблице решений, в терминах правила принятия решений. Правила принятия решения - это выражения формы if [условие], затем [следствие], которые представляют форму зависимости между критериями условия и критериями решения. В процедурах генерации правил принятия решений из таблицы решений используется принцип индуктивного обучения. Можно выделить три типа правил: определенные, возможные и приблизительные. Некоторые правила генерируются из более низких приближений объединений классов; возможные правила генерируются из верхних приближений объединений классов, а приближенные правила генерируются из граничных областей.

Некоторые правила имеют следующую форму:

, если $f (x, q 1) ≤ r 1 {\ displaystyle f (x, q_ {1}) \ Leq r_ {1} \, \!}$ ${\ displaystyle f (x, q_ {1}) \ leq r_ {1} \, \!}$ и $f (x, q 2) ≤ r 2 {\ displaystyle f (x, q_ {2}) \ leq r_ {2} \, \!}$ ${\ displaystyle f (x, q_ {2}) \ leq r_ {2} \, \!}$ и $… f (x, qp) ≤ rp {\ displaystyle \ ldots f (x, q_ {p}) \ leq r_ {p} \, \!}$ $\ldots f(x,q_{p})\leq r_{p}\,\!$ тогда $x ∈ C lt ≤ {\ displaystyle x \ in Cl_ {t} ^ {\ leq}}$ $x\in Cl_{t}^{\leq }$

Возможные правила имеют аналогичный синтаксис, однако последующая часть правила имеет вид: $x {\ displaystyle x \, \!}$ $x \, \!$ может принадлежать $C lt ≥ {\ displaystyle Cl_ {t} ^ {\ geq}}$ $Cl_{t}^{\geq }$ или форме : $x {\ displaystyle x \, \!}$ $x \, \!$ может принадлежать $C lt ≤ {\ displaystyle Cl_ {t} ^ {\ leq}}$ ${\ displaystyle Cl_ {t} ^ {\ leq}}$ .

Наконец, приблизительные правила имеют синтаксис:

если $f (x, q 1) ≥ r 1 {\ displaystyle f (x, q_ {1}) \ geq r_ {1} \, \!}$ $f(x,q_{1})\geq r_{1}\,\!$ и $f (x, q 2) ≥ r 2 {\ displaystyle f (x, q_ {2}) \ geq r_ {2} \, \!}$ $f(x,q_{2})\geq r_{2}\,\!$ и $… е (х, qk) ≥ rk {\ displaystyle \ ldots f (x, q_ {k}) \ geq r_ {k} \, \!}$ ${\ displaystyle \ ldots f (x, q_ {k}) \ geq r_ {k} \, \!}$ и $f (x, qk + 1) ≤ rk + 1 {\ displaystyle f (x, q_ {k + 1}) \ leq r_ {k + 1} \, \!}$ ${\ displaystyle f (x, q_ {k + 1}) \ leq r_ {k + 1} \, \!}$ и $f (x, qk + 2) ≤ rk + 2 {\ displaystyle f (x, q_ {k + 2}) \ leq r_ {k + 2} \, \!}$ ${\ displaystyle f (x, q_ {k + 2}) \ leq r_ {k + 2} \, \ !}$ и $… f (x, qp) ≤ rp {\ displaystyle \ ldots f (x, q_ {p}) \ leq r_ {p} \, \!}$ $\ldots f(x,q_{p})\leq r_{p}\,\!$ тогда $x ∈ C ls ∪ C ls + 1 ∪ C lt {\ displaystyle x \ in Cl_ {s} \ cup Cl_ {s + 1} \ cup Cl_ {t}}$ $x\in Cl_{s}\cup Cl_{s+1}\cup Cl_{t}$

Определенные, возможные и приблизительные правила представляют собой определенные, возможные и неоднозначные знания, извлеченные из таблицы решений.

Каждое правило принятия решения должно быть минимальным. Поскольку решающее правило - это импликация, под минимальным решающим правилом мы понимаем такой импликации, что нет другого импликации с антецедентом, по крайней мере, такой же слабости (другими словами, правило, использующее подмножество элементарных условий или / и более слабых элементарных условия) и следствие, по крайней мере, такой же силы (другими словами, правило, относящее объекты к одному и тому же объединению или подсоюзу классов).

Набор правил принятия решений считается полным, если он может охватывать все объекты из таблицы решений таким образом, что согласованные объекты переклассифицируются в их исходные классы, а несогласованные объекты классифицируются в кластеры классов, ссылающихся на к этому несоответствию. Мы называем минимальным каждый набор правил принятия решений полным и неизбыточным, т.е. исключение любого правила из этого набора делает его неполным. Для получения набора решающих правил может быть принята одна из трех стратегий индукции:

генерация минимального описания, т. Е. Минимального набора правил,
генерация исчерпывающего описания, т. Е. Всех правил для данного матрица данных,
генерация описания характеристики, т. е. набора правил, охватывающих относительно много объектов каждый, но все вместе не обязательно все объекты из таблицы решений

Самый популярный алгоритм индукции правил для доминирования - Основанный на приблизительном наборе подход - DOMLEM, который генерирует минимальный набор правил.

Пример

Рассмотрим следующую проблему оценок учащихся старших классов:

Таблица 1: Пример - оценки средней школы
объект (ученик)	$q 1 {\ displaystyle q_ {1}}$ $q_{1}$ . (математика)	$q 2 {\ displaystyle q_ {2}}$ $q_{2}$ . (физика)	$q 3 {\ displaystyle q_ {3}}$ $q_{3}$ . (литература)	$d {\ displaystyle d}$ $d$ . (общая оценка)
$x 1 {\ displaystyle x_ {1}}$ $x_{1}$	medium	medium	bad	bad
$x 2 {\ displaystyle x_ {2}}$ $x_{2}$	хорошо	medium	плохой	средний
$x 3 {\ displaystyle x_ {3}}$ $x_ {3}$	средний	хороший	плохой	средний
$x 4 {\ displaystyle x_ {4}}$ $x_{4}$	плохой	средний	хорошее	плохое
$x 5 {\ displaystyle x_ {5}}$ $x_5$	плохое	плохое	среднее	плохое
$x 6 {\ displaystyle x_ { 6}}$ $x_{6}$	плохо	среднее	среднее	среднее
$x 7 {\ displaystyle x_ {7}}$ ${\ displaystyle x_ {7}}$	хорошо	хорошее	плохо	хорошо
$x 8 {\ displaystyle x_ {8}}$ $x_{8}$	хорошо	medium	medium	medium
$x 9{\ displaystyle x_ {9}}$ $x_{9}$	средний	средний	хороший	хороший
$x 10 {\ displaystyle x_ {10}}$ $x_ {10}$	хороший	средний	хорошо	хорошо

Каждый объект (студент) описывается тремя критериями $q 1, q 2, q 3 {\ displaystyle q_ {1}, q_ {2 }, q_ {3} \, \!}$ ${\ displaystyle q_ {1}, q_ {2}, q_ {3} \, \!}$ , относящиеся к уровням математики, физики и литературы соответственно. В соответствии с атрибутом решения учащиеся делятся на три класса, упорядоченных по предпочтениям: $C l 1 = {bad} {\ displaystyle Cl_ {1} = \ {bad \}}$ ${\ displaystyle Cl_ {1} = \ {bad \}}$ , $C l 2 = {medium } {\ displaystyle Cl_ {2} = \ {medium \}}$ $Cl_{2}=\{medium\}$ и $C l 3 = {хорошо} {\ displaystyle Cl_ {3} = \ {good \}}$ $Cl_{3}=\{good\}$ . Таким образом, были аппроксимированы следующие объединения классов:

$C l 1 ≤ {\ displaystyle Cl_ {1} ^ {\ leq}}$ ${\ displaystyle Cl_ {1} ^ {\ leq}}$ т.е. класс (максимум) плохих учеников,
$C l 2 ≤ {\ displaystyle Cl_ {2} ^ {\ leq}}$ ${ \ displaystyle Cl_ {2} ^ {\ leq}}$ т.е. класс не более средних студентов
$C l 2 ≥ {\ displaystyle Cl_ {2} ^ {\ geq}}$ ${\ displaystyle Cl_ { 2} ^ {\ geq}}$ т.е. класс как минимум средних учеников,
$C l 3 ≥ {\ displaystyle Cl_ {3} ^ {\ geq}}$ $Cl_{3}^{\geq }$ т.е. класс (по крайней мере) хороших студентов.

Обратите внимание, что оценки объектов $x 4 {\ displaystyle x_ {4} \, \!}$ ${\ displaystyle x_ {4} \, \!}$ и $x 6 {\ displaystyle x_ {6} \, \!}$ $x_{6}\,\!$ несовместимы, потому что $x 4 {\ displaystyle x_ {4} \, \!}$ ${\ displaystyle x_ {4} \, \!}$ имеет лучшие оценки по всем трем критериям, чем $x 6 {\ displaystyle x_ {6} \, \!}$ $x_{6}\,\!$ , но глобальный рейтинг хуже.

Следовательно, нижние приближения объединений классов состоят из следующих объектов:

P _ (C l 1 ≤) = {x 1, x 5} {\ displaystyle {\ underline {P}} (Cl_ {1} ^ {\ leq}) = \ {x_ {1}, x_ {5} \}}

{\ displaystyle {\ underline {P}} (Cl_ {1} ^ {\ leq}) = \ {x_ {1}, x_ {5} \}}

P _ (C l 2 ≤) = {x 1, x 2, x 3, x 4, x 5, Икс 6, Икс 8} = С l 2 ≤ {\ Displaystyle {\ underline {P}} (Cl_ {2} ^ {\ leq}) = \ {x_ {1}, x_ {2}, x_ {3 }, x_ {4}, x_ {5}, x_ {6}, x_ {8} \} = Cl_ {2} ^ {\ leq}}

{\underline {P}}(Cl_{2}^{\leq })=\{x_{1},x_{2},x_{3},x_{4},x_{5},x_{6},x_{8}\}=Cl_{2}^{\leq }

P _ (C l 2 ≥) = {x 2, х 3, х 7, х 8, х 9, х 10} {\ displaystyle {\ underline {P}} (Cl_ {2} ^ {\ geq}) = \ {x_ {2}, x_ {3}, x_ {7}, x_ {8}, x_ {9}, x_ {10} \}}

{\ displaystyle {\ underline {P}} (Cl_ {2} ^ {\ geq}) = \ {x_ {2}, x_ {3}, x_ {7}, x_ {8}, x_ {9}, x_ {10} \}}

P _ (C l 3 ≥) = {x 7, x 9, x 10} = C l 3 ≥ {\ displaystyle {\ underline {P}} (Cl_ {3} ^ {\ geq}) = \ {x_ {7}, x_ {9}, x_ {10} \} = Cl_ {3} ^ {\ geq}}

{\ displaystyle {\ underline {P}} (Cl_ {3} ^ {\ geq}) = \ {x_ {7}, x_ {9}, x_ {10} \} = Cl_ {3} ^ {\ geq} }

Таким образом, только классы $C l 1 ≤ {\ displaystyle Cl_ {1} ^ {\ leq}}$ ${\ displaystyle Cl_ {1} ^ {\ leq}}$ и $C l 2 ≥ {\ displaystyle Cl_ {2} ^ {\ geq}}$ ${\ displaystyle Cl_ { 2} ^ {\ geq}}$ нельзя точно определить. Их верхние приближения следующие:

P ¯ (C l 1 ≤) = {x 1, x 4, x 5, x 6} {\ displaystyle {\ overline {P}} (Cl_ {1} ^ {\ leq}) = \ {x_ {1}, x_ {4}, x_ {5}, x_ {6} \}}

{\overline {P}}(Cl_{1}^{\leq })=\{x_{1},x_{4},x_{5},x_{6}\}

P ¯ (C l 2 ≥) = {x 2, x 3, x 4, х 6, х 7, х 8, х 9, х 10} {\ displaystyle {\ overline {P}} (Cl_ {2} ^ {\ geq}) = \ {x_ {2}, x_ {3}, x_ {4}, x_ {6}, x_ {7}, x_ {8}, x_ {9}, x_ {10} \}}

{\ displaystyle {\ overline {P}} (Cl_ {2} ^ {\ geq}) = \ {x_ {2}, x_ {3}, x_ {4}, x_ {6}, x_ {7}, x_ {8}, x_ {9}, x_ {10} \}}

, а их граничные области:

B n P (C l 1 ≤) знак равно B N P (C l 2 ≥) = {x 4, x 6} {\ displaystyle Bn_ {P} (Cl_ {1} ^ {\ leq}) = Bn_ {P} (Cl_ {2} ^ { \ geq}) = \ {x_ {4}, x_ {6} \}}

{\ displaystyle Bn_ {P} (Cl_ {1} ^ {\ leq}) = Bn_ {P} (Cl_ {2} ^ {\ geq}) = \ {x_ {4}, x_ {6} \}}

Конечно, поскольку $C l 2 ≤ {\ displaystyle Cl_ {2} ^ {\ leq}}$ ${ \ displaystyle Cl_ {2} ^ {\ leq}}$ и $C l 3 ≥ {\ displaystyle Cl_ {3} ^ {\ geq}}$ $Cl_{3}^{\geq }$ точно аппроксимируются, мы имеем $P ¯ (C l 2 ≤) = C l 2 ≤ {\ displaystyle {\ overline {P}} (Cl_ {2} ^ {\ leq}) = Cl_ {2} ^ {\ leq}}$ ${\ displaystyle {\ overline {P}} (Cl_ {2} ^ {\ leq}) = Cl_ {2} ^ {\ leq}}$ , $P ¯ (C l 3 ≥) = C l 3 ≥ { \ Displaystyle {\ overline {P}} (Cl_ {3} ^ {\ geq}) = Cl_ {3} ^ {\ geq}}$ ${\overline {P}}(Cl_{3}^{\geq })=Cl_{3}^{\geq }$ и $B n P (C l 2 ≤) Знак равно В N п (C l 3 ≥) знак равно ∅ {\ Displaystyle Bn_ {P} (Cl_ {2} ^ {\ leq}) = Bn_ {P} (Cl_ {3} ^ {\ geq}) = \ emptyset}$ $Bn_{P}(Cl_{2}^{\leq })=Bn_{P}(Cl_{3}^{\ geq })=\emptyset$

Следующий минимальный набор из 10 правил может быть выведен из таблицы решений:

если $P hysics ≤ bad {\ displaystyle Physics \ leq bad}$ $Physics\leq bad$ , то $student ≤ плохо {\ displaystyle student \ leq bad}$ $student\leq bad$
если $L итература ≤ плохо {\ displaystyle Literature \ leq bad}$ $Literature\leq bad$ и $P hysics ≤ medium {\ displaystyle Physics \ leq medium }$ $Physics\leq medium$ и $M ath ≤ medium {\ displaystyle Math \ leq medium}$ $Math\leq medium$ тогда $студент ≤ плохой {\ displaystyle student \ leq bad}$ $student\leq bad$
если $M ath ≤ bad {\ displaystyle Math \ leq bad}$ $Math\leq bad$ тогда $student ≤ medium {\ displaystyle student \ leq medium}$ $student\leq medium$
если $L итература ≤ medium {\ displaystyle Literature \ leq medium}$ ${\ displaystyle Literature \ leq medium}$ и $P hysics ≤ medium {\ displaystyle Physics \ leq medium}$ $Physics\leq medium$ тогда $student ≤ medium {\ displaystyle student \ leq medium}$ $student\leq medium$
если $M ath ≤ средний {\ displaystyle Math \ leq medium}$ $Math\leq medium$ и $L итература ≤ плохой {\ displaystyle Literature \ leq bad}$ $Literature\leq bad$ , тогда $student ≤ medium {\ displaystyle student \ leq medium}$ $student\leq medium$
если $L итература ≥ хорошо {\ displaystyle Literature \ geq good}$ ${\ displaystyle Literature \ geq good}$ и $M ath ≥ medium {\ displaystyle Math \ geq medium}$ $Math\geq medium$ затем $студент ≥ хорошо {\ displaystyle student \ geq good}$ $student\geq good$
если $P hysics ≥ good {\ displaystyle Physics \ geq good}$ $Physics\geq good$ и $M ath ≥ good {\ displaystyle Math \ geq good}$ ${\ displaystyle Math \ geq good}$ тогда $студент ≥ хорошо {\ displaystyle student \ geq good}$ $student\geq good$
если $M ath ≥ good {\ displaystyle Math \ geq good}$ ${\ displaystyle Math \ geq good}$ , то $студент ≥ medium {\ displaystyle student \ geq medium}$ ${\ displaystyle student \ geq medium}$
if $P hysics ≥ good {\ displaystyle Physics \ geq good}$ $Physics\geq good$ тогда $student ≥ medium {\ displaystyle student \ geq medium}$ ${\ displaystyle student \ geq medium}$
если $M ath ≤ bad {\ displaystyle Math \ leq bad}$ $Math\leq bad$ и $P hysics ≥ me d я U м {\ displaystyle Physics \ geq medium}$ $Physics\geq medium$ затем $s t u d e n t = b a d ∨ m e d i u m {\ displaystyle student = bad \ lor medium}$ $student=bad\lor medium$

Последнее правило является приблизительным, а остальные - точными.

Расширения

Многокритериальный выбор и задачи ранжирования

Две другие проблемы, рассматриваемые в рамках многокритериального анализа решений и ранжирования проблемы, также можно решить, используя приблизительный подход, основанный на преобладании. Это делается путем преобразования таблицы решений в (PCT).

DRSA с переменной согласованностью

Определения грубых приближений основаны на строгом применении принципа доминирования. Однако при определении однозначных объектов разумно принять ограниченную долю отрицательных примеров, особенно для больших таблиц решений. Такая расширенная версия DRSA называется моделью (VC-DRSA)

Стохастическим DRSA

В реальных данных, особенно для больших наборов данных, понятия грубых приближений оказались чрезмерно ограничительными. Поэтому было введено расширение DRSA, основанное на стохастической модели (), которое допускает некоторую несогласованность. Сформулировав вероятностную модель для задач порядковой классификации с ограничениями монотонности, концепции нижних приближений распространяются на стохастический случай. Метод основан на оценке условных вероятностей с использованием непараметрического метода максимального правдоподобия, который приводит к проблеме изотонической регрессии.

Приблизительные наборы на основе стохастического доминирования также можно рассматривать как своего рода переменную. -модель согласованности.

Программное обеспечение

4eMka2 - это система поддержки принятия решений для задач классификации по множеству критериев, основанных на приблизительных наборах на основе доминирования (DRSA). JAMM является более продвинутым преемником 4eMka2. Обе системы бесплатно доступны для некоммерческих целей на веб-сайте Лаборатории интеллектуальных систем поддержки принятия решений (IDSS).

См. Также

Ссылки

Чахар С., Ишизака А., Лабиб А., Саад И. ( 2016). Основанный на доминировании приблизительный подход для групповых решений, European Journal of Operational Research, 251 (1): 206-224
Ли С., Ли Т. Чжан З., Чен Х., Чжан Дж. (2015 г.)). Параллельное вычисление приближений в подходе грубых множеств на основе доминирования, системы, основанные на знаниях, 87: 102-111
Ли С., Ли Т. (2015). Постепенное обновление приближений в подходе грубых множеств на основе доминирования при изменении значений атрибутов, Информационные науки, 294: 348-361
Ли С., Ли Т., Лю Д. (2013). Динамическое поддержание приближений в подходе грубых множеств на основе доминирования при изменении множества объектов, International Journal of Intelligent Systems, 28 (8): 729-751

Внешние ссылки

Международное общество грубых множеств
Лаборатория интеллектуальных систем поддержки принятия решений (IDSS) в Познаньском технологическом университете.
Обширный список ссылок DRSA на домашней странице Roman Słowiński.