Многошаговая система поиска альтернатив в информационном каталоге

щем кадре с помощью уравнения линейного равноускоренного движения: r=r0+v0t+(at2)/2, где r0 -начальная позиция знака на изображении; v0 -скорость; a - ускорение знака; r - позиция знака по прошествии интервала времени.

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

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

Литература

1. Stallkamp J., Schlipsing M., Salmen J., Igel C., Man vs. Computer: Benchmarking Machine Learning Algorithms for Traffic Sign Recognition, Neural Networks, 2012, Vol. 32, pp. 323-332.

2. Baro X., Escalera S., Vitria J., Pujol O., Radeva P., Traffic sign recognition using evolutionary Adaboost detection and Forest-ECOC classification, IEEE Transactions on Intelligent Transportation Systems, 2009, Vol. 10, no. 1, pp. 113-126.

3. Balas B.J. and Sinha P., STICKS: Image-representation via non-local comparisons, J. Vis., 2003, Oct., Vol. 3, no. 9, p. 12.

4. Timofte R., Zimmermann K. and Gool L.V., Multi-view traffic sign detection, recognition, and 3D localization, Workshop on Applications of Computer Vision, 2009, pp. 1-8.

5. Overett G.M., Tychsen-Smith L., Petersson L., Andersson L., Pettersson N., Creating Robust High-Throughput Traffic Sign Detectors Using Centre-Surround HOG Statistics, Machine Vision and Applications, 2011, Dec., pp. 1-14.

6. Dalal N., Triggs W., Histogram of oriented gradients for human detection, Proc. IEEE Conf.Comput. Vis. and Pattern Recog., 2005, pp. 886-893.

7. Russian Traffic Signs Dataset. URL: ftp://anonymous@ki-viuq.graphicon.ru/AnonymousFTP/RTSD/ (дата обращения: 12.06.2013).

8. Моисеев Б., Чигорин А. Классификация автодорожных знаков на основе сверточной нейросети, обученной на синтетических данных // ГрафиКон'2012: сб. тр. 22-й Междунар. конф. по компьют. графике и машин. зрению. М.: МГУ, 2012. С. 284-287.

9. Ruta A., Porikli F., Watanabe S., Li Y., In-vehicle camera traffic sign detection and recognition, Mach. Vis. Appl., 2011, Vol. 22, no. 2, pp. 359-375.

10. Cuda-convnet library. URL: https://code.google.com/p/cu-da-convnet/ (дата обращения: 12.06.2013).

References

1. Stallkamp J., Schlipsing M., Salmen J., Igel C., Neural Networks, 2012, Vol. 32, pp. 323-332.

2. Baro X., Escalera S., Vitria J., Pujol O., Radeva P., IEEE Transactions on Intelligent Transportation Systems, 2009, Vol. 10, no. 1, pp. 113-126.

3. Balas B.J., Sinha P., Journ. of Vision, 2003, Vol. 3, no. 9, p. 12.

4. Timofte R., Zimmermann K., Gool L.V., Workshop on Applications of Computer Vision, 2009, pp. 1-8.

5. Overett G.M., Tychsen-Smith L., Petersson L., Andersson L., Pettersson N., Machine Vision and Applications, 2011, pp. 114.

6. Dalal N., Triggs W., Proc. IEEE Conf. Comput. Vis. and Pattern Recog., 2005, pp. 886-893.

7. Russian Traffic Signs Dataset, available at: ftp://anony-mous@kiviuq.graphicon.ru/AnonymousFTP/RTSD/ (accessed 12 June 2013).

8. Moiseev B., Chigorin A., GrafiKon'2012: sb. tr. 22 Mezh-dunar. konf. po kompyut. grafike i mashinnomu zreniyu [Graphi-Kon'2012: proc. of 22th int. conf.on computer graphics and mashine vision], 2012, pp. 284-287.

9. Ruta A., Porikli F., Watanabe S., Li Y., Mach. Vis. Appl., 2011, Vol. 22, no. 2, pp. 359-375.

10. Cuda-convnet library, available at: https://code.google. com/p/cuda-convnet/ (accessed 12 June 2013).

УДК 004.415.2.031.43

МНОГОШАГОВАЯ СИСТЕМА ПОИСКА АЛЬТЕРНАТИВ В ИНФОРМАЦИОННОМ КАТАЛОГЕ

Б.В. Палюх, д.т.н., профессор; И.А. Егерева, к.т.н., докторант

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

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

Ключевые слова: систематизация, каталог сервисов, поиск информации, теория нечетких систем, многошаговый процесс принятия решения.

