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

Для проведения сравненительного анализа, была также создана база знаний с помощью коммерчески доступной нечеткой нейронной сети ДБМ [6].

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

Таблица

Результаты аппроксимации гармонического сигнала

Подход Ошибка Вычислительные

аппроксимации затраты

I ~6*10-5 100 поколений

II ~4*10-6 1000 шагов

AFM ~4*10-6 1000 шагов

100 поколений генетического

III ~1.6*10-6 алгоритма + 500 шагов алгоритма обратного распространения ошибки

Для проверки разработанного подхода был рассмотрен также типовой обучающий сигнал Фишера [7]. Для компонент сигнала были получены лингвистические аппроксимации и сформирована база нечетких правил. В процессе обучения было использовано 50 % данных. В результате получено 100 % распознавание элементов обучающей выборки, и 97 % распознавание элементов тестирующей выборки.

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

Список литературы

1. Лохин В.М., Макаров И.М., Манько С.В., Романов М.П. Методические основы аналитического конструирования регуляторов нечеткого управления. - Изв. РАН: Теория и системы управления. - 2000. - №1. - С. 56-69.

2. Torkkola K. Mutual Information in Learning Feature Transformations, Proc. 17th International Conf. on Machine Learning, 2000.

3. Nguyen H.N., Walker E.A. A First Course in Fuzzy Logic, CRC Press, 1997.

4. Holland J., Adaptation in Natural and Artificial Systems, Univercity of Michgan (1975), reprinted with revision by MIT Press (1992).

5. David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Pub Co., 1989.

6. Adaptive Fuzzy Modeler (AFM), http://eu.st.com/ston-line/index.shtml.

7. Fisher R.A. The Use of Multiple Measurements in Axonomic Problems, Annals of Eugenics 7, 1936, pp. 179-188.

ПОИСКОВЫЕ СИСТЕМЫ С ПРОСТРАНСТВЕННО-ОБРАЗНЫМ ИНДЕКСИРОВАНИЕМ И ИСПОЛЬЗОВАНИЕМ НЕЧЕТКИХ МОДЕЛЕЙ ПРИНЯТИЯ РЕШЕНИЙ

С.Л. Беляков, Э.М. Котов, А.Н. Целых

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

- процесс накопления данных развивается независимо от процесса их использования, причем цели каждого из процессов различны;

- информационная основа настолько разнородна, что не имеет смысла указывать единую схему данных из-за многоаспектности использования информации;

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

Как следствие, возникает проблема избыточности ответов на поисковые запросы. Типичным примером является получение информации из Интернета: обычным явлением может быть ответ по-

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

Возможным путем решения проблемы может стать использование технологии геоинформационных систем (ГИС). Ее особенность в манипулировании пространственно-образными моделями реальных объектов и событий [1]. Если речь идет о земном пространстве, то естественной концептуальной основой моделей являются географические карты. Однако ничто не мешает создавать пространственно-образные модели информационного пространства, каковым может являться информационная база крупного предприятия или учреждения. С точки зрения организации поиска привлекательны следующие свойства карт, схем и планов.

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

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

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

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

Известным и эффективно применяемым на практике принципом поиска документов является поиск по ключевым словам [2].

Поисковая система для множества доступных документов D = {d1,d2,...,dn} строит индекс как отображение множества ключевых слов K = {k1,k2,...,km} в множестве документов I:K ^ D.

Запрос на поиск формируется как выражение F(KF), где KF с K .

Результатом выполнения запроса является множество документов R с D, причем dj е R ^ Kd. е KF ^f(kf)= true.

Здесь Kd. - ключевое множество слов документа d,.

Пространственный характер индекс приобретает в случае, когда

I:V(x,y,z)^D, где V(x, y, z) - трехмерное евклидово пространство. Каждому документу в таком представлении сопоставлен объект трехмерного пространства -образ множества документов V(x,y,z)^ D, Vj (x,y,z)c V(x,y,z),Dv. с D .

Запрос на поиск документов является выражением G(x,y,z), которое используется аналогично рассмотренному выше:

dj е R ^ dj е DVj ^ G^(x,y,z))= true .

Расширение размерности пространства для индексирования документов с формальной точки зрения не ускоряет поиск и не упрощает индексирование. Цель подобной операции - переход в более естественную для человека среду решения интеллектуальных задач. В отличие от числовых операций и символьных преобразований, пространственно-образные категории способны отобразить самые ценные - глубинные знания человека-эксперта [3]. Хотя указанные преимущества не реализуются автоматически, следует обратить внимание на особенность инструментария ГИС, позволяющего работать с объектами сложных систем: документы, характеризующиеся не набором ключевых слов Kdj , но более высокоуровневым в смысловом отношении набором показателей качества Q = {q1,q2,—,qA }.

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

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

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

