Грубый набор

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

Определения

В следующем разделе содержится обзор основных принципов грубой теории множеств, первоначально предложенных Здиславом И. Павляком , а также некоторые ключевые определения. Более формальные свойства и границы грубых множеств можно найти в Pawlak (1991) и в цитируемых ссылках. Первоначальную и основную теорию грубых множеств иногда называют «грубыми множествами Павлака» или «классическими грубыми множествами» , чтобы отличить ее от более поздних расширений и обобщений.

Структура информационной системы

Позволять $I=(\mathbb {U} ,\mathbb {A} )$ быть информационной системой ( системой атрибут-значение ), где $\mathbb {U}$ представляет собой непустое конечное множество объектов (вселенная) и $\mathbb {A}$ — непустое конечное множество атрибутов такое, что $I:\mathbb {U} \rightarrow V_{a}$ для каждого $a\in \mathbb {A}$ . $V_{a}$ это набор значений, которые атрибутируют $a$ может возьму. Информационная таблица присваивает значение $a(x)$ от $V_{a}$ каждому атрибуту $a$ и объект $x$ во вселенной $\mathbb {U}$ .

С любым $P\subseteq \mathbb {A}$ существует связанное отношение эквивалентности $\mathrm {IND} (P)$ :

\mathrm {IND} (P)=\left\{(x,y)\in \mathbb {U} ^{2}\mid \forall a\in P,a(x)=a(y)\right\}

Отношение $\mathrm {IND} (P)$ называется $P$ - отношение неразличимости . Раздел $\mathbb {U}$ является семейством всех эквивалентности классов $\mathrm {IND} (P)$ и обозначается $\mathbb {U} /\mathrm {IND} (P)$ (или $\mathbb {U} /P$ ).

Если $(x,y)\in \mathrm {IND} (P)$ , затем $x$ и $y$ неотличимы от (или неотличимы) по признакам $P$ .

Классы эквивалентности $P$ -отношения неразличимости обозначаются $[x]_{P}$ .

Пример: структура класса эквивалентности

Например, рассмотрим следующую информационную таблицу:

Образец информационной системы
Объект	$P_{1}$	$P_{2}$	$P_{3}$	$P_{4}$	$P_{5}$
$O_{1}$	1	2	0	1	1
$O_{2}$	1	2	0	1	1
$O_{3}$	2	0	0	1	0
$O_{4}$	0	0	1	2	1
$O_{5}$	2	1	0	2	1
$O_{6}$	0	0	1	2	2
$O_{7}$	2	0	0	1	0
$O_{8}$	0	1	2	2	1
$O_{9}$	2	1	0	2	2
$O_{10}$	2	0	0	1	0

Когда полный набор атрибутов $P=\{P_{1},P_{2},P_{3},P_{4},P_{5}\}$ рассматриваем, мы видим, что имеем следующие семь классов эквивалентности:

{\begin{cases}\{O_{1},O_{2}\}\\\{O_{3},O_{7},O_{10}\}\\\{O_{4}\}\\\{O_{5}\}\\\{O_{6}\}\\\{O_{8}\}\\\{O_{9}\}\end{cases}}

Таким образом, два объекта в первом классе эквивалентности, $\{O_{1},O_{2}\}$ , невозможно отличить друг от друга на основе доступных атрибутов, а также трех объектов второго класса эквивалентности, $\{O_{3},O_{7},O_{10}\}$ , невозможно отличить друг от друга на основе доступных атрибутов. Остальные пять объектов отличимы от всех остальных объектов.

Очевидно, что выбор разных подмножеств атрибутов обычно приводит к разным классам неразличимости. Например, если атрибут $P=\{P_{1}\}$ выбран только один, мы получаем следующую, гораздо более грубую структуру классов эквивалентности:

{\begin{cases}\{O_{1},O_{2}\}\\\{O_{3},O_{5},O_{7},O_{9},O_{10}\}\\\{O_{4},O_{6},O_{8}\}\end{cases}}

Определение грубого множества

Позволять $X\subseteq \mathbb {U}$ быть целевым набором, который мы хотим представить с помощью подмножества атрибутов $P$ ; то есть нам говорят, что произвольный набор объектов $X$ содержит один класс, и мы хотим выразить этот класс (т. е. это подмножество) с помощью классов эквивалентности, индуцированных подмножеством атрибутов $P$ . В общем, $X$ не может быть выражено точно, поскольку множество может включать и исключать объекты, неотличимые по признакам. $P$ .

Например, рассмотрим целевой набор $X=\{O_{1},O_{2},O_{3},O_{4}\}$ и пусть подмножество атрибутов $P=\{P_{1},P_{2},P_{3},P_{4},P_{5}\}$ , полный доступный набор функций. Набор $X$ не может быть выражено точно, поскольку в $[x]_{P},$ , объекты $\{O_{3},O_{7},O_{10}\}$ неразличимы. Таким образом, невозможно представить какое-либо множество $X$ который включает в себя $O_{3}$ но исключает объекты $O_{7}$ и $O_{10}$ .

Однако поставленная цель $X$ можно аппроксимировать, используя только информацию, содержащуюся в $P$ путем создания $P$ -нижний и $P$ -верхние приближения $X$ :

{\underline {P}}X=\{x\mid [x]_{P}\subseteq X\}

{\overline {P}}X=\{x\mid [x]_{P}\cap X\neq \emptyset \}

Нижнее приближение и положительная область

The $P$ -нижнее приближение , или положительная область , представляет собой объединение всех классов эквивалентности в $[x]_{P}$ которые содержатся в целевом наборе (т. е. являются его подмножествами) – в примере ${\underline {P}}X=\{O_{1},O_{2}\}\cup \{O_{4}\}$ , объединение двух классов эквивалентности в $[x]_{P}$ которые содержатся в целевом наборе. Нижнее приближение – это полный набор объектов в $\mathbb {U} /P$ которые могут быть положительно (т.е. однозначно) классифицированы как принадлежащие к целевому набору $X$ .