MULTISTEP ALTERNATIVES SEARCH IN AN INFORMATION CATALOGUE Palyukh B. V., Ph.D., professor; Egereva I.A., Ph.D., doctorant (Tver State Technical University, Quay Nikitin, 22, Tver, 170026, Russia, irina.egereva@gmail.com) Abstract. Despite the fact that data catalogues are widely used in different areas, data search that is considered as the major part of data systematization, is being done with strictly formulated search requests that result in a search results list. However, quite often it is impossible to state a specific search request. It is also impossible to state search criteria specifically. To avoid restricting the access to full information in given catalogues, it is recommended to provide quality system access. The article addresses software solutions for systematization of heterogeneous data. The article gives solutions description in words and parameters to provide forming a ranked search results list that matches a search request best. The article proves motivation for the use of basic principles of fuzzy systems principles when selecting solutions in registers and catalogues. The article describes an algorithm of multistep decision making process for an original problem with a fixed number of steps. It also demonstrates how this system works in a data catalogue.

Keywords: systematization, catalogue of services, data search, fuzzy systems theory, multistep task solving.

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

Существует огромное количество решателей, доступ к которым из-за их сложной организации часто нельзя осуществить. Для обеспечения пользователю возможности применять существующие разработки, знакомиться с опытом их использования, оценивать степень возможности применения того или иного сервиса для решения возникшей задачи создаются отдельные каталоги сервисов по различным предметным областям, такие как Mathtree - древовидный каталог математических интернет-ресурсов, разработанный Институтом систем информатики им. А.П. Ершова СО РАН [1]; проект Wolfram MathWorld, в котором, кроме энциклопедических данных, пользователям сайта предоставляется возможность решать несложные математические задачи [2]; проект nigma [3]; каталоги различных сервисов [4, 5] и др.

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

проблемных) классификаторов научно-технической информации. Кроме того, существует ряд требований, определяемых ГОСТами ISO 8000 (ГОСТ Р ИСО 8000) «Качество данных», ISO 22745 (ГОСТ Р ИСО 22745) «Системы промышленной автоматизации и их интеграция. Открытые технические словари и их применение к основным данным» и др.

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

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

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

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

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

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

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

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

Многошаговый алгоритм процесса принятия решений при поиске альтернатив в информационном каталоге

Пусть множество Х={х} - каталог сервисов {хь Х2, ... , Хп }. Нечеткое множество Ух={ух} содержит семантическое описание каждого сервиса каталога, а Нх={^} - параметрическое описание сервисов (рис. 2).

Запрос к системе (рис. 3) формулируется в семантическом виде, состоит из множества термов из поисковой строки Zx1={zx1}, дополнительного множества слов-синонимов Zx2={zx2}, дополнительного множества схожих по значению и близких по смыслу слов Zx3={zx3} и составляет множество Zx={Zx} или Zx=ZxlUZx2UZx3.

Пользователь

_ Запрос

| к системе

Альтернативы Система

--— Сервисы-решатели

Рис. 1. Постановка задачи многошагового процесса принятия решения в общем виде

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

Введем множество соответствия /.^{/д;}, где О^/'^! включающее в себя индексы соответствия заданного описания объектов Yx={yx} запрашиваемому Zx={zx} и формируемое в результате вычисления степени совпадения содержания пользовательского запроса и семантического описания сервисов в реестре. Сервисы с наименьшим индексом соответствия не рассматриваются, поэтому целесообразно ограничить множество /с требуемым процентным выражением сходства семантического описания ах. Используя идентификатор сервиса в множестве /x|a,x множества /х, в результате ограничения исходного множества Х={х} получаем множество Х/^сХ

Системный электронный

Семантическое описание

Рис. 2. Упрощенная схема структуры каталога

Запрос к системе: множество

множество термов из поисковой строки

={2Х1}

множество слов-синонимов

2x2 ={2x2}

множество схожих по значению слов

2х3 ={2хз}

Рис. 3. Формирование семантического множества искомых альтернатив

Следующий шаг реализуется в случае, когда ограничения /х|ах недостаточно. Кроме стандартного повторения процедуры формирования множества соответствия 1Х и множества Х1х\ах на основе корректировки семантического множества искомых альтернатив 1Х и ограничений аХ, возможно формирование уточняющего семантического множества ВХ, с помощью которого не нужно полностью переформулировать запрос к системе. Достаточно ввести некоторые уточнения при поиске необходимых решателей в уже сформированном множестве. Результатом данного этапа является множество Х1х\ах\ъх. Если данный этап работы с системой пропущен, множество Х1х\ах\Ьх=Х1х\ах.

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

После сравнения данных, содержащихся в множестве параметрического описания сервисов Нх, с искомыми требованиями формируется множество СхоНх. Возможно формирование ранжированного списка сервисов, содержащихся в множе-

стве ^!х\ах\ьх =^!х\ах, в соответствии с заданными параметрами. Далее множество Х/х\ах\Ьх ограничивается системой параметров СхоНх.

Результатом решения поставленной задачи является множество Dx=X^x|ax|bxnСxnHХ), представляющее собой пересечение целей и ограничений.

На рисунке 4 отображена схема работы системы многошагового процесса принятия решений.

Программная реализация

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

Рис. 4. Схема функционирования системы многошагового процесса принятия решений

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

