Формирование подмножеств сильносвязанных признаков при построении алгоритмов распознавания

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

Научно-инновационный центр информационно-коммуникационных технологий при Ташкентском университете информационных технологий имени Мухаммада ал-Хоразмий, Республика Узбекистан

Формирование подмножеств сильносвязанных признаков при построении алгоритмов распознавания

Мирзаев Номаз Мирзаевич, Раджабов Собиржон Сатторович

кандидат технических наук, старший научный

сотрудник лаборатории "Системы обработки данных"

Аннотация

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

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

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

Ключевые слова: взаимосвязанность признаков, выделение подмножеств признаков, принцип потенциалов, система признаков, суммарная потенциальная энергия

Рубрика: 05.00.00 ТЕХНИЧЕСКИЕ НАУКИ

Библиографическая ссылка на статью:

Мирзаев Н.М., Раджабов С.С. Формирование подмножеств сильносвязанных признаков при построении алгоритмов распознавания // Современные научные исследования и инновации. 2017. № 10 [Электронный ресурс]. URL: http://web.snauka.ru/issues/2017/10/84465 (дата обращения: 27.09.2018).

Введение

алгоритм распознавание признаковый пространство

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

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

В работах [9-12] рассмотрены модели алгоритмов распознавания, основанных на оценке взаимосвязанности признаков. Одним из основных этапов этих алгоритмов является выделение подмножеств сильносвязанных признаков. Несмотря на это, задачи, связанные с вопросами выделения подмножеств сильносвязанных признаков, малоисследованы.

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

1. Постановка задачи

Рассмотрим множество  признаков , которые образуют m-мерное пространство . Предполагается, что в пространстве  определена количественная мера парных связей между признаками и [13]:

Пусть требуется разбить множество

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

2) ;

3) , .

Разбиение множества признаков  на  непустых подмножеств обозначим через . Метод решения

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

1) ,

(1)где  - потенциальная функция второго типа [1]; - число признаков, входящих в подмножества  и ;

 -

параметры алгоритма.

2) ;

3) .

В дальнейшем в качестве меры близости можно использовать любую из рассмотренных выше .

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

такое, что . Для подмножеств  определим его потенциальную энергию :

.

Для двух подмножеств  и  потенциальной энергией этих подмножеств относительно друг друга определим в следующем виде:

.

Нетрудно заметить, что для одноэлементного

подмножества  () потенциальная энергия  есть потенциал, который создан по всем элементам подмножества  относительно элемента .

Из свойства аддитивности потенциала вытекает свойство аддитивности потенциальной энергии при взаимодействии элементов подмножеств ,  и  ( ):

;

 при .

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

.

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

. (2)

Очевидно, что разбиение  (при фиксированном ) с максимальным значением энергии т.е.

,

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

Далее рассмотрим описание основных этапов этих алгоритмов.

Этап 1. Формирование начальных подмножеств сильносвязанных признаков. В начале данного этапа предполагается, что каждый признак образует отдельное подмножество, т.е. имеются подмножеств [13]. На основе исходного разбиения вычисляются значения мер близости между признаками по всевозможным парам и формируются матрицы близости  нулевого порядка.

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

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

Тогда на -ом шаге выполняются следующие операции.

1. Определяется максимальный элемент из матрицы близости.

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

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

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

Заметим, что этот процесс продолжается до тех пор, пока не получится  ”независимых” подмножеств признаков , каждая из которых сильносвязана в своем подмножестве.

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

,

где  - шаг признаков, в подмножество .

На k-ом шаге итерации заданное множество признаков распределяется по n подмножествам по следующему правилу:

если  для всех ,

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

На основе результатов k-ого шага определяется новый источник потенциалов ,  Следует отметить, что новые источники потенциалов  определяются исходя из условия максимума суммарную потенциалов:

 (3)

Одним из простых способов определения , который обеспечивает максимум (3), является вычисление выборочного среднего по всем признакам, принадлежащим подмножеству  [14]:

Здесь  - число признаков, входящих в подмножество . Если координаты источников не изменились, то процедура второго этапа завершается. В противном случае выполняется следующая итерация.