Верхнее приближение и отрицательная область

The $P$ -верхнее приближение – это объединение всех классов эквивалентности в $[x]_{P}$ которые имеют непустое пересечение с целевым набором – в примере ${\overline {P}}X=\{O_{1},O_{2}\}\cup \{O_{4}\}\cup \{O_{3},O_{7},O_{10}\}$ , объединение трех классов эквивалентности в $[x]_{P}$ которые имеют непустое пересечение с целевым набором. Верхнее приближение – это полный набор объектов, которые в $\mathbb {U} /P$ которые не могут быть положительно (т. е. однозначно) классифицированы как принадлежащие к дополнению ( ${\overline {X}}$ ) целевого набора $X$ . Другими словами, верхнее приближение — это полный набор объектов, которые, возможно, являются членами целевого набора. $X$ .

Набор $\mathbb {U} -{\overline {P}}X$ следовательно, представляет собой отрицательную область , содержащую набор объектов, которые можно определенно исключить как членов целевого набора.

Пограничный регион

Граничная область , заданная разностью наборов ${\overline {P}}X-{\underline {P}}X$ , состоит из тех объектов, которые нельзя ни включить, ни исключить как членов целевого набора. $X$ .

Таким образом, нижнее приближение целевого набора — это консервативное приближение, состоящее только из тех объектов, которые можно с уверенностью идентифицировать как члены набора. (Эти объекты не имеют неразличимых «клонов», исключенных из целевого набора.) Верхнее приближение — это либеральное приближение, которое включает все объекты, которые могут быть членами целевого набора. (Некоторые объекты в верхнем приближении могут не входить в целевое множество.) С точки зрения $\mathbb {U} /P$ , нижнее приближение содержит объекты, которые являются членами целевого набора с уверенностью (вероятность = 1), а верхнее приближение содержит объекты, которые являются членами целевого набора с ненулевой вероятностью (вероятность > 0).

Грубый набор

Кортеж $\langle {\underline {P}}X,{\overline {P}}X\rangle$ составленное из нижнего и верхнего приближений, называется грубым множеством ; таким образом, приблизительный набор состоит из двух четких наборов, один из которых представляет нижнюю границу целевого набора. $X$ , а другой представляет верхнюю границу целевого набора $X$ .

Точность множества грубого представления $X$ может быть дано (Pawlak 1991) следующим образом:

\alpha _{P}(X)={\frac {\left|{\underline {P}}X\right|}{\left|{\overline {P}}X\right|}}

То есть точность грубого представления множества $X$ , $\alpha _{P}(X)$ , $0\leq \alpha _{P}(X)\leq 1$ , — отношение числа объектов, которые можно положительно поместить в $X$ количеству объектов, которые можно разместить в $X$ – это дает представление о том, насколько близко приблизительный набор приближен к целевому набору. Очевидно, что когда верхнее и нижнее приближения равны (т.е. граничная область пуста), то $\alpha _{P}(X)=1$ , и приближение идеальное; с другой стороны, когда нижнее приближение пусто, точность равна нулю (независимо от размера верхнего приближения).

Объективный анализ

Грубая теория множеств — один из многих методов, которые можно использовать для анализа неопределенных (в том числе расплывчатых) систем, хотя он менее распространен, чем более традиционные методы вероятности , статистики , энтропии и теории Демпстера-Шафера . Однако ключевое отличие и уникальная сила использования классической грубой теории множеств заключается в том, что она обеспечивает объективную форму анализа (Павлак и др., 1995). В отличие от других методов, подобных приведенным выше, классический грубый анализ множества не требует дополнительной информации, внешних параметров, моделей, функций, оценок или субъективных интерпретаций для определения принадлежности множества – вместо этого он использует только информацию, представленную в данных данных (Düntsch and Gediga 1995). ). Более поздние адаптации грубой теории множеств, такие как теория доминирования, теория принятия решений и нечеткие грубые множества, привнесли в анализ больше субъективности.

Определимость

В общем, верхнее и нижнее приближения не равны; в таких случаях мы говорим, что целевой набор $X$ невозможно определить или грубо определить по набору атрибутов $P$ . Когда верхнее и нижнее приближения равны (т. е. граница пуста), ${\overline {P}}X={\underline {P}}X$ , то целевой набор $X$ определяется атрибутов по набору $P$ . Можно выделить следующие частные случаи неопределимости:

Набор $X$ неопределима внутренне , если ${\underline {P}}X=\emptyset$ и ${\overline {P}}X\neq \mathbb {U}$ . Это означает, что при наборе атрибутов $P$ , нет объектов , в отношении которых мы можем быть уверены, что они принадлежат целевому набору $X$ , но есть объекты , которые мы можем окончательно исключить из множества $X$ .
Набор $X$ , внешне неопределима если ${\underline {P}}X\neq \emptyset$ и ${\overline {P}}X=\mathbb {U}$ . Это означает, что при наборе атрибутов $P$ , есть объекты , которые, как мы можем быть уверены, принадлежат целевому набору $X$ , но нет объектов , которые мы могли бы окончательно исключить из множества $X$ .
Набор $X$ совершенно неопределимо, если ${\underline {P}}X=\emptyset$ и ${\overline {P}}X=\mathbb {U}$ . Это означает, что при наборе атрибутов $P$ , нет объектов , в отношении которых мы можем быть уверены, что они принадлежат целевому набору $X$ , и нет объектов , которые мы могли бы окончательно исключить из множества $X$ . Таким образом, по набору атрибутов $P$ , мы не можем решить, является ли какой-либо объект членом $X$ .

