Алгоритм параллельной предварительной обработки таблиц, основанный на теории приближенных множеств

Информационной системой называется пара, где — непустое конечное множество объектов, названное универсумом и — непустое конечное множество атрибутов такое, что: для каждого. Множество называется множеством значений. Система решений (таблица решений) — это информационная система вида:

.

где — атрибут решения. Элементы называются атрибутами условия.

С каждым множеством атрибутов ассоциировано отношение эквивалентности, называемое отношением — неразличимости:

.

Обозначим:

.

Через обозначим классы эквивалентности отношения .

Обобщенное решение в — это функция:

.

Таблица решений называется непротиворечивой (детерминированной), если для любого, иначе называется противоречивой (недетерминированной).

Представим формальное определение обобщенной задачи разбиения значений атрибутов [Akchurina et al., 2004, Vagin et al., 2004].

Пусть.

— таблица решений, где для. Любая функция называется разбиением. Ранг определяется как.

.

Любое семейство разбиений определяет из новую систему решений.

.

для любого объекта,. Семейство разбиений — непротиворечиво, если, где и — обобщенные решения и соответственно. — непротиворечивое семейство разбиений называетсяоптимальным, если для любогонепротиворечивого семейства разбиений. Обобщенная задача разбиения атрибутов состоит в том, чтобы найти — оптимальное семейство разбиений и получить таблицу решений .

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

Пусть.

— система решений, где:

и .

Тройка называется цепочкой, где для и .

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

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

Для подсчета таких пар объектов используем понятие — относительной матрицы различимости для цепочек, основанное на понятии — относительной матрицы различимости.

— относительной матрицей различимости для цепочек будем называть симметричную матрицу с элементами:

.

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

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

Шаг 1. Производим наивную дискретизацию, которая заключается в разделении непрерывных областей значений атрибутов на заданное число равных интервалов.

Шаг 2. Каждое отсутствующее значение заменяем на уникальное значение. Обозначим — множество уникальных значений атрибута, .

Шаг 3. Для каждого процесса из.

Формируем матрицу изого столбца — относительной матрицы для цепочек.

Шаг 4. Находим наиболее часто встречающуюся цепочку в элементах .

Шаг 5. Цепочка добавляется к множеству цепочек .

Шаг 6. Все ячейки, содержащие заменяем пустыми множествами.

Шаг 7. Если все ячейки матрицы являются пустыми множествами, то переходим к шагу 4, иначе к шагу 8.

Шаг 8. Формируем множество цепочек из наиболее часто встречающихся цепочек в .

Шаг 9. Для каждого процесса из .

Проверяем, различает ли все объекты из различных классов решений при помощи матриц .

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

Шаг 10. определяет из новую систему решений:

.

для любого объекта, .

Шаг 11. Разделяем числовые атрибуты на интервалы. Шкалированые качественные атрибуты на подмножества.