строится поисковый образ с использованием бу-левого оператора «И», то это интерпретируется как минимум из двух функций, соответствующих терминам запросов. При использовании булевого оператора «ИЛИ» это интерпретируется как максимум, а при использовании булевого оператора «НЕ» - как 1 («значение функции»). Далее документы результата поиска ранжируются в соответствии с полученными значениями так же, как и в случае с поиском по мерам близости.

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

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

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

Такую функцию можно назвать интервальной функцией принадлежности интервального нечеткого множества [4].

Рассмотрим алгоритм построения функции принадлежности интервального нечеткого множества.

Пусть требуется для множества А найти значения функции принадлежности по результатам

опроса т экспертов [5] ^ (х.)=[ ^а . ^а (х.)],

1. Каждому из экспертов предъявляется количественное значение х. и определяется субъективное значение функции принадлежности (х.),

получаемое от . эксперта, соответствующее значению для множества А . Далее находим среднее значение функции принадлежности, используя среднее арифметическое, задаваемое формулой [6]

^ ч 1 т * ( \ т.=1

2. Определяется отклонение от среднего значения по формуле

2.

3. Определяются предварительная верхняя и предварительная нижняя границы по формулам

^Аерх

соответственно.

максимальное минимальное

значение значение

4. Определяется тах( ^Аерх (х.)) и

• / ииж / ч ч ^

тш( ^а (х.)) соответственно для верхней и нижней границ.

5. Значения (х.) и (х.) определяются по формулам:

цАерХ

ЦА(х.):

^ (тах(^^х(х.))-т1п(^^(х.))) производятся нормировки верхней и нижней границ. Верхняя граница не должна превышать 1, а нижняя граница не должна быть меньше 0.

Пункты 1-5 повторяются для всех количественных значений шкалы Х, тем самым определя-

*

ются все значения функции (х.).

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

Можно предложить метод изменения запросов, известный под названием обратная связь по релевантности.

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

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

q' = q + а 2 г. - р 2

иеИ £8

где г. - это .-й документ, входящий в множество

релевантных документов; - .-й документ, входящий в множество нерелевантных документов; а, р - константы.

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

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

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

Если документы и запросы представлены множеством наборов взвешенных терминов документа и запроса, можно вычислить функцию подобия векторов 8, отражающую степень сходства каждой пары «запрос-документ»:

запр°с О = {Ч1,Ч2,-,Ч„ К

где q¡ - вес 1-го термина запроса;

документ ] },

где | - вес ¡-го термина документа |

Функция подобия

, , ё

)=  ¡=1 .

V¡=1 ¡=1

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

При решении проблемы отображения данных, не поддающихся количественной оценке, в ГИС может быть использован следующий прием: вводится совокупность тематических карт или схем, в каждой из которых вектор показателей документа ) представляется, например, как

^р^ у^^Г-^А)), qp,qz е^и^^А}.

Это означает представление в двухмерной координатной системе ) документа образом,

характеризующимся ). Сопоставляя

слои графического изображения, цвет, текстуры и формы, комбинируя пары показателей ),

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

Инструментарий ГИС дает дополнительные возможности построения запросов интуитивно-образного характера. Например, запрос "найти до-

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

Структуру поисковой системы можно изобразить следующим образом:

Запрос строится пользователем с использованием навигатора - диалогового средства, предоставляемого ГИС. С его же помощью ГИС формирует и поддерживает пространственно-образный индекс. Планировщик выполнения запросов является экспертной системой, которая на основе знаний из пространственно-образного индекса формирует множество ссылок на запрошенные документы. Приведенная структура может быть эффективно реализована по технологии "клиент-сервер". Многие современные ГИС представляют объектный интерфейс внешним приложениям по спецификациям COM или CORBA. Таким образом, сервер ГИС выполняет традиционную функцию по управлению картографической информацией, которая в данном случае относится к информационному пространству.

Список литературы

1. Берштейн Л.С., Беляков С.Л. Геоинформационные справочные системы.- Таганрог: Изд-во ТРТУ, 2001.

2. Гаврилова Т.Н., Хорошевский В.Ф. Базы знаний интеллектуальных систем. - С-Пб: Питер, 2000.

3. Дулин С.К., Самохвалов Р.В. Оценка эффективности экспертного анализа диссиминации неструктурированной текстовой информации - Изв. РАН: Теория и системы управления. - 2003. - №1. - С. 95-104.

4. Целых А.Н. Разработка и исследование моделей принятия решений в интегрированных интеллектуальных системах и их применение для решения экологических задач: Дис. ... докт. техн. наук. - Таганрог, 2000.

5. Берштейн Л.С., Целых А.Н., Тимошенко Р.П. Об использовании интервальной функции принадлежности нечеткого множества. - Изв. вузов. Северо-Кавказский регион. Технические науки. - Р-н-Д.: Изд-во РГУ. - 1999. - №1. - С. 3-8.

6. Бочаров. П.П., Печерина А.В. Теория вероятностей. Математическая статистика: Учеб. пособие. - М.: Гардарика, 1998.-326 с.

7. Solton G., The Performance of interactive information retrieval, Information processing letters, 1, No. 2, 1971.