Сокращение и ядро

Интересный вопрос заключается в том, существуют ли в информационной системе (таблице атрибутов-значений) атрибуты, которые более важны для знаний, представленных в структуре классов эквивалентности, чем другие атрибуты. Часто мы задаемся вопросом, существует ли подмножество атрибутов, которые сами по себе могут полностью охарактеризовать знания в базе данных; такой набор атрибутов называется сокращением .

Формально сокращение — это подмножество атрибутов. $\mathrm {RED} \subseteq P$ такой, что

$[x]_{\mathrm {RED} }$ = $[x]_{P}$ , то есть классы эквивалентности, индуцированные сокращенным набором атрибутов $\mathrm {RED}$ такие же, как и структура класса эквивалентности, индуцированная полным набором атрибутов. $P$ .
набор атрибутов $\mathrm {RED}$ является минимальным в том смысле, что $[x]_{(\mathrm {RED} -\{a\})}\neq [x]_{P}$ для любого атрибута $a\in \mathrm {RED}$ ; другими словами, ни один атрибут не может быть удален из набора $\mathrm {RED}$ без изменения классов эквивалентности $[x]_{P}$ .

Сокращение можно рассматривать как достаточный набор функций – то есть достаточный для представления структуры категории. В приведенной выше таблице примера набор атрибутов $\{P_{3},P_{4},P_{5}\}$ является сокращением – информационная система, спроецированная только на эти атрибуты, обладает той же структурой классов эквивалентности, что и полная совокупность атрибутов:

{\begin{cases}\{O_{1},O_{2}\}\\\{O_{3},O_{7},O_{10}\}\\\{O_{4}\}\\\{O_{5}\}\\\{O_{6}\}\\\{O_{8}\}\\\{O_{9}\}\end{cases}}

Набор атрибутов $\{P_{3},P_{4},P_{5}\}$ является сокращением, поскольку устранение любого из этих атрибутов приводит к коллапсу структуры класса эквивалентности, в результате чего $[x]_{\mathrm {RED} }\neq [x]_{P}$ .

Редукция информационной системы не является уникальной : может существовать множество подмножеств атрибутов, которые сохраняют структуру классов эквивалентности (т. е. знания), выраженные в информационной системе. В приведенном выше примере информационной системы еще одно сокращение: $\{P_{1},P_{2},P_{5}\}$ , создавая ту же структуру классов эквивалентности, что и $[x]_{P}$ .

Набор атрибутов, общий для всех редуктов, называется ядром : ядро — это набор атрибутов, которым обладает каждый редукт, и, следовательно, состоит из атрибутов, которые нельзя удалить из информационной системы, не вызывая коллапса класса эквивалентности. структура. Ядро можно рассматривать как набор необходимых атрибутов, то есть необходимых для представления структуры категории. В примере единственным таким атрибутом является $\{P_{5}\}$ ; любой из других атрибутов может быть удален отдельно, не нарушая структуру классов эквивалентности, и, следовательно, все они необязательны . Однако удаление $\{P_{5}\}$ само по себе меняет структуру классов эквивалентности и, таким образом, $\{P_{5}\}$ является непременным атрибутом этой информационной системы, а значит, и ее ядром.

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

Зависимость атрибута

Одним из наиболее важных аспектов анализа базы данных или сбора данных является обнаружение зависимостей атрибутов; то есть мы хотим выяснить, какие переменные тесно связаны с какими другими переменными. Как правило, именно эти прочные взаимосвязи требуют дальнейшего изучения и в конечном итоге будут полезны в прогнозном моделировании.

В грубой теории множеств понятие зависимости определяется очень просто. Возьмем два (непересекающихся) набора атрибутов, набор $P$ и установить $Q$ и выяснить, какая степень зависимости существует между ними. Каждый набор атрибутов порождает структуру классов эквивалентности (неразличимость), классы эквивалентности, индуцированные $P$ данный $[x]_{P}$ и классы эквивалентности, индуцированные $Q$ данный $[x]_{Q}$ .

Позволять $[x]_{Q}=\{Q_{1},Q_{2},Q_{3},\dots ,Q_{N}\}$ , где $Q_{i}$ — заданный класс эквивалентности из структуры классов эквивалентности, индуцированной набором атрибутов $Q$ . Тогда зависимость набора атрибутов $Q$ по набору атрибутов $P$ , $\gamma _{P}(Q)$ , определяется

\gamma _{P}(Q)={\frac {\sum _{i=1}^{N}\left|{\underline {P}}Q_{i}\right|}{\left|\mathbb {U} \right|}}\leq 1

То есть для каждого класса эквивалентности $Q_{i}$ в $[x]_{Q}$ , мы суммируем размер его нижнего приближения по атрибутам в $P$ , то есть, ${\underline {P}}Q_{i}$ . Это приближение (как и выше, для произвольного набора $X$ ) — количество объектов, которые по набору атрибутов $P$ может быть положительно идентифицирован как принадлежащий к целевому набору $Q_{i}$ . Добавлено во все классы эквивалентности в $[x]_{Q}$ , числитель выше представляет общее количество объектов, которые – на основе набора атрибутов $P$ – могут быть положительно категоризированы в соответствии с классификацией, вызванной атрибутами $Q$ . Таким образом, коэффициент зависимости выражает долю (во всей вселенной) таких классифицируемых объектов. Зависимость $\gamma _{P}(Q)$ «можно интерпретировать как долю таких объектов в информационной системе, для которой достаточно знать значения атрибутов в $P$ определить значения атрибутов в $Q$ ".

