Модели построения информационных массивов для решения задачи классификации сведений в условиях неопределенности
Целевое пространство информационных массивов, построение процедур его декомпозиции. Критерий сложности построения информационных массивов. Классификация неопределенностей при решении задачи классификации, выбор математического аппарата для формализации.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | автореферат |
Язык | русский |
Дата добавления | 29.08.2018 |
Размер файла | 358,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
На правах рукописи
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата технических наук
модели построения информационных массивов для решения задачи классификации сведений в условиях неопределенности
Специальность 05.25.05 - «Информационные системы и процессы»
Данилкин Сергей Владимирович
Тамбов 2010
Диссертационная работа выполнена на кафедре «Информационные системы и защита информации» Государственного образовательного учреждения высшего профессионального образования «Тамбовский государственный технический университет» (ГОУ ВПО ТГТУ).
Научный руководитель: доктор технических наук, профессор
Громов Юрий Юрьевич
Официальные оппоненты: доктор технических наук, профессор
Алексеев Владимир Витальевич
кандидат физико-математических наук, доцент
Хакимуллин Евгений Робертович
Ведущая организация: Государственное образовательное учреждение высшего профессионального образования «Воронежская государственная технологическая академия»
Защита диссертации состоится 9 июня в 11 часов 00 минут на заседании диссертационного совета Д 212.260.05 ГОУ ВПО ТГТУ по адресу: 392000, г.Тамбов, ул. Советская, 106, Большой зал.
Отзыв на автореферат в двух экземплярах, заверенных гербовой печатью, просим направлять по адресу: 392000, г.Тамбов, ул. Советская, 106, ГОУ ВПО ТГТУ, ученому секретарю диссертационного совета Д 212.260.05 Селивановой З.М.
С диссертацией можно ознакомиться в библиотеке ГОУ ВПО ТГТУ.
Автореферат диссертации размещен на официальном сайте ГОУ ВПО ТГТУ www.tstu.ru
Автореферат разослан «_____»______________2010 г.
Ученый секретарь
диссертационного совета
доктор технических наук, профессор
Селиванова З.М.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. На современном этапе развития общества, характеризующемся интенсивным внедрением информационных технологий, которые в большинстве своем основываются на использовании компьютерных сетей, особое значение приобретают задачи классификации сведений, получаемых из различных источников, одним из которых являются результаты работы информационно-поисковых машин (ИПМ). Использование информационно-поисковых машин в настоящее время приобретает особую значимость при нахождении сведений, необходимых для решения задач анализа, оптимизации, управления и принятия решений в различных сферах деятельности. Необходимость решения задач классификации сведений обусловлена неудовлетворительным качеством работы информационно-поисковых машин, результаты работы которых, в большинстве своем, не отранжированы по критерию релевантности и даже в тех случаях, когда этот критерий используется, отсутствует какая-либо группировка сведений, способствующая упрощению процесса их последующей обработки. Одной из основных особенностей задачи классификации сведений является наличие как качественных, являющихся источником неопределенности, так и количественных признаков в описании объектов исходного множества. При выделении однородных групп сведений, относящихся к объектам выбранной предметной области, различают такие виды группировки исходных данных, как структурная и типологическая. Структурная группировка представляет собой способ выделения количественно однородных групп объектов, а типологическая -- способ выделения качественно однородных групп.
Методы выделения однородных групп сведений используют следующие основные подходы:
- вероятностный подход, основанный на предположении о том, что объекты, принадлежащие одному из выделяемых классов, описываются одинаково распределенными случайными векторами, а для различных классов характерны различные распределения вероятностей;
- вариативный подход, состоящий в разбиении множества объектов по выбранному исследователем признаку на интервалы группирования, в результате чего исходное множество объектов разбивается на группы таким образом, что объекты одной группы находятся на относительно небольшом расстоянии друг от друга;
- структурный подход, базирующийся на представлении об объектах как точках в многомерном пространстве, которое получило развитие в работах Солодовникова В.В., Дубова Ю.А., Якимца В.И., Кузьмина В.Б., Макарова И.М., Виноградской Т.М., Рубчинского А.А., Бирюкова В.Ф., Тумаркина В.И. и др.
Однако при этом не рассматривался процесс получения сведений, подлежащих классификации, основанный не только на результатах работы информационно-поисковых машин, но и на формировании соответствующих информационных массивов, используемых в дальнейшем для решения задач классификации сведений. Процессы построения информационных массивов при решении широкого класса задач рассматривались в работах Кузнецова Н.А., Кульбы В.В., Норенкова И.П., Ковалевского С.С., Косяченко С.А., Цвиркуна А.Д., Павлова В.Б. и др., однако они не использовались для решения задачи классификации сведений в условиях неопределенности, методам и подходам раскрытия которых посвящены работы российских и зарубежных ученых Поспелова Д.А., Аверкина А.Н., Батыршина И.З., Блишуна А.Ф., Кузьмина В.Б., Борисова А.Н., Алексеева.А.В., а также Заде Л.А., Кофмана А. и др.
Таким образом, решение задачи классификации сведений, основанной на использовании сформированных специальным образом информационных массивов и выборе соответствующих методов их обработки в условиях неопределенности, является актуальным.
Цель работы: повысить эффективность процесса классификации сведений в условиях неопределенности путем формирования информационных массивов заданной сложности.
Задачи исследования:
ввести в рассмотрение целевое пространство информационных массивов (ЦПИМ) для последующего построения процедур его декомпозиции;
ввести в рассмотрение критерий сложности построения информационных массивов (ИМ);
провести классификацию неопределенностей, имеющих место при решении задачи классификации, и обосновать выбор математического аппарата для их формализации;
предложить и обосновать структуру информационного массива, удовлетворяющую предложенному критерию оценки сложности, учитывающую влияние факторов неопределенности при решении задачи классификации.
Объект исследования. Методы построения информационных массивов для решения задач классификации сведений.
Предмет исследования. Модели построения информационных массивов по критерию сложности для решения задачи классификации сведений в условиях неопределенности.
Методы исследования. Для решения поставленных задач в работе использованы методы системного анализа, теории нечетких множеств и математического программирования.
Научная новизна работы заключается в следующем:
- предложена формализация целевого пространства информационных массивов в виде кортежа из трех элементов, которыми являются множество информационных массивов, отвечающих общей цели, и определенные на нем отношения эквивалентности и частичной упорядоченности, что дало возможность построить процедуры декомпозиции;
- построены аналитические и процедурные модели декомпозиции информационных массивов, основанные на использовании предложенных типов взаимосвязи, определяемых отношениями эквивалентности, частичной упорядоченности и введенных в рассмотрение прототипах;
- предложен критерий оценки сложности информационного массива, построенный на основе использования характеристических функций, разбивающих целевое пространство информационных массивов на уровни декомпозиции;
- построена аналитическая модель выбора типа «много входов - один выход» (MISO), основанная на применении выбранных T-норм, методов решения задачи классификации сведений из построенных информационных массивов в условиях неопределенности.
Практическая значимость полученных результатов заключается в использовании разработанного программного обеспечения, реализующего построенные процедурные модели решения задач классификации сведений, что позволяет существенно сократить время получения и поиска сведений в локальных и сетевых информационных системах.
Работа выполнена при поддержке Государственного контракта № П292 в рамках ФЦП «Научные и научно-педагогические кадры инновационной России на 2009-2013годы».
Реализация результатов работы осуществлена в ОАО «Пигмент», г.Тамбов; ООО «Совтех», г.Воронеж; Государственном образовательном учреждении высшего профессионального образования «Тамбовский государственный технический университет».
Положения, выносимые на защиту:
формализация целевого пространства информационных массивов в виде кортежа из трех элементов, которыми являются множество информационных массивов, отвечающих общей цели, и определенные на нем отношения эквивалентности и частичной упорядоченности, позволяет построить процедуры его декомпозиции и повысить эффективность решения задачи классификации сведений;
аналитические и процедурные модели декомпозиции целевого пространства информационных массивов, основанные на использовании предложенных типов взаимосвязи, определяемых отношениями эквивалентности, частичной упорядоченности и введенных в рассмотрение прототипах, дают возможность сформировать информационные массивы для решения задачи классификации;
критерий оценки сложности информационного массива, построенный на основе использования характеристических функций, разбивающих целевое пространство информационных массивов на уровни декомпозиции, который позволяет осуществить построение информационного массива с заданными свойствами;
аналитическая модель выбора типа MISO, основанная на применении T-норм, методов решения задачи классификации сведений из построенных информационных массивов в условиях неопределенности, позволила автоматизировать процесс и сократить временные затраты.
Апробация работы. Основные результаты работы представлены и обсуждены на Всероссийских и международных научных конференциях “Наука на рубеже тысячелетий” (международная конференция, Тамбов, 2004), “Динамiка наукових дослiджень `2005” (IV мiждународна науково-практична конференцiя, Днiпропетровськ, 2005), “Теория конфликта и ее приложения” (IV Всероссийская научно-техническая конференция, Воронеж, 2006), на семинарах кафедры “Информационные системы и защита информации” ГОУ ВПО ТГТУ и кафедры “Прикладная информатика” Тамбовского филиала Московского государственного университета культуры и искусств.
Объем и структура работы. Диссертация, общий объем которой составляет 174 страницы (основной текст - 147 страниц), состоит из введения, трех глав, заключения, списка используемых источников, включающего 249 наименования научных трудов на русском и иностранном языках, и 10 приложений. Диссертация содержит 25 рисунков и 12 таблиц.
Публикации. По теме диссертации опубликовано 8 работ, из них 5 статей, в том числе 4 статьи в изданиях, рекомендованных ВАК РФ, и 3 тезисов докладов на Всероссийских и международных научных конференциях.
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
информационный массив декомпозиция формализация
Во введении обоснована актуальность выбранной темы, сформулирована цель работы, поставлены задачи, решения которых позволяют достичь цель исследования.
В главе 1 «Анализ методов решения задачи классификации и проблемы неопределенности» выявлено, что виды и формы нечеткости исследованы в работах Поспелова Д.А., Аверкина А.Н., Батыршина И.З., Блишуна А.Ф., Кузьмина В.Б., Борисова А.Н.
Постановка задачи классификации на предметно-содержательном уровне включает формулировку целей исследования, определяющих тип задачи, выявление характера исходной информации и определение характера результатов исследования. Сделан вывод, что неопределенность в той или иной степени характеризует каждую из этих составляющих, что может быть представлено структурной схемой, изображенной на рис. 1.
Размещено на http://www.allbest.ru/
Рис. 1. Виды неопределенностей в задачах классификации
Для раскрытия неопределенностей, присущих задачам классификации сведений, как правило, используются подходы, достаточно хорошо разработанные и представленные в большом количестве статей и монографий, основные идеи которых обобщены в таблице 1.
Таблица 1. Подходы к обработке неопределенностей в задачах классификации
Неопределенность задачи классификации |
Методология обработки неопределенности |
||
Вид неопределенности |
Форма проявления неопределенности |
||
Неопределенность исходных сведений |
Неоднозначность числа объектов исходной совокупности |
Нечеткие числа (L-R) - типа |
|
Неоднозначность значений переменных в матрице |
Заполнение средними; заполнение с помощью регрессии |
||
Неточность значений перемен-ных в матрице исходных сведений |
Инструментарий с высокой точ-ностью измерения или вычисления |
||
Неполнота исходных сведений |
Методы исключения некомплект-ных объектов; методы с заполне-нием; методы взвешивания; мето-ды, основанные на моделировании |
||
Неопределенность результатов исследования |
Неопределенность формы и взаимного расположения кластеров |
Разведочный анализ сведений |
|
Размытость природы искомой классификации |
Нечеткие методы классификации |
||
Неоднозначность числа кластеров |
Оптимизационные алгоритмы с функционалом качества при неизвестном числе кластеров |
Подходы раскрытия неопределенностей (таблица 1) не являются единственно возможными и не претендуют на статус универсальных; более того, при решении задач классификации имеют место ситуации, которые характеризуются наличием типов (видов) неопределенности. В этом случае положительный эффект достигается за счет незначительного раскрытия и последующего устранения неопределенности. Наличие неопределенности существенно снижает эффективность решения задачи классификации. Рациональным представляется подход, основанный на предварительной обработке используемых сведений. Для проведения такой обработки необходимо ввести в рассмотрение пространство, элементами которого являются сведения. В настоящее время, характеризуемое интенсивным применением сетевых технологий для решения задачи классификации сведений, особое значение приобретает задача классификации сведений, полученных при помощи различных ИПМ из сети Internet. В результате исследований, проведенных в данном разделе, доказана целесообразность рассмотрения пространства ИМ, основываясь на понятии ИМ, введенного и обоснованного в работах Гиляревского Р.С., Кузнецова Н.А., Кульбы В.В., Ковалевского С.С., Косяченко С.А., Сиротюка В.О., при этом ИМ содержит сведения, полученные в результате работы одной ИПМ. Использование пространства ИМ позволит осуществить предварительную обработку сведений, что в свою очередь, обеспечит повышение эффективности решения задачи классификации.
В главе 2 «Аналитические и процедурные модели декомпозиции целевого пространства информационных массивов и построение оценки сложности информационных массивов» вводится в рассмотрение множество ИМ, объединенных общностью цели построения, вместе с множеством отношений на нем. Из этого множества отбираются те ИМ, которые отвечают одной и той же (главной) цели построения или одному и тому же множеству (главных) целей, для последующего использования при решении задачи классификации.
Целевое пространство информационных массивов формализуется аналитической моделью, которая представлена кортежем из 3-х элементов:
, , , (2.1)
информационный массив декомпозиция формализация
где - исходное множество ИМ, - множество отношений эквивалентности, - множество отношений частичного порядка.
Рассмотрим множество всех эквивалентностей, определенных на ЦПИМ; оно по определению не пусто. Если , то примем, что
(из вытекает , )
и из , следует, что . (2.2)
Это отношение логического следования запишем в виде:
, . (2.2')
Определенное таким образом на отношение рефлексивно, антисимметрично, транзитивно, т.е. устанавливает на частичный порядок.
Рассмотрим возможность декомпозиции ЦПИМ на основе понятий смежного класса и факторизации. Любая эквивалентность в принципе позволяет осуществить декомпозицию ЦПИМ на смежные классы из или их объединения:
, (2.3)
где - смежный класс элемента , - фактор-множество. Будем рассматривать только такие декомпозиции, которые позволяют построить систему содержательных оценок ИМ, входящих в ЦПИМ.
Введем в рассмотрение следующие типы взаимосвязи отношений эквивалентности и частичной упорядоченности на ЦПИМ, предполагая, что эквивалентность отличается от тривиальной (равенства), т.е. , а частичный порядок обладает свойствами , - невозможно, в этом случае справедлива аналитическая модель вида :
SP1 - союзная пара : если , то невозможно;
SP2 - сопоставимая пара : если ,, , то невозможно;
SP3 - связанная пара : если , , , то ;
SP4 - сопряженная пара : a) ecть SP1, или SP2, или SP3; б) пусть заданы ; тогда в существуют , такие, что либо , либо ;
SP5 - согласованная пара : каковы бы ни были два различных элемента , либо (в этом случае , невозможно), либо , либо .
Декомпозиция ЦПИМ проводится на основе одной из процедурных моделей, разработанных в диссертации, и имеющей следующей вид:
Шаг 1. В каждом из блоков факторизации ЦПИМ отмечаем по элементу . Множество отмеченных элементов вполне упорядочено отношением , т.е. каждый отмеченный элемент образует «склейку» всех -эквивалентных ему элементов, и таким образом, множество отмеченных элементов изоморфно фактор-множеству , где , - индекс, - индексное множество.
Шаг 2. Вполне упорядоченное множество , согласно теореме Шпильрайна, имеет наименьший элемент , где .
Множество - элемент факторизации ЦПИМ - будем называть минимальным множеством декомпозиции ЦПИМ. Ввиду того, что по определению есть смежный класс , то .
Шаг 3. Предположим, что не пусто; тогда оно содержит наименьший элемент . Пусть . Строим объединение множеств . Тогда , причем по построению , а значит, .
Шаг . Предположим, что не пусто; тогда оно содержит наименьший элемент , - индекс. Строим объединение множеств . Тогда , причем очевидно, что , , а значит, .
Процесс построения продолжается до исчерпания множества , т.е. до исчерпания ЦПИМ, поскольку является разбиением ЦПИМ. Следовательно, образуют декомпозицию .
Таким образом, в результате моделирования построены:
-- декомпозиция в виде покрывающего ЦПИМ семейства множеств , причем ;
-- множество отмеченных элементов , таких, что , является вполне упорядоченным.
Сложность декомпозиции, таким образом, соответствует расстоянию Гливенко от минимального множества до .
Поэтому рассмотрим множество признаков информационных массивов (МПИМ), входящих в пространство: . К числу признаков относятся запросы, типы, размеры, как фактические, так и желаемые.
Для формализации процесса будем предполагать, что все признаки могут быть выражены единым алфавитом, образованным символами -- простыми словами, из которых формируются сложные слова и совокупности слов, т.е. тексты (или списки) на языке алгебры высказываний. Длина слова несущественна, и в дальнейшем не будем различать единичные слова и тексты, т.е. текст будет считаться «длинным» словом.
Пусть -- ЦПИМ; рассмотрим соответствующее МПИМ универсальное множество слов , выражающих все свойства систем и ЦПИМ: . На множестве определим операцию сшивания слов: , где -- конечная комбинация слов из , причем по смыслу символов будем считать, что здесь операция сшивания обладает следующими свойствами:
1) каждое слово определяется сшиванием символов алфавита: , где -- конечно и является номером символа в алфавите , -- каждый символ алфавита ;
2) любые два символа или слова перестановочны: , поскольку порядок указания в списке или слове свойств систем не имеет значения для их облика;
3) любой из символов и любое из слов идемпотентны: , поскольку повторение в списке или слове одного и того же свойства систем ничего не изменяет в их облике;
4) символ играет роль единицы: .
Таким образом, доказана применимость результатов моделирования, позволяющая построить декомпозицию ЦПИМ.
Процедурная модель декомпозиции ЦПИМ имеет вид:
Шаг 1. Минимальное множество (множество элементов минимальной сложности) ; это прообраз слова, означающего, что ИМ отвечает минимальному количеству условий.
Шаг 2. где -- элемент фактор-множества , непосредственно следующий за .
Шаг +1. , где -- элемент фактор-множества , непосредственно следующий за .
В результате построено семейство множеств , являющееся покрытием ЦПИМ и представляющее собой его декомпозицию. Одновременно с указанным процессом декомпозиции ЦПИМ из представителей смежных классов может быть построено множество отмеченных элементов, являющееся шкалой сложности.
В главе получен ряд практически важных применений понятия нечеткости при оценке сложности ИМ: нечеткость ЦПИМ, нечеткость декомпозиций ЦПИМ, что является основой для проведения дальнейших исследований в области классификации сведений в различных областях деятельности.
В главе 3 «Формирование информационных массивов для решения задачи классификации» рассмотрено применение полученных в предыдущей главе результатов для решения задачи классификации сведений.
В качестве иллюстрации разработанных процедурных и аналитической моделей рассмотрим процесс формирования ИМ для решения задачи классификации сведений об известных математиках. Для формирования ИМ используются ИПМ, применение которых осложняется следующими факторами:
1) существует достаточно большое количество сайтов, посвященных данной тематике, однако отсутствуют общие подходы к их построению;
2) при поиске информации, касающейся области профессиональной деятельности, достаточно трудно сформулировать запрос. Например, работы, относящиеся к смежным областям, или находящиеся на стыке различных областей знаний: математики и биологии, вычислительной математики и теплообмена;
3) на различных сайтах представлена неструктурированная информация, полнота и точность которой многократно раскритикована в литературе. Это подчеркивает необходимость рассмотрения факторов неопределенности, классификация которых представлена в первой главе.
Предложена процедурная модель, отражающая этапы решения задачи классификации (рис. 2).
Проведен анализ методов решения задачи классификации, рассмотренных в данной главе, и вычислены оценки сложности известных алгоритмов для последующего использования в предложенной модели выбора. Для получения оценок сложности использованы подходы, развитые в предыдущей главе.
Сформулированы рекомендации по выбору групп методов в зависимости от информации, которой располагает исследователь:
1) если у исследователя существуют содержательные представления об условиях объединения объектов в классы, следует выбрать группу эвристических методов нечеткого подхода в кластерном анализе;
Размещено на http://www.allbest.ru/
Рис. 2. Процедурная модель выбора алгоритмов решения задачи классификации
2) если целью классификации является получение нечеткого разбиения на заранее известное число классов исследуемой совокупности объектов, следует выбрать группу оптимизационных методов нечеткого подхода в кластерном анализе;
3) если целью классификации является получение наглядного представления о нечеткой структуре классифицируемой совокупности объектов сравнительно небольшого объема, следует выбрать иерархические методы нечеткого подхода в кластерном анализе.
Рассмотрим процесс формирования пространства ИМ, содержащих сведения об академике А. Н. Колмогорове, для последующего решения задачи классификации. Пространство ИМ строится по результатам работы ИПМ, при различных вариантах запросов, фрагментарно представленных в таблице 2.
Таблица 2. Среднее количество гиперссылок по ключевым словам в ИПМ за 2009 год.
Ключевые слова ИПМ |
Колмогоров (тыс.) |
Колмогоров А.Н. (тыс.) |
Акад. Колмогоров (тыс.) |
Акад. Колмогоров А.Н. (тыс.) |
Kolmogorov (тыс.) |
Kolmogorov A.N. (тыс.) |
Prof. Kolmogorov (тыс.) |
Prof. Kolmogorov A.N. (тыс.) |
Проф. Колмогоров (тыс.) |
Проф. Колмогоров А.Н. (тыс.) |
|
№ запр. |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
Rambler |
368 |
28 |
41 |
15 |
48 |
44 |
0,765 |
0,604 |
11 |
5 |
|
Yandex |
378 |
213 |
5,104 |
4,827 |
115 |
73 |
5,7 |
4,8 |
12 |
11 |
|
AltaVista |
0,126 |
0,004 |
0,016 |
0,001 |
334 |
319 |
51,6 |
57,1 |
0,001 |
- |
|
|
158 |
67,1 |
10,53 |
9,08 |
354 |
337 |
52,1 |
52,1 |
2,67 |
2,47 |
|
Aport |
73,085 |
73,994 |
30,376 |
29,891 |
1,285 |
0,723 |
1,274 |
0,473 |
9,056 |
3.146 |
|
Yahoo |
181 |
169 |
1,35 |
1,29 |
2210 |
1500 |
107 |
77,2 |
3,36 |
2,72 |
|
Ask |
32,9 |
19,2 |
6,87 |
6,3 |
334 |
270 |
286 |
208 |
3,04 |
1,92 |
|
Lycos |
7,696 |
5,13 |
0,173 |
0,163 |
98,059 |
11,689 |
6,939 |
0,939 |
0,301 |
0,262 |
|
Nigma |
703,94 |
12,392 |
64,437 |
47,894 |
256,18 |
277,81 |
31,567 |
31,033 |
53,39 |
28,43 |
Для построения множества ИМ предварительно был проведен статистический анализ работы ИПМ за период 2007-2009 гг., этапы которого подробно рассмотрены в работе, а часть результатов представлена на рис. 5-10.
Рис. 5. Среднее количество гиперссылок за период 2007-2009 гг. по запросам ИПМ Google
Рис. 6. Среднее количество гиперссылок за период 2007-2009 гг. по запросам ИПМ ASK
Рис. 7. Среднее количество гиперссылок за период 2007-2009 гг. по запросам ИПМ Lycos
Рис. 8. Среднее количество гиперссылок за период 2007-2009 гг. по запросам ИПМ Nigma
Рис. 9. Среднее количество гиперссылок за период 2007-2009 гг. по запросам ИПМ AltaVista
Рис. 10. Среднее количество гиперссылок за период 2007-09 гг. по запросам ИПМ Aport
По результатам проведенного анализа можно сделать вывод об увеличении количества гиперссылок на запросы, обрабатываемые наиболее часто используемыми ИПМ. Для формирования пространства ИМ используем результаты, представленные в таблице 2.
Для выбора метода решения задачи классификации сведений в работе предложена логико-лингвистическая модель, позволяющая выбрать группу методов решения задачи и непосредственно метод из выбранной группы.
Результат решения задачи классификации представлены на рис. 11а. При этом было использовано исходное пространство ИМ.
Далее решалась задача декомпозиции в следующей постановке: задано исходное пространство ИМ (таблица 2), которое определяется парой , где - шкала сложности (допустимое пространство проектирования ИМ определено в главе 2); декомпозиция по сложности , построенная на основе использования процедурных моделей, предложенных в главе 2; множество неотрицательных действительных чисел, которые описывают набор параметров; критериальная функция . Тогда задача построения заключается в выборе элементов из ЦПИМ , для которого выполняется условие вида
, ,
где - фиксированный элемент, , - индексное множество, - порядковая сложность.
Результаты повторного решения задачи классификации представлены на рис. 11б.
а)б)
Рис. 11. Результаты решения задачи классификации эвристическими методами:
а) до проведения процедуры декомпозиции; б) после проведения процедуры декомпозиции
¦ - метод Тамуры-Хигути-Танаки, ¦ - метод Гитмана-Левина,
^ - метод Кутурье-Фьолео,Ч - метод Берштейна-Дзюбы
Анализ представленных результатов позволил сделать вывод о сокращении временных затрат. Таким образом, в результате решения задачи классификации сформировано три кластера (таблица 3, где цифра после точки соответствует номеру запроса ИПМ, а цифра перед точкой - номеру ссылки, ею найденной).
Таблица 3. Результат решения задачи классификации
ИПМ |
Кластер 1 |
Кластер 2 |
Кластер 3 |
|
1 |
2 |
3 |
4 |
|
Rambler |
1.1,7.1-16.1,23.1, 5.2,7.2,8.2,10.2,37.2, 2.3,9.3,12.3,17.3,29.3, 3.4,9.4,27.4,49.4 |
1.5,2.5,4.5,7.5,11.5, 3.6,5.6-7.6,9.6,14.6, 2.7-5.7,8.7,12.7-14.7, 6.8,8.8,9.8,13.8 |
1.9-3.9,6.9-9.9, 2.10,6.10,8.10,10.10-12.10 |
|
Yandex |
1.1-5.1,8.1-10.1, 1.2-3.2,5.2-8.2, 1.3,3.3,6.3,9.3,10.3, 7.4,9.4,10.4 |
1.5-3.5,24.5,45.5, 1.6-6.6,9.6,10.6, 18.7,42.7,57.7,64.7, 2.8,4.8,6.8,9.8 |
2.9,23.9,36.9,41.9, 22.10,34.10,43.10,48.10 |
|
Alta Vista |
1.1-4.1,6.1-8.1, 3.2,4.2,7.2,11.2-14.2, 4.3-7.3,12.3,16.3, 6.4,9.4,12.4,24.4 |
1.5,2.5,6.5,7.5, 1.6-6.6,8.6,9.6, 1.7,4.7,7.7,9.7, 2.8,12.8,14.8,25.8 |
3.9-6.9,8.9,10.9-14.9, 5.10,8.10,10.10,16.10 |
|
|
1.1-3.1,9.1,10.1, 1.2-7.2,10.2,11.2, 8.3,9.3,12.3-15.3, 1.4,3.4-6.4,10.4 |
1.5-2.5,4.5,5.5,6.5, 2.6-6.6,8.6,9.6,11.6, 1.7,2.7,5.7,18.7, 2.8,8.8,11.8,24.8 |
9.9,15.9,19.9,26.9, 4.10,19.10,21.10,27.10 |
|
Aport |
1.1-4.1,6.1,8.1, 2.2-6.2,7.2-9.2, 3.3,7.3,9.3,14.3,25.3, 6.4-8.4,12.4,16.4 |
2.5,4.5,7.5,8.5,9.5, 1.6,3.6-10.6, 1.7,2.7,4.7,14.7, 1.8,16.8,28.8,37.8 |
3.9,5.9,7.9-12.9, 2.10,7.10,11.10-14.10 |
|
Yahoo |
1.1,4.1-10.1, 2.2-6.2,8.2,12.2,16.2, 1.3-9.3, 1.4,2.4,9.4 |
1.5-11.5, 2.6-3.6,6.6,8.6,10.6, 1.7,2.7,10.7, 2.8,5.8,6.8,7.8,8.8 |
1.9,9.9,14.9-17.9, 2.10,5.10-7.10,16.10 |
|
Ask |
1.1-3.1,7.1,8.1, 1.2,5.2,7.2,14.2,18.2, 1.3,2.3,4.3,5.3,7.3,8.3, 6.4,7.4,8.4,9.4,10.4 |
1.5,2.5,6.5-9.5, 2.6,4.6-7.6,9.6, 4.7,5.7,6.7,8.7, 9.8,22.8,36.8,40.8 |
6.9,7.9,9.9, 15.10,18.10,27.10 |
|
Lycos |
1.1-8.1, 2.2-7.2,10.2, 2.3-6.3,11.3, 3.4,6.4,8.4,10.4-13.4 |
2.5-6.5,3.6-9.6, 2.7,4.7,6.7-12.7, 5.8,7.8,11.8,24.8 |
4.9,8.9,13.9,21.9, 8.10-10.10,16.10,19.10 |
|
Nigma |
3.1,4.1,7.1,12.1,13.1, 17.2-20.2, 1.3,16.3,17.3,20.3, 2.4,3.4,6.4,11.4,14.4 |
1.5-7.5,9.5,10.5,12.5, 2.6-4.6,7.6,9.6,12.6-17.6, 1.7,10.7,12.7, 3.8,4.8,11.8,14.8,16.8 |
1.9-3.9,16.9,20.9, 14.10,16.10,20.10 |
Полученный результат определяет иерархию поиска необходимых сведений, отвечающих рассмотренным запросам, который в данном случае может проводиться как по полученным кластерам, так и внутри них.
Для достижения поставленной в работе цели необходимо оценить эффективность (Э) решения задачи классификации. Для этого предлагается использовать выражение вида:
,
где - оценка качества результата, полученного с использованием алгоритма решения задачи классификации на пространстве ИМ; - алгоритм решения задачи классификации; - исходное пространство ИМ; - декомпозированное пространство ИМ.
Результаты, графические интерпретации которых представлены на рисунках 11а, 11б, легли в основу расчета эффективности решения задачи классификации сведений, для решения которой использовались исходное и декомпозированное пространства ИМ. При этом в рассмотрение принимался метод Тамуры-Хигути-Танаки, относящийся к группе эвристических методов, характеризующийся наименьшими временными затратами.
Рис. 12. Эффективность решения задачи классификации методом Тамуры-Хигути-Танаки
Эффективность решения задачи классификации методом Тамуры-Хигути-Танаки после проведения декомпозиции, отранжированная по номерам запросов, представлена на рис. 12, и анализ изменения которой позволил сделать вывод, что ее максимальная величина составила 32,5%.
В заключении сформулированы основные результаты работы
предложена формализация целевого пространства информационных массивов в виде кортежа из трех элементов, которыми являются множество информационных массивов, отвечающих общей цели, и определенные на нем отношения эквивалентности и частичной упорядоченности, что дало возможность построить процедуры его декомпозиции с целью повышения эффективности решения задачи классификации сведений;
построены аналитические и процедурные модели декомпозиции ИМ, основанные на использовании предложенных типов взаимосвязи, определяемых отношениями эквивалентности, частичной упорядоченности и введенных в рассмотрение прототипах, что позволило сформировать информационные массивы с заданными свойствами для решения задачи классификации;
предложен критерий оценки сложности информационного массива, построенный на основе использования характеристических функций, разбивающих целевое пространство информационных массивов на уровни декомпозиции, использование которого дало возможность организовать информационный массив с заданными свойствами;
разработана аналитическая модель выбора типа MISO, основанная на применении обоснованно выбранных T-норм, методов решения задачи классификации сведений построенных информационных массивов в условиях неопределенности;
результаты проведенных экспериментальных исследований дали возможность сделать вывод о повышении эффективности решения задачи классификации сведений на 32,5% вследствие применения построенных в работе аналитических и процедурных моделей формирования информационных массивов и проведения декомпозиции ИМ.
СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ
Публикации в изданиях, рекомендованных ВАК РФ
Данилкин, С.В. Определение целевого пространства информационных массивов / С.В. Данилкин // Вопросы современной науки и практики. Университет им. В.И. Вернадского. - 2009. - №11(25). - С.210-215.
Данилкин, С.В. Информационные модели для организации имитационных исследований / С.В. Данилкин, А.В. Сыроид // Инженерная физика. - 2010. - №3. - C.11-16 (6/3).
Данилкин, С.В. Математическая формализация процесса обучения / С.В. Данилкин, Ю.Ю. Громов, Н.А. Земской, О.Г. Иванова, А.В. Лагутин, Т. Лутхон, И.И. Пасечников, В.М. Тютюнник, Т.Г. Самхарадзе // Инженерная физика. - 2005. - №3. - С.51-55 (5/2).
Данилкин, С.В. Математическое моделирование информационных процессов в сети с заданной структурой / С.В. Данилкин, Ю.Ю. Громов, О.Г. Иванова, А.В. Лагутин, Н.А. Земской, И.И. Пасечников // Инженерная физика. - 2003. - №2. - C.44 - 47 (4/1).
Статьи и материалы конференций
Данилкин, С.В. Гносеологические подходы к решению задач классификации с позиции теории нечетких множеств / С.В. Данилкин, С.А. Неезжалая, А.Ю. Громова // Информационные системы и процессы: сб. научных тр. / под ред. проф. В.М.Тютюнника. - Тамбов; М.; Баку; Вена: Изд-во «Нобелистика». - 2006. - Вып.4. - С.41-49 (9/6).
Данилкин, С.В. Проблема неопределенности в задачах автоматической классификации при построении информационных систем / С.В. Данилкин, А.Ю. Громова, О.Г. Иванова // Теория конфликта и ее приложения: Материалы IV Всероссийской научно-технической конференции. Часть II / Сост. Львович И.Я., Сербулов Ю.С. - / АНОО ВИВТ; РосНОУ (ВФ). - Воронеж: Научная книга. - 2006. - 363 с. - С. 170-181 (12/6).
Данилкин, С.В. Актуальность использования отказоустойчивых кластерных систем в инфраструктуре / Данилкин С.В., Громов Ю.Ю., Земской Н.А., Борисов А.Н. // IV мiждународна науково-практична конференцiя «Динамiка наукових дослiджень `2005». Том 50. Соучаснi iнформацiйнi технологiї. -Днiпропетровськ: Наука i освiта. - 2005. - 47 с. - C. 22-23 (2/1).
Данилкин, С.В. К вопросу построения аналитических моделей информационных систем / С.В. Данилкин, Ю.Ю. Громов, Д.Е. Винокуров, А.В. Старущенко // Международная конференция «Наука на рубеже тысячелетий»: Сборник научных статей по материалам конференции 29-30 октября 2004 года - Тамбов: изд-во БМА. - 2004. - С.164-165 (2/1).
Размещено на Allbest.ru
Подобные документы
Схема организационной структуры управления информационных и аналитических технологий аппарата администрации. Математическая постановка задачи классификации информационных сообщений СМИ. Описание информационного обеспечения на примере АИС "Классификатор".
дипломная работа [677,2 K], добавлен 28.07.2009Ознакомление с особенностями программной реализации алгоритмов преобразования одномерных массивов. Исследование развития вычислительной техники, которое подразумевает использование компьютерных и информационных технологий. Изучение интерфейса программы.
курсовая работа [1,0 M], добавлен 02.06.2017Широкое использование компьютерных и информационных технологий. Концепции типов данных. Алгоритмы сортировки одномерных массивов. Описание двумерного массива Паскаля. Методы доступа к элементам массивов. Индексные, динамические и гетерогенные массивы.
курсовая работа [66,3 K], добавлен 07.12.2010Разработка программ на языке Turbo Pascal на основе использования массивов данных. Особенности хранения данных, способы объявления переменных, действия над элементами массивов, их ввод и вывод. Практическое применение одномерных и многомерных массивов.
методичка [17,8 K], добавлен 25.11.2010Понятие массива и правила описания массивов в программах на языке С. Рассмотрение основных алгоритмов обработки одномерных массивов. Примеры программ на языке С для всех рассмотренных алгоритмов. Примеры решения задач по обработке одномерных массивов.
учебное пособие [1,1 M], добавлен 22.02.2011Характеристика сущности и назначения автоматизированных информационных систем (АИС), под которыми понимают совокупность информационных массивов технических, программных и языковых средств, предназначенных для сбора, хранения, поиска, обработки данных.
контрольная работа [24,4 K], добавлен 29.08.2010Разработка программы для решения инженерных задач с использованием функций, процедур и сложных типов данных, в том числе динамических массивов и объединений. Интерфейс ввода/вывода. Схемы алгоритмов отдельных подзадач. Технические требования к программе.
курсовая работа [60,7 K], добавлен 26.11.2012Структура – это объединение одного либо более объектов (переменных, массивов, указателей, других структур). Понятие структурной переменной. Создание массивов структур. Использование вложенных структур в виде элементов массивов person, date, pibm.
лабораторная работа [17,6 K], добавлен 15.07.2010Реализация различных методов сортировки. Алгоритмические языки программирования. Обработка большого числа единообразно организованных данных. Алгоритмы сортировки массивов. Анализ проблем реализации и использования различных видов сортировок массивов.
курсовая работа [640,3 K], добавлен 07.07.2011Задачи информационных потоков в логистике. Виды и принципы построения, структура и элементы информационных логистических систем, основные требования к ним. Рекомендации по созданию, внедрению и режиму работы информационных систем в сфере логистики.
реферат [25,9 K], добавлен 14.01.2011