Нечеткие гибридные системы в задачах интеллектуального анализа данных

Размещено на http://www.allbest.ru/

Нечеткие гибридные системы в задачах интеллектуального анализа данных

Введение

нечеткий реляционный сервер гибридный

В настоящее время применение методов анализа данных часто бывает затруднено тем, что часто для конкретной задачи из какой либо предметной области выборка характеризуется не числовым характером атрибутов. В частности, в макроэкономических, социологических, маркетинговых, медицинских базах данных широко используется лингвистическая форма представления данных. Для оперирования подобными данными необходимо организовать среду хранения нечетких атрибутов. В настоящее время существует ряд теоретических и практических разработок, позволяющих создавать хранилища данных с нечеткими атрибутами. Это отражено в работах Дидьера Дюбуа Дюбуа Д., 1990 , Мичинори Наката (Michiori Nakata), Генри Прада (Henri Prade) Eufit'98 1998 , в которой исследуется нахождение элементов, с достаточно важными характеристиками; Ж.К.Куберо (J.C.Cubero), Ф.Куенца (F.Cuenca), И.Бланко (I.Blanco), М.А.Вила (M.A.Vila) IFSA'97, 1997 , где рассматриваются неполные функциональные зависимости в сравнении с нахождением знаний в базах данных; исследования Греда Вагнера (Gred Wagner) Eufit'98 1998 , связаны с логической перестройкой нечеткого обращения в базах данных и логических программах; М.А.Вила (M.A.Vila), Ж.К.Куберо (J.C.Cubero), О.Понс (O.Pons), Дж.М.Медина (J.M.Medina) , где исследуются запросы в объектно-ориентированных нечетких базах данных; Анны Изабель Агуилера Фарако (Ana Isabel Aguilera Faraco) и Леонида Жозе Тинео Родригаса (Leonid Jose Tineo Rodriguez) Eufit'98 1998 , в которой разработана нечеткая дедуктивная модель и доведена до реального воплощения; Горбоконенко Е.А. Горбоконенко Е.А. 2000a; 2000b, 2001, где предложена и реализована нечеткая реляционная модель данных.

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

1. Формализованная постановка задачи нечеткой кластеризации

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

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

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

2. Модель и реализация нечеткого реляционного сервера данных

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

Пусть схемой отношения R называется конечное множество имен атрибутов {A₁, A₂, …, A_n}. Каждому имени атрибута A_i ставится множество D_i, называемое доменом атрибута A_i, 1 Ј--i--Ј--n. Домены являются произвольными непустыми конечными или счетными множествами. И пусть D = <D₁, D₂ , …,D_n>.

Домен атрибута реляционного отношения будем называть нечетким, если для него определены:

1. имя атрибута A_i;

2. универсальное множество X;

3. терминальное множество значений T, представляющих собой нечеткие метки.

Нечетким отношением будем называть конечное множество отображений {t₁, t₂, …, t_p} из R в D, если хотя бы одно t_i ? D_i и D_i - нечеткий домен.

Модель рассчитана на представление нечетких чисел; следовательно, доменом атрибута нечеткого числа является множество действительных чисел. Нечеткое число определяется на основе:

1. функции принадлежности;

2. лингвистической оценки.

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

3. Гибридный алгоритм нечеткой кластеризации

1. Новая функция оценки сепарабельности и компактности.

2. Алгоритм кластеризации. Многошаговый maxnim.

С помощью Maxmin метода производится инциализация разбиений путем разделения объектов настолько, насколько это возможно. Затем, путем оптимизации находится локальный оптимум. Каждый центр кластера используется в качестве начальной точки. Затем переход на следующую итерацию. Алгоритм выполняется до сходимости алгоритма или пока не будет достигнуто заданное количество итераций.

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

Из множества существующих алгоритмов кластеризации лишь несколько ориентированны на кластеризацию плотных скоплений точек. Эти методы предполагают, что пользователем задано число кластеров и/или некоторые пороговые значения, изменение которых сильно влияет на результат.

1. Предлагается новая функция оценки, которая пригодна для использования даже при очень большом количестве кластеров.

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

Гибридный алгоритм кластеризации включает в себя следующие шаги.

Вход: множество данных , maxnum - максимальное количество кластеров.

Выход: Оптимальное множество кластеров .

Шаг 1. , , . Случайным образом выбирается объект в качестве точки старта . Выполняется многошаговый maxmin алгоритм с параметрами для поиска оптимального множества кластеров для . Вычисляется функция оценки для .

Шаг 2. Выполняется алгоритм слияния для получения множества кластеров , выбирается центр в качестве точки старта , , . Выполняется многошаговый maxmin алгоритм с параметрами для поиска оптимального множества кластеров для . Вычисляется функция оценки для и принимается как . Если , тогда , , . Повтор шага 2, пока .

Шаг 3. Вывод: - оптимальное множество кластеров.

Данный алгоритм имеет ряд преимуществ перед другими алгоритмами кластеризации.

Сравнение алгоритмов кластеризации. Табл. 1

4. Результат кластеризации социологической базы данных

В 2000 году институтом социально-экономических проблем народонаселения при российской академией наук была разработана анкета «Социально-экономическое положение населения России». Анкета имеет такие разделы, как «Общие данные», «Занятость», «Социальная мобильность», «Социальное положение», «Политическая активность», «Социально-демографический состав домохозяйства», «Уровень жизни домохозяйства», «Расходы», «Имущество», «Жилищные условия», «Личное подсобное хозяйство (для сельских жителей), дачный, огородный участок (для горожан)». Выборка данных для анализа представлена результатами проведения анкетирования в г. Димитровград Ульяновской области.

Целью данной анкеты являлось изучение социально-экономического положения населения России. Эти данные необходимы для корректировки экономической политики России, разработки рекомендаций по мерам, направленным на повышение уровня жизни российских граждан. Анкета состоит из 129 пунктов (438 вопросов). Для проведения опроса случайным образом были отобраны 1080 человек. На некоторые из вопросов нельзя дать четких ответов, например, вопрос №46 «Как часто Вы работаете дома по вечерам и в Ваши выходные дни?». Варианты ответов: часто, редко, никогда. Кластеризация таких данных сложна, так как при делении на классы необходимо объединять различные лингвистические метки. Данные, полученные на основе анкетирования, были погружены в нечеткий реляционный сервер данных. В результате были получены данные, пригодные для автоматизированной обработки информации с помощью DM. Нечетким меткам были поставлены в соответствие функции принадлежности

Табл.2Функции принадлежности.