Другой, интуитивный способ рассмотреть зависимость — взять разбиение, вызванное $Q$ как целевой класс $C$ и рассмотрим $P$ в качестве набора атрибутов, который мы хотим использовать для «реконструкции» целевого класса $C$ . Если $P$ можно полностью реконструировать $C$ , затем $Q$ полностью зависит от $P$ ; если $P$ приводит к плохой и, возможно, случайной реконструкции $C$ , затем $Q$ не зависит от $P$ совсем.

Таким образом, эта мера зависимости выражает степень функциональной (т. е. детерминированной) зависимости набора атрибутов. $Q$ по набору атрибутов $P$ ; оно не симметрично. Связь этого понятия зависимости атрибута с более традиционными теоретико-информационными (т.е. энтропийными) понятиями атрибутной зависимости обсуждалась в ряде источников (например, Pawlak, Wong & Ziarko 1988; Yao & Yao 2002; Wong, Ziarko , & Ye 1986, Quafafou & Boussouf 2000).

Извлечение правил

Все представленные выше представления категорий носят экстенсиональный характер; то есть категория или сложный класс представляет собой просто сумму всех своих членов. Таким образом, представлять категорию — это просто иметь возможность перечислить или идентифицировать все объекты, принадлежащие к этой категории. Однако экстенсиональные представления категорий имеют очень ограниченное практическое применение, поскольку они не дают информации для принятия решения о том, являются ли новые (никогда ранее не встречавшиеся) объекты членами категории.

Обычно желательно намеренное описание категории, представление категории на основе набора правил , описывающих область действия категории. Выбор таких правил не уникален, и в этом заключается проблема индуктивного смещения . см. в разделе «Пространство версий» и «Выбор модели» Дополнительные сведения об этой проблеме .

Существует несколько методов извлечения правил. Мы начнем с процедуры извлечения правил, основанной на Ziarko & Shan (1995).

Матрицы решений

Допустим, мы хотим найти минимальный набор непротиворечивых правил ( логических выводов ), характеризующих нашу выборочную систему. Для набора условия атрибутов ${\mathcal {P}}=\{P_{1},P_{2},P_{3},\dots ,P_{n}\}$ и атрибут решения $Q,Q\notin {\mathcal {P}}$ , эти правила должны иметь вид $P_{i}^{a}P_{j}^{b}\dots P_{k}^{c}\to Q^{d}$ , или, прописано,

(P_{i}=a)\land (P_{j}=b)\land \dots \land (P_{k}=c)\to (Q=d)

где $\{a,b,c,\dots \}$ являются законными значениями из областей соответствующих атрибутов. Это типичная форма ассоциативных правил , и количество элементов в $\mathbb {U}$ которые соответствуют условию/антецеденту, называется поддержкой правила. Метод извлечения таких правил, приведенный в Ziarko & Shan (1995), заключается в формировании матрицы решений, соответствующей каждому отдельному значению. $d$ атрибута решения $Q$ . Неформально, матрица решений для значения $d$ атрибута решения $Q$ перечисляет все пары атрибут-значение, которые различаются между объектами, имеющими $Q=d$ и $Q\neq d$ .

Лучше всего это объяснить на примере (который также позволяет избежать множества обозначений). Рассмотрим приведенную выше таблицу и пусть $P_{4}$ быть переменной решения (т. е. переменной в правой части импликаций) и пусть $\{P_{1},P_{2},P_{3}\}$ — переменные условия (в левой части импликации). Заметим, что переменная решения $P_{4}$ принимает два разных значения, а именно $\{1,2\}$ . Мы рассматриваем каждый случай отдельно.

Сначала мы рассмотрим случай $P_{4}=1$ , и мы разделимся $\mathbb {U}$ в объекты, имеющие $P_{4}=1$ и те, у которых есть $P_{4}\neq 1$ . (Обратите внимание, что объекты с $P_{4}\neq 1$ в данном случае это просто объекты, которые имеют $P_{4}=2$ , но в целом $P_{4}\neq 1$ будет включать все объекты, имеющие какое-либо значение для $P_{4}$ кроме $P_{4}=1$ , причем таких классов объектов может быть несколько (например, имеющих $P_{4}=2,3,4,etc.$ )) При этом объекты, имеющие $P_{4}=1$ являются $\{O_{1},O_{2},O_{3},O_{7},O_{10}\}$ в то время как объекты, имеющие $P_{4}\neq 1$ являются $\{O_{4},O_{5},O_{6},O_{8},O_{9}\}$ . Матрица решений для $P_{4}=1$ перечислены все различия между объектами, имеющими $P_{4}=1$ и те, у кого есть $P_{4}\neq 1$ ; то есть в матрице решений перечислены все различия между $\{O_{1},O_{2},O_{3},O_{7},O_{10}\}$ и $\{O_{4},O_{5},O_{6},O_{8},O_{9}\}$ . Ставим «положительные» объекты ( $P_{4}=1$ ) как строки и «отрицательные» объекты $P_{4}\neq 1$ как столбцы.