Техническая реализация сайта выполнена с помощью средств PHP и БД MySQL.

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

В настоящее время в ТвГТУ в рамках проекта «Интеллектуальная распределенная система информационной поддержки инноваций в науке и образовании» ведется разработка информационной системы оценки инновационных проектов, которая позволит проанализировать предлагаемые варианты решений стоящей перед пользователем задачи и сделать вывод о целесообразности применения данного сервиса на практике.

Литература

1. Каталог математических интернет-ресурсов. URL: http://www.mathtree.ru (дата обращения: 06.05.2013).

2. Проект Wolfram Mathworld. URL: http://mathworld. wolfram.com (дата обращения: 06.05.2013).

3. Проект Нигма.РФ, раздел «Математика». URL: http:// www.nigma.ru/index.php?t=math& (дата обращения: 06.05.2013).

4. Проект Biocatalogue. URL: http://www.biocatalogue.org/ (дата обращения: 06.05.2013).

5. Проект Programmable web. URL: http://www.program-mableweb.com/ (дата обращения: 06.05.2013).

6. Декларация о международных принципах каталогизации. URL: http://www.ifla.org/files/cataloguing/icp/icp_2009-ru.pdf (дата обращения: 06.05.2013).

7. Беллман Р., Заде Л. Принятие решений в расплывчатых условиях. М.: Мир, 1976. 46 с.

8. Проект MathCloud. URL: http://mathcloud.org/ru/ (дата обращения: 06.05.2013).

9. Астафьев А.С., Афанасьев А.П., Лазарев И.В., Сухоро-слов О.В., Тарасов А.С. Научная сервис-ориентированная среда на основе технологий Web и распределенных вычислений // Научный сервис в сети Интернет: масштабируемость, параллельность, эффективность: тр. Всерос. суперкомп. конф. (21-26 сентября 2009 г., Новороссийск). М.: Изд-во МГУ, 2009. С. 463-467.

10. Сухорослов О.В. Унифицированный интерфейс доступа к алгоритмическим сервисам в Web // Проблемы вычислений в распределенной среде: тр. ИСА РАН. М.: КРАСАНД, 2009. Т. 46. С. 60-82.

11. Палюх Б.В., Егерева И.А. Методы классификации вычислительных сервисов // Вестн. ТвГТУ. 2012. Вып. 20. С. 14-19.

References

1. Katalog matematicheskikh internet resursov [The catalog of mathematical Internet resources], available at: http://www.math-tree.ru (accessed 6 May 2013).

2. Wolfram Mathworld Project, available at: http://math-world.wolfram.com (accessed 6 May 2013).

3. Nigma.RF Project, available at: http://www.nigma.ru/in-dex.php?t=math& (accessed 6 May 2013).

4. Biocatalogue Project, available at: http://www.biocata-logue.org/ (accessed 6 May 2013).

5. Programmable web Project, available at: http://www.pro-grammableweb.com/ (accessed 6 May 2013).

6. Deklaratsiya o mezhdunarodnykh printsipakh katalogiza-tsii [Notice on the int. principles of cataloguing], available at: http://www.ifla.org/files/cataloguing/icp/icp_2009-ru.pdf (accessed 6 May 2013).

7. Bellman R., Zade L., Prinyatie resheniy v rasplyvchatykh usloviyakh [Decision making under fuzzy conditions], Moscow, Mir, 1976.

8. MathCloud Project, available at: http://mathcloud.org/ru/ (accessed 6 May 2013).

9. Astafyev A.S., Afanasyev A.P., Lazarev I.V., Sukhoroslov O.V., Tarasov A.S., Trudy Vseros. superkomp. konf. "Nauchny servis v seti Internet: masshtabiruemost, parallelnost, effektivnost" [Proc. all Russian supercomp. conf. "Internet scientific service: scalability, concurrency, efficiency"], Moscow, Lomonosov MSU Publ., 2009, pp. 463-467.

10. Sukhoroslov O.V., Trudy ISA RAN [Proc. of ISA RAS], Vol. 46, Moscow, KRASAND, 2009, pp. 60-82.

11. Palyukh B.V., Egereva I.A., Vestnik TvGTU [The bulletin of TSTU], 2012, iss. 20, pp. 14-19.

НИИ «Центрпрограммсистем»

осуществляет полный цикл исследований, проектирования, разработки и внедрения информационных систем:

- разработка тренажеров, тренажерных комплексов и автоматизированных систем обучения;

- разработка автоматизированных систем управления техническим обеспечением;

- автоматизация морской спасательной деятельности;

- моделирование сложных технических объектов;

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

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

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

- издание печатной продукции, в том числе международного журнала «Программные продукты и системы».

Адрес: 170024, г. Тверь, пр-т 50 лет Октября, д. 3а Сайт: www.cps.tver.ru

Телефон: +7 (4822) 44-32-44. Факс: +7 (4822) 39-91-00 Электронная почта: info@cps.tver.ru