В целях оценки работоспособности предложенных алгоритмов проводятся экспериментальные исследования при выделении подмножеств сильносвязанных признаков.

Экспериментальная проверка

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

1) модельной задачи;

2) практической задачи определения закономерностей размещения месторождений полезных ископаемых (МПИ).Задача 1. Исходные данные для модельной задачи были сгенерированы в пространстве зависимых признаков. При этом использован метод формирования случайных векторов с заданными корреляционными свойствами [15]. Объем анализируемой выборки - 50 реализаций. Количество признаков равно 6. Число подмножеств сильносвязанных признаков равно 3: в первом подмножестве 2 признака, во втором - 1, в третьем - 3. Вид распределения нормальный. Параметры распределения:

,

,

где M - математическое ожидание; - ковариационная матрица сгенерированных данных.

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

, , .

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

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

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

В таблице 1 приведен результат работы алгоритма.

Таблица 1 Выявленные подмножества сильносвязанных признаков

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

Заключение

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

Библиографический список

1. Айзерман М.А., Браверман Э.М., Розоноэр Л.И. Метод потенциальных функций в теории обучения машин. - М.: Наука, 1970. - 348 с.

2. Журавлев Ю.И. Избранные научные труды. - М.: Магистр, 1998. - 420 с.

3. Журавлев Ю.И., Рязанов В.В., Сенько О.В. Распознавание. Математические методы. Программная система. Практические применения. -М.: Фазис, 2006.-159 с.

4. Загоруйко Н.Г. Прикладные методы анализа данных и знаний. - Новосибирск: ИМ СО РАН, 1999. - 266 с.

5. Лбов Г.С., Бериков В.Б. Устойчивость решающих функций в задачах распознавания образов и анализа разнотипной информации. - Новосибирск: ИМ СО РАН, 2005. - 220 с.

6. Vapnik V. Statistical Learning Theory. -New York: John Wiley Sons, Inc., 1998. -732 p.

7. R. Duda, P. Hart, D. Stork. Pattern Classification. - New York: John Wiley, Inc., 2001. - 680 p.

8. Камилов М.М., Мирзаев Н.М., Раджабов С.С. Современное состояние вопросов построения моделей алгоритмов распознавания //Химическая технология. Контроль и управление. - Ташкент, 2009. - № 2. - С.67-72.

9. Фазылов Ш.Х., Мирзаев Н.М., Мирзаев О.Н. Об одной модели модифицированных алгоритмов распознавания типа потенциальных функций //Математические методы распознавания образов: Тез. докл. - М., 2009. - С. 200-203.

10. Каримов И.К., Раджабов С.С., Мирзаев О.Н., Даминов О.А. Распознающие операторы, основанные на принципе потенциалов, в условиях большой размерности признакового пространства // Вестник Камчатского государственного технического университета. - Петропавловск-Камчатский, 2012. - № 4 (22). - С. 8-14.

11. Мирзаев О.Н. Распознающие операторы, основанные на построении модели источников потенциала // Проблемы информатики и энергетики. - Ташкент, 2012. - № 6. - С.80-86.

12. Камилов М.М., Фазылов Ш.Х., Мирзаев О.Н. Модель модифицированных распознающих операторов, основанных на принципе потенциалов //Химическая технология. Контроль и управление. - Ташкент, 2013. - № 3. - С. 50-56.

13. Камилов М.М., Мирзаев Н.М., Раджабов С.С. Определение параметров модели алгоритмов распознавания, основанных на оценке взаимосвязанности признаков // Знания-Онтологии-Теории: Материалы Всерос. конф. с международным участием / Ин-т матем. СО РАН. - Новосибирск, 2009. - Т. 1. - С. 35 - 41.

14. Zaki M.J., W. Meira Jr. Data mining and analysis: fundamental concepts and algorithms. - Cambridge: Cambridge University Press, 2014. - 660 p.

15. Rainey L.B., Tolk A. Modeling and Simulation Support for System of Systems Engineering Applications. - New York: John Wiley Sons, Inc., 2015. - 640 p.

Размещено на Allbest.ru