Матрица решений для $P_{4}=1$
Объект	$O_{4}$	$O_{5}$	$O_{6}$	$O_{8}$	$O_{9}$
$O_{1}$	$P_{1}^{1},P_{2}^{2},P_{3}^{0}$	$P_{1}^{1},P_{2}^{2}$	$P_{1}^{1},P_{2}^{2},P_{3}^{0}$	$P_{1}^{1},P_{2}^{2},P_{3}^{0}$	$P_{1}^{1},P_{2}^{2}$
$O_{2}$	$P_{1}^{1},P_{2}^{2},P_{3}^{0}$	$P_{1}^{1},P_{2}^{2}$	$P_{1}^{1},P_{2}^{2},P_{3}^{0}$	$P_{1}^{1},P_{2}^{2},P_{3}^{0}$	$P_{1}^{1},P_{2}^{2}$
$O_{3}$	$P_{1}^{2},P_{3}^{0}$	$P_{2}^{0}$	$P_{1}^{2},P_{3}^{0}$	$P_{1}^{2},P_{2}^{0},P_{3}^{0}$	$P_{2}^{0}$
$O_{7}$	$P_{1}^{2},P_{3}^{0}$	$P_{2}^{0}$	$P_{1}^{2},P_{3}^{0}$	$P_{1}^{2},P_{2}^{0},P_{3}^{0}$	$P_{2}^{0}$
$O_{10}$	$P_{1}^{2},P_{3}^{0}$	$P_{2}^{0}$	$P_{1}^{2},P_{3}^{0}$	$P_{1}^{2},P_{2}^{0},P_{3}^{0}$	$P_{2}^{0}$

Чтобы прочитать эту матрицу решений, посмотрите, например, на пересечение строки $O_{3}$ и столбец $O_{6}$ , показывая $P_{1}^{2},P_{3}^{0}$ в клетке. Это означает, что относительно ценности решения $P_{4}=1$ , объект $O_{3}$ отличается от объекта $O_{6}$ по атрибутам $P_{1}$ и $P_{3}$ и конкретные значения этих атрибутов для положительного объекта $O_{3}$ являются $P_{1}=2$ и $P_{3}=0$ . Это говорит нам о том, что правильная классификация $O_{3}$ как принадлежность к классу решений $P_{4}=1$ опирается на атрибуты $P_{1}$ и $P_{3}$ ; хотя тот или иной атрибут может быть необязательным, мы знаем, что по крайней мере один из этих атрибутов необязателен .

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

{\begin{cases}(P_{1}^{1}\lor P_{2}^{2}\lor P_{3}^{0})\land (P_{1}^{1}\lor P_{2}^{2})\land (P_{1}^{1}\lor P_{2}^{2}\lor P_{3}^{0})\land (P_{1}^{1}\lor P_{2}^{2}\lor P_{3}^{0})\land (P_{1}^{1}\lor P_{2}^{2})\\(P_{1}^{1}\lor P_{2}^{2}\lor P_{3}^{0})\land (P_{1}^{1}\lor P_{2}^{2})\land (P_{1}^{1}\lor P_{2}^{2}\lor P_{3}^{0})\land (P_{1}^{1}\lor P_{2}^{2}\lor P_{3}^{0})\land (P_{1}^{1}\lor P_{2}^{2})\\(P_{1}^{2}\lor P_{3}^{0})\land (P_{2}^{0})\land (P_{1}^{2}\lor P_{3}^{0})\land (P_{1}^{2}\lor P_{2}^{0}\lor P_{3}^{0})\land (P_{2}^{0})\\(P_{1}^{2}\lor P_{3}^{0})\land (P_{2}^{0})\land (P_{1}^{2}\lor P_{3}^{0})\land (P_{1}^{2}\lor P_{2}^{0}\lor P_{3}^{0})\land (P_{2}^{0})\\(P_{1}^{2}\lor P_{3}^{0})\land (P_{2}^{0})\land (P_{1}^{2}\lor P_{3}^{0})\land (P_{1}^{2}\lor P_{2}^{0}\lor P_{3}^{0})\land (P_{2}^{0})\end{cases}}

Каждое утверждение здесь, по сути, является весьма конкретным (возможно, слишком конкретным) правилом, регулирующим членство в классе. $P_{4}=1$ соответствующего объекта. Например, последний оператор, соответствующий объекту $O_{10}$ , утверждает, что должны быть выполнены все следующие условия:

Или $P_{1}$ должно иметь значение 2, или $P_{3}$ должно иметь значение 0 или оба.
$P_{2}$ должно иметь значение 0.
Или $P_{1}$ должно иметь значение 2, или $P_{3}$ должно иметь значение 0 или оба.
Или $P_{1}$ должно иметь значение 2, или $P_{2}$ должно иметь значение 0 или $P_{3}$ должно иметь значение 0 или любую их комбинацию.
$P_{2}$ должно иметь значение 0.

Понятно, что здесь имеется большая избыточность, и следующим шагом будет упрощение с использованием традиционной булевой алгебры . Заявление $(P_{1}^{1}\lor P_{2}^{2}\lor P_{3}^{0})\land (P_{1}^{1}\lor P_{2}^{2})\land (P_{1}^{1}\lor P_{2}^{2}\lor P_{3}^{0})\land (P_{1}^{1}\lor P_{2}^{2}\lor P_{3}^{0})\land (P_{1}^{1}\lor P_{2}^{2})$ соответствующие объектам $\{O_{1},O_{2}\}$ упрощается до $P_{1}^{1}\lor P_{2}^{2}$ , что дает импликацию

(P_{1}=1)\lor (P_{2}=2)\to (P_{4}=1)

Аналогично, заявление $(P_{1}^{2}\lor P_{3}^{0})\land (P_{2}^{0})\land (P_{1}^{2}\lor P_{3}^{0})\land (P_{1}^{2}\lor P_{2}^{0}\lor P_{3}^{0})\land (P_{2}^{0})$ соответствующие объектам $\{O_{3},O_{7},O_{10}\}$ упрощается до $P_{1}^{2}P_{2}^{0}\lor P_{3}^{0}P_{2}^{0}$ . Это дает нам импликацию

(P_{1}=2\land P_{2}=0)\lor (P_{3}=0\land P_{2}=0)\to (P_{4}=1)

Вышеупомянутые последствия также можно записать в виде следующего набора правил:

{\begin{cases}(P_{1}=1)\to (P_{4}=1)\\(P_{2}=2)\to (P_{4}=1)\\(P_{1}=2)\land (P_{2}=0)\to (P_{4}=1)\\(P_{3}=0)\land (P_{2}=0)\to (P_{4}=1)\end{cases}}

Можно отметить, что каждое из первых двух правил имеет поддержку 1 (т.е. антецедент соответствует двум объектам), а каждое из последних двух правил имеет поддержку 2. Чтобы закончить написание набора правил для этой системы знаний, ту же процедуру, что и выше (начиная с написания новой матрицы решений), следует выполнить для случая $P_{4}=2$ , что дает новый набор последствий для этого значения решения (т. е. набор последствий с $P_{4}=2$ как следствие). В общем, процедура повторяется для каждого возможного значения переменной решения.

Система введения правил LERS

Система данных LERS (Обучение на примерах, основанных на грубых наборах) Гржимала-Буссе (1997) может создавать правила на основе противоречивых данных, т. е. данных с конфликтующими объектами. Два объекта конфликтны, когда они характеризуются одинаковыми значениями всех признаков, но принадлежат разным понятиям (классам). LERS использует грубую теорию множеств для вычисления нижних и верхних приближений для концепций, конфликтующих с другими концепциями.

Правила, индуцированные из нижнего приближения понятия, заведомо описывают это понятие, поэтому такие правила называются определенными . С другой стороны, правила, индуцированные из верхнего приближения понятия, описывают понятие возможно , поэтому эти правила называются возможными . Для индукции правил LERS использует три алгоритма: LEM1, LEM2 и IRIM.

Алгоритм LEM2 LERS часто используется для индукции правил и применяется не только в LERS, но и в других системах, например, в RSES (Bazan et al. (2004). LEM2 исследует пространство поиска пар атрибут-значение . Его входные данные набор данных является нижним или верхним приближением понятия, поэтому его набор входных данных всегда согласован. В общем, LEM2 вычисляет локальное покрытие, а затем преобразует его в набор правил. Мы приведем несколько определений для описания алгоритма LEM2.

Алгоритм LEM2 основан на идее блока пары атрибут-значение. Позволять $X$ быть непустым нижним или верхним приближением понятия, представленного парой значений решения. $(d,w)$ . Набор $X$ зависит от набора $T$ пар атрибут-значение $t=(a,v)$ тогда и только тогда, когда

\emptyset \neq [T]=\bigcap _{t\in T}[t]\subseteq X.

Набор $T$ представляет собой минимальный комплекс $X$ тогда и только тогда, когда $X$ зависит от $T$ и нет подходящего подмножества $S$ из $T$ существует такое, что $X$ зависит от $S$ . Позволять $\mathbb {T}$ быть непустой совокупностью непустых наборов пар атрибут-значение. Затем $\mathbb {T}$ является локальным покрытием $X$ тогда и только тогда, когда выполняются следующие три условия:

каждый участник $T$ из $\mathbb {T}$ представляет собой минимальный комплекс $X$ ,

\bigcup _{t\in \mathbb {T} }[T]=X,

\mathbb {T}

является минимальным, т.е.

\mathbb {T}

имеет минимально возможное число членов.

Для нашей примерной информационной системы LEM2 будет вводить следующие правила:

{\begin{cases}(P_{1},1)\to (P_{4},1)\\(P_{5},0)\to (P_{4},1)\\(P_{1},0)\to (P_{4},2)\\(P_{2},1)\to (P_{4},2)\end{cases}}

Другие методы изучения правил можно найти, например, у Pawlak (1991), Stefanowski (1998), Bazan et al. (2004) и др.

Неполные данные

Грубая теория множеств полезна для вывода правил из неполных наборов данных. Используя этот подход, мы можем различать три типа отсутствующих значений атрибутов: потерянные значения (значения, которые были записаны, но в настоящее время недоступны), значения концепции атрибута (эти отсутствующие значения атрибута могут быть заменены любым значением атрибута, ограниченным той же концепцией). и условия «безразлично» (исходные значения не имели значения). Понятие класс ( ) — это совокупность всех объектов , классифицированных (или диагностируемых) одинаково.

Были тщательно изучены два специальных набора данных с отсутствующими значениями атрибутов: в первом случае все отсутствующие значения атрибутов были потеряны (Стефановский и Цукиас, 2001), во втором случае все отсутствующие значения атрибутов были условиями «безразличия» (Крышкевич, 1999).

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

Приложения

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

История

Идея грубого набора была предложена Павляком (1981) как новый математический инструмент для работы с расплывчатыми понятиями. Комер, Гржимала-Буссе, Ивински, Ниеминен, Новотный, Павляк, Обтулович и Помыкала изучали алгебраические свойства грубых множеств. Различные алгебраические семантики были разработаны П. Пальяни, И. Данчем, М. К. Чакраборти, М. Банерджи и А. Мани; они были распространены на более обобщенные грубые множества, в частности, Д. Каттанео и А. Мани. Грубые наборы могут использоваться для представления двусмысленности , неопределенности и общей неопределенности .

Расширения и обобщения

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

Три заметных расширения классических грубых множеств:

Подход грубого множества, основанный на доминировании (DRSA), является расширением теории грубых множеств для многокритериального анализа решений (MCDA), представленной Греко, Матараццо и Словински (2001). Основным изменением в этом расширении классических грубых множеств является замена отношения неразличимости отношением доминирования , которое позволяет формализму иметь дело с несоответствиями, типичными при рассмотрении критериев и классов решений, упорядоченных по предпочтениям.
Грубые множества теории принятия решений (DTRS) — это вероятностное расширение грубой теории множеств, введенное Яо, Вонгом и Линграсом (1990). Он использует байесовскую процедуру принятия решений для принятия решений с минимальным риском. Элементы включаются в нижнее и верхнее приближения в зависимости от того, превышает ли их условная вероятность пороговые значения. $\textstyle \alpha$ и $\textstyle \beta$ . Эти верхние и нижние пороги определяют включение областей для элементов. Эта модель уникальна и мощна, поскольку сами пороговые значения рассчитываются на основе набора из шести функций потерь, представляющих классификационные риски.
Теоретико-игровые грубые множества (GTRS) — это основанное на теории игр расширение грубого множества, которое было представлено Гербертом и Яо (2011). Он использует теоретико-игровую среду для оптимизации определенных критериев классификации или принятия решений на основе грубых наборов с целью получения эффективных размеров регионов.

Грубое членство

Грубые множества также можно определить в качестве обобщения, используя грубую функцию принадлежности вместо объективной аппроксимации. Грубая функция принадлежности выражает условную вероятность того, что $x$ принадлежит $X$ данный $\textstyle \mathbb {R}$ . Это можно интерпретировать как степень, $x$ принадлежит $X$ в плане информации о $x$ выраженный $\textstyle \mathbb {R}$ .

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

Другие обобщения

Было введено, изучено и применено для решения задач несколько обобщений грубых множеств. Вот некоторые из этих обобщений:

грубые мультисеты (Гржимала-Буссе, 1987)
нечеткие грубые множества расширяют концепцию грубых множеств за счет использования классов нечеткой эквивалентности (Накамура, 1988).
Альфа-грубая теория множеств (α-RST) - обобщение грубой теории множеств, позволяющее аппроксимировать с использованием нечетких концепций (Quafafou, 2000).
интуиционистские нечеткие грубые множества (Корнелис, Де Кок и Керре, 2003)
обобщенные грубые нечеткие множества (Фэн, 2010)
грубые интуиционистские нечеткие множества (Томас и Наир, 2011)
мягкие грубые нечеткие множества и мягкие нечеткие грубые множества (Мэн, Чжан и Цинь, 2011)
составные черновые наборы (Чжан, Ли и Чен, 2014 г.)

См. также

Ссылки

Павляк, Здислав (1982). «Грубые наборы». Международный журнал параллельного программирования . 11 (5): 341–356. дои : 10.1007/BF01001956 . S2CID 9240608 .
Базан, Ян; Щука, Марцин; Война, Аркадиуш; Войнарски, Марцин (2004). «Об эволюции системы исследования грубых наборов». Грубые множества и современные тенденции в области вычислений . Конспекты лекций по информатике. Том. 3066. стр. 592–601. CiteSeerX 10.1.1.60.3957 . дои : 10.1007/978-3-540-25929-9_73 . ISBN 978-3-540-22117-3 .
Дюбуа, Д.; Прад, Х. (1990). «Грубые нечеткие множества и нечеткие грубые множества». Международный журнал общих систем . 17 (2–3): 191–209. дои : 10.1080/03081079008935107 .
Герберт, JP; Яо, Джей Ти (2011). «Теоретико-игровые грубые множества». Фундамента информатики . 108 (3–4): 267–286. дои : 10.3233/FI-2011-423 .
Греко, Сальваторе; Матараццо, Бенедетто; Словинский, Роман (2001). «Грубая теория множеств для многокритериального анализа решений». Европейский журнал операционных исследований . 129 (1): 1–47. дои : 10.1016/S0377-2217(00)00167-3 . S2CID 12045346 .
Гржимала-Буссе, Ежи (1997). «Новая версия системы индукции правил LERS». Фундамента информатики . 31 : 27–39. дои : 10.3233/FI-1997-3113 .
Гржимала-Буссе, Ежи; Гржимала-Буссе, Витольд (2007). «Экспериментальное сравнение трех грубых подходов к отсутствующим значениям атрибутов». Транзакции по грубым наборам, вып. VI . Конспекты лекций по информатике. стр. 31–50. дои : 10.1007/978-3-540-71200-8_3 . ISBN 978-3-540-71198-8 .
Крышкевич, Мажена (1999). «Правила в неполных системах». Информационные науки . 113 (3–4): 271–292. дои : 10.1016/S0020-0255(98)10065-8 .
Павляк, Отчет об исследовании грубых множеств Здзислава PAS 431, Институт компьютерных наук Польской академии наук (1981)
Павляк, Здислав; Вонг, СКМ; Зярко, Войцех (1988). «Грубые множества: вероятностный и детерминистический подход». Международный журнал человеко-машинных исследований . 29 : 81–95. дои : 10.1016/S0020-7373(88)80032-4 .
Павляк, Здислав (1991). Грубые множества: теоретические аспекты рассуждений о данных . Дордрехт: Академическое издательство Kluwer. ISBN 978-0-7923-1472-1 .
Слезак, Доминик; Вроблевски, Якуб; Иствуд, Виктория; Сынак, Петр (2008). «Brighthouse: хранилище аналитических данных для специальных запросов» (PDF) . Труды Фонда VLDB . 1 (2): 1337–1345. дои : 10.14778/1454159.1454174 .
Стефановский, Ежи (1998). «О подходах к индукции решающих правил, основанных на грубых наборах». В Полковском, Лех; Сковрон, Анджей (ред.). Грубые наборы в открытии знаний 1: Методология и приложения . Гейдельберг: Physica-Verlag. стр. 500–529.
Стефановский, Ежи; Цукиас, Алексис (2001). «Неполные информационные таблицы и приблизительная классификация» . Вычислительный интеллект . 17 (3): 545–566. дои : 10.1111/0824-7935.00162 . S2CID 22795201 .
Вонг, СКМ; Жярко, Войцех; Йе, Р. Ли (1986). «Сравнение приблизительных и статистических методов индуктивного обучения». Международный журнал человеко-машинных исследований . 24 : 53–72. дои : 10.1016/S0020-7373(86)80033-5 .
Яо, Джей Ти; Яо, ГГ (2002). «Введение правил классификации с помощью гранулярных вычислений». Материалы Третьей Международной конференции по грубым множествам и современным тенденциям в области вычислений (TSCTC'02) . Лондон, Великобритания: Springer-Verlag. стр. 331–338. дои : 10.1007/3-540-45813-1_43 .
Жярко, Войцех (1998). «Грубые наборы как методология интеллектуального анализа данных». Грубые наборы в открытии знаний 1: Методология и приложения . Гейдельберг: Physica-Verlag. стр. 554–576.
Жярко, Войцех; Шан, Нин (1995). «Обнаружение связей, зависимостей и правил атрибутов с помощью приблизительных наборов». Материалы 28-й ежегодной Гавайской международной конференции по системным наукам (HICSS'95) . Гавайи. стр. 293–299.
Павляк, Здислав (1999). «Правила принятия решений, правило Байеса и грубые множества». Новое направление в грубых наборах, интеллектуальном анализе данных и гранулярно-мягких вычислениях : 1–9. дои : 10.1007/978-3-540-48061-7_1 .
Павляк, Здислав (1981). Непростые отношения, сообщает . Том. 435(3):205–218}. Институт компьютерных наук.
Орловская, Э. (1987). «Рассуждения о смутных понятиях». Вестник Польской академии наук . 35 : 643–652.
Полковски, Л. (2002). «Грубые множества: Математические основы». Достижения в области мягких вычислений .
Скоурон, А. (1996). «Грубые декорации и расплывчатые понятия». Фундамента информатика : 417–431.
Бургин М. (1990). Теория именованных множеств как фундаментальная основа математики, Структуры в математических теориях: отчеты международного симпозиума в Сан-Себастьяне, 25–29 сентября 1990 г. ( http://www.blogg.org/blog-30140-date-2005- 10-26.html )
Бургин, М. (2004). Единые основы математики, Препринт математики LO/0403186, стр. 39. (электронное издание: https://arxiv.org/ftp/math/papers/0403/0403186.pdf )
Бургин, М. (2011), Теория именованных множеств, Развитие математических исследований, Nova Science Pub Inc., ISBN 978-1-61122-788-8
Корнелис К., Де Кок М. и Керре Э. (2003) Интуиционистские нечеткие грубые множества: на перекрестке несовершенных знаний, Expert Systems, 20:5, стр. 260–270.
Дюнч И. и Гедига Г. (1995) Грубый анализ зависимостей в оценочных исследованиях – применение при изучении повторных сердечных приступов. Университет Ольстера, Отчеты об исследованиях в области информатики № 10
Фэн Ф. (2010). Обобщенные грубые нечеткие множества на основе мягких множеств, Soft Computing, 14:9, стр. 899–911.
Гржимала-Буссе, Дж. (1987). Обучение на примерах, основанных на грубых мультимножествах, в Трудах 2-го Международного симпозиума по методологиям интеллектуальных систем, стр. 325–332. Шарлотт, Северная Каролина, США
Мэн Д., Чжан Х. и Цинь К. (2011). Мягкие грубые нечеткие множества и мягкие нечеткие грубые множества, Компьютеры и математика с приложениями, 62:12, стр. 4635–4645.
Куафафу М. (2000). α-RST: обобщение грубой теории множеств, Information Sciences, 124:1–4, стр. 301–316.
Куафафу М. и Буссуф М. (2000). Выбор элементов на основе обобщенных черновых наборов. Журнал «Интеллектуальный анализ данных», 4:1, стр. 3 – 17.
Накамура, А. (1988) Нечеткие грубые множества, «Заметки о многозначной логике в Японии», 9:1, стр. 1–8.
Павляк З., Гржимала-Буссе Дж., Словински Р. Зиарко В. (1995). Грубые наборы. Сообщения ACM, 38:11, стр. 88–95.
Томас К. и Наир Л. (2011). Грубые интуиционистские нечеткие множества в решетке, Международный математический форум, 6:27, стр. 1327–1335.
Чжан Дж., Ли Т., Чэнь Х. (2014). Составные грубые наборы для динамического анализа данных, Информационные науки, 257, стр. 81–100.
Чжан Дж., Вонг Дж.С., Пан Ю., Ли Т. (2015). Параллельный матричный метод для вычисления приближений в неполных информационных системах, IEEE Transactions on Knowledge and Data Engineering, 27(2): 326-339.
Чен Х., Ли Т., Луо К., Хорнг С.Дж., Ван Г. (2015). Теоретико-решительный грубый подход для динамического анализа данных. Транзакции IEEE в нечетких системах, 23 (6): 1958–1970.
Чен Х., Ли Т., Луо К., Хорнг С.Дж., Ван Г. (2014). Грубый метод на основе наборов для обновления правил принятия решений по уточнению и уточнению значений атрибутов, IEEE Transactions on Knowledge and Data Engineering, 26(12): 2886-2899.
Чен Х., Ли Т., Руан Д., Линь Дж., Ху К. (2013)Поэтапный подход на основе грубого набора для обновления аппроксимаций в условиях динамического обслуживания. IEEE Transactions on Knowledge and Data Engineering, 25(2): 274-284.

Дальнейшее чтение

Джанпьеро Каттанео и Давиде Чиуччи, «Алгебры Гейтинга Вайсберга как абстрактная среда, связывающая нечеткие и грубые множества» в JJ Alpigini et al. (Ред.): RSCTC 2002, LNAI 2475, стр. 77–84, 2002 г. дои : 10.1007/3-540-45813-1_10

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