WWW.NET.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Интернет ресурсы
 

Pages:     | 1 | 2 || 4 | 5 |   ...   | 6 |

«ПРОЦЕССЫ УПРАВЛЕНИЯ И УСТОЙЧИВОСТЬ ТРУДЫ XLIII МЕЖДУНАРОДНОЙ НАУЧНОЙ КОНФЕРЕНЦИИ АСПИРАНТОВ И СТУДЕНТОВ Санкт-Петербург 2 – 5 апреля 2012 года ИЗДАТЕЛЬСТВО САНКТ-ПЕТЕРБУРГСКОГО ...»

-- [ Страница 3 ] --

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

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

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

Литература

1. Green William H. Economertic analisys. Fifth edition // USA:

Prentice Hall, 2001. P. 663–755.

2. Сайт всероссийского общества профилактики аритмии.

http://aritmija.org/category/vidy-aritmii/fibrillyatsiya

3. Long J. Scott. Regression models for categorical and limited dependent variables // USA: SAGE Publications, 1997. P. 34–83.

Лакрисенко П. А.

Санкт-Петербургский государственный университет

Об ограниченности решений системы Лотки Вольтерры с переключениями

Рекомендовано к публикации профессором Александровым А. Ю.

Введение. Под системой с переключениями подразумевается система, состоящая из семейства подсистем и правила, определяющего переключения между ними [1].

Математически система с переключениями может быть описана системой дифференциальных уравнений вида

x = f (x), (1)

где x Rn ; { fp : p P } семейство достаточно регулярных функций, действующих из Rn в Rn, параметризованное некоторым набором индексов P ; : [0, ) P кусочно-постоянная функция времени, называемая сигналом переключения. В некоторых ситуациях значение в данный момент времени t может зависеть, например, только от t или x(t), или и от t, и от x(t).

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

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

Но это условие не является достаточным. Данная проблема хорошо изучена для линейных систем с переключениями [1].

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

Постановка задачи. Рассмотрим систему

–  –  –

x = 2x 0, 01xy, x = 2x 0, 02xy, y = y + 0, 03xy, y = y + 0, 01xy.

Можно применить теорему 1. Следовательно, у рассматриваемой системы существуют неограниченные решения. При c1 = 11 траектория системы с переключениями будет иметь вид, представленный на рис. 1.

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

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

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

Рис. 1. Траектория системы с переключениями

Литература

1. Liberzon D., Morse A. S. Basic problems in stability and design of switched systems // Control System Magazine, IEEE, 1999. Vol. 19, No. 5. P. 59–70.

2. Decarlo R. A., Branicky M. S., Petterson S., Lennartson B.

Perspectives and results on the stability and stabilizability of hybrid systems // Proc. of the IEEE, 2000. Vol. 88, No. 7. P. 1069–1082.

3. Вольтерра В. Математическая теория борьбы за существование.

М.: Наука, 1976. 287 с.

Мамочев В. А.

Санкт-Петербургский государственный университет

–  –  –

Рекомендовано к публикации доцентом Тамасяном Г. Ш.

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

Даны два конечных множества точек A, B Rn,

A = {a1,..., ak }, B = {b1,..., bl }.

Требуется как можно лучше (в некотором смысле) разделить точки этих множеств. Обычно для этого выбирается функция f (называемая идентификатором) из некоторого семейства функций (идентификаторов) F.

Идентификация проводится следующим образом. Возьмем точку x из множества A B. Если f (x) 0, то считаем, что x принадлежит множеству A, если же f (x) 0, то считаем, что x принадлежит множеству B. Может оказаться, что точка x идентифицирована неверно.

Функция f выбирается из класса функций F оптимальным в некотором смысле образом (например, так, чтобы количество неверно идентифицированных точек было наименьшим). В настоящей работе для разделения двух множеств оптимальный идентификатор строится по правилу, описанному в работе [1].

Рассмотрим теперь задачу разделения не двух, а трёх множеств.

Для решения этой задачи предлагается следующий метод.

Даны три конечных множества A, B, C Rn,

–  –  –

Вначале решим задачи разделения следующих трёх пар множеств:

A от B C, B от A C и C от A B. Для этого, например, можно В таблице 1 в первых трех столбцах указаны результаты идентификации по каждому из трех выбранных методов идентификации.

Знак + в первом столбце означает, что первый метод идентифицировал точку как точку множества A. Знак + во втором столбце означает, что второй метод идентифицировал эту же точку как точку множества B.

Далее будем называть строки в столбцах 1–3 комбинациями.

Столбцы 4–6 содержат информацию о том, сколько точек из данного множества оказались в группе с такой комбинацией. Так, значение b2 в столбце 5 означает, что b2 точек из множества B имеют комбинацию + + –. Значения в столбцах 7–9 являются отношениями соответствующих значений из столбцов 4–6 к количеству точек в этих столбцах. Так, к примеру, B1 равно b1 /k, т. е. отношение значения из столбца b к количеству точек в множестве B.

В столбце 10 ( ) стоят суммарные значения по этой строке из столбцов 7–9. В столбцах 11–13 (Q, R, Z) стоят отношения значения в столбце 7–9 к суммарному значению из столбца 10 (т. е.

qi = Ai /si, ri = Bi /si, zi = Ci /si ).

3. Иллюстрация метода. Проиллюстрируем применение описанного подхода на примере обработки баз данных, предоставленных студентом БГТУ ВОЕНМЕХ П. Главновым. База данных состоит из 29 пациентов множества A, 33 пациентов множества B, 22 пациентов множества C. Каждый пациент характеризуется точкой в 23-мерном пространстве (пространство параметров). Множество A представляет собой множество пациентов с рецидивом заболевания меньше 1 раза в год, B от 1 до 3 раз в год, а C больше 3 раз в год.

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

Нахождение этих наборов происходит с помощью программного комплекса [1]. Лучшие результаты идентификации дали функционалы, использующие наборы параметров (3, 5, 13, 20), (7, 8, 15, 16) и (10, 13, 14, 23). Например, набор (3, 5, 13, 20) состоит из номеров столбцов в базе данных, соответствующих таким параметрам, как интенсивность болей, провоцирующий фактор, концентрация гемоглобина, национальность; (7, 8, 15, 16) форма стула, наличие патологических примесей в кале, количество сегментоядерных и палочкоядерных элементов крови; (10, 13, 14, 23) концентрация электроцитов, концентрация гемоглобина, тромбоциты, курение.

Как видно из таблицы 2, если получилась комбинация + – –, то с вероятностью 0,84 данный пациент принадлежит множеству A, c вероятностью 0,09 множеству B и с вероятностью 0,07 множеству C.

Таблица 2. Точность идентификации на примере базы БГТУ a b c ai bi ci A B C Q R Z + + + 0 0 0 0 0 0 0 - - Вывод.

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

Литература

1. Мамочев В. А. Применение статистического метода в задаче классификации // Процессы управления и устойчивость: Труды 42-й международной научной конференции аспирантов и студентов / Под ред. А. С. Ерёмина, Н. В. Смирнова. СПб.: Издат. Дом.

С.-Петерб. гос. ун-та, 2011. С. 245–248.

2. Иголкин В. Н., Ковригин Ф. Б. и др. Статистическая классификация, основанная на выборочных распределениях. Л.: Изд-во ЛГУ, 1978. 102 с.

Морозов П. Д.

Санкт-Петербургский государственный университет Одно дискретное вейвлет-преобразование акустического сигнала Рекомендовано к публикации профессором Михеевым С. Е.

Введение. Преобразование Фурье дает частотно-амплитудное представление сигнала. Однако при работе с нестационарными сигналами оно не позволяет определить время существования той или иной частоты [1]. В этом случае обращаются к частотно-временному представлению сигнала. К такому типу преобразований и относится вейвлет-преобразование (ВП). Оно в некотором смысле решает проблему плохого разрешения: на высоких частотах лучше разрешение по времени, на низких по частоте. ВП использует параметры масштаба s и сдвига. Само ВП в непрерывном случае определяется по формуле 1 t (, s) = x(t) dt, x |s| s где оператор комплексного сопряжения, (t) функция преобразования, именуемая материнским вейвлетом.

Вычисление. На рис. 1 показан вид использовавшегося в данной работе материнского вейвлета Мексиканская шляпа, который t2 задаётся формулой (t) = (1 t2 )e 2.

–  –  –

В программном виде дискретизация согласно приводимым выше формулам проводилась в виде следующего основного блока (реализация выполнена на С++):

for (int t = 0; t SIZE; t++) {x =.0;

for (int j = 1; j 9; j++) {float s = pow(s0, j);

for (int k = 0; k SIZE/(s*t0); k++) {W =.0;

Phi_i = exp(-(-1+(k+1)*s*t0)*(-1+(k+1) *s*t0)/(2*s*s))- (k+1)*s*t0*exp(-(-1+(k+1) *s*t0)*(-1+(k+1)*s*t0)/(2*s*s));

for (int i = 0; i SIZE; i++) {Phi_i1 = (i+1) *exp(-(-(i+1)+(k+1)*s*t0) *(-(i+1)+(k+1)*s*t0)/(2*s*s)) - (k+1)*s*t0 *exp(-(-(i+1)+(k+1)*s*t0)*(-(i+1)+(k+1) *s*t0)/(2*s*s));

W += WorkR[i] * (Phi_i1-Phi_i); Phi_i = Phi_i1;

};

psi_jk = 1 / sqrt(s) * (1-(t/s-k*t0)*(t/s-k*t0)) *exp(-(t/s-k*t0)*(t/s-k*t0)/2);

x += W * psi_jk / s;

};

};

Out[t] = x;

};

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

Рис. 2. Входной и восстановленный сигналы

Литература

1. Камачкин А. М., Михеев С. Е., Евстафьева В. В. Модели колебаний в нелинейных системах. СПб.: Изд-во СПбГУ, 2004. 194 с.

2. Козлов П. В., Чен Б. Б. Вейвлет-преобразование и анализ временных рядов // Вестник КРСУ, № 2, 2002.

http://www.krsu.edu.kg/vestnik/2002/v2/a15.html.

3. Polikar R. An introduction to wavelets // IEEE Computational Sciences and Engineering, 1995. Vol. 2, No 2. P. 50–61.

Морозов П. Д., Михеев В. С.

Санкт-Петербургский государственный университет

Выявление пороговых значений слышимости речи при амплитудной модуляции

Рекомендовано к публикации профессором Михеевым С. Е.

Введение. Амплитудной модуляцией в радиотехнике называется такое кодирование звукового сигнала в радиоволны, при котором амплитуда гармонического электромагнитного колебания несущего сигнала есть линейная функция звукового давления входного сигнала (амплитуда переходит в амплитуду; при частотной модуляции, соответственно, амплитуда переходит в частоту) [1].

Если представить шепотную речь как модуляцию некоторого гортанного шипения-шума, то данное шипение окажется смесью высокочастотных колебаний. В справедливости подобного представления можно без труда удостовериться, исходя непосредственно из графиков визуализированного базового (несущего) шипения, оцифрованного с помощью стандартных аналого-цифровых преобразователей, встроенных в обычные персональные компьютеры. Использование звукового редактора Sound Forge 7.0 с целью выявления частотного анализа базового шипения позволило обнаружить наличие частот, превышающих 10 кГц. Вследствие чего возник интерес к модуляции акустического сигнала на акустическом же гармоническом несущем сигнале высокой частоты для установления различимости (человеческим ухом) входной информации в выходном сигнале, как при частотной, так и при амплитудной модуляции. Между простым сложением сигналов и амплитудной модуляцией имеется различие (рис. 1). Проводимые эксперименты были связаны с распознаванием сигнала после применения амплитудной (частотной) модуляции не на электромагнитных, а на акустических гармонических колебаниях высокой частоты. Эксперименты проводились для определения пороговых значений слышимости и понимания речи человеческим ухом.

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

Описание экспериментов. Основа стимульного материала была составлена из десяти предложений, длительность зачитывания которых была около двух секунд при темпе, близком к темпу зачиРис. 1. Схематическое сравнение сложения сигналов (а) и амплитудной модуляции (б) тывания новостей по телевизору. Согласно [2], высокий голос обладает лучшей различимостью, нежели низкий, поэтому пять предложений зачитывались низким голосом (мужским), пять других высоким (женским) и записывались в выходные WAV-файлы. Далее программно генерировался гармонический несущий сигнал частотой от 10 до 14 кГц с частотой дискретизации 192000 Гц. В первой серии экспериментов происходила амплитудная модуляция: входные WAVфайлы накладывались на амплитуду несущего сигнала, результаты записывались в выходные WAV-файлы. Во второй серии экспериментов результаты накладывались на частоту несущего сигнала, образуя, тем самым, фазопериодические функции [3]. Стимульный материал появлялся после воспроизведения выходных WAV-файлов с помощью описанного ниже аппаратного и программного обеспечения.

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

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

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

Фразы:

1. Сам процесс ввода публикаций не вполне тривиален.

2. В будущем это может отразиться на размерах стимула.

3. Серьезно отнеситесь к организации выполнения работы.

4. Сегодня из девяти человек, которые работают в компании...

5. Наши программисты трезво оценивают свои возможности.

Аппаратное и программное обеспечение. В наличии имелась аппаратура: PC Genuine Intel(R) CPU 2160 @ 1,80 ГГц, Sound Blaster, динамики UTT SP-80, конденсаторный микрофон Dialog M-110 с частотным диапазоном 50–16000 Гц. Она позволяла генерировать различимый звук лишь до частот порядка 14 кГц. Поэтому, несмотря на возможность программного инструментария как личного, так и фирменных звуковых редакторов создавать файлы, которые могли бы на соответствующей аппаратуре порождать звуки до 96 кГц, и интересный диапазон слышимых более высоких звуков 1420 кГц, и неслышимый ультразвуковой 20 48 кГц остались неисследованными. Для исследования фразы записывались с помощью микрофона и звукового редактора Sound Forge 7.0 в WAV-файл. Формат WAV был выбран в силу простоты структуры, а также как содержащий информацию о звуковом давлении в виде простой оцифровки усредненного давления на фиксированном временном интервале, называемом сэмплом [4].

Частота дискретизации для входного сигнала, т. е. количество измерений звукового давления в секунду (иными словами, количество сэмплов в секунде), было выбрано равным 48 кГц.

Результаты. Периоды несущего сигнала выбирались от 6 до 42 сэмплов, что для выходного сигнала при частоте дискретизации 192 кГц соответствовало частотам от 32 до 4,6 (кГц). Вероятность распознавания при частотной модуляции на всех частотах несущего сигнала оказалась 0% (ни единого слова). При амплитудной модуляции фразы были вполне различимы. Все испытуемые успешно справились с распознаванием при периодах несущего сигнала от 10 до 22 сэмплов, т. е. частотах от 19,2 кГц до 8,7 кГц, уровень опознания составил 100%. Частичная различимость была для периода 9 и периодов от 23 до 37 сэмплов (80% и 75–60%, соответственно). Для прочих периодов несущего сигнала наступала полная неразличимость (0%).

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

При амплитудной модуляции фактически единственной составляющей звукового сигнала является несущая высокая частота, поэтому априори можно было бы предполагать отсутствие слышимости на существенно более низких частотах. В нашем эксперименте несущая частота (от 10 до 14 кГц) не менее чем в 100 раз превосходила основную частоту участвующего в эксперименте мужского голоса (100 Гц), в 29,5 женского (340 Гц). Тем не менее, после модулирования сохранялась различимость сигнала.

Литература

1. Стеценко О. А. Радиотехнические цепи и сигналы. М.: Высшая школа, 2007. 432 с.

2. Самойлов В. О. Медицинская биофизика. СПб.: Спецлит, 2007.

560 с.

3. Камачкин А. М., Михеев С. Е., Евстафьева В. В. Модели колебаний в нелинейных системах. СПб.: Изд-во СПбГУ, 2004. 194 с.

4. Михеев С. Е. Нелинейные методы в оптимизации. СПб.: Изд-во СПбГУ, 2001. 276 с.

Никитина И. П., Губар Е. А.

Санкт-Петербургский государственный университет Развитие эпидемического процесса в группах риска с учетом структуры популяции

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

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

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

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

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

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

2. Постановка задачи. Рассмотрим эволюционную модель развития эпидемического процесса для основной массы населения и выделенной группы риска. В дальнейшем представителей подгрупп будем называть игроками. В данной постановке стратегия также является состоянием игрока. Обозначим через K r = {S, I, R | S r, I r, Rr } множество всех чистых стратегий, где S стратегия восприимчивых, I инфицированных и R иммунных. Обозначим через ei, ej K r чистые стратегии, через xi = ni /N, i = 1, 6, долю индивидуумов из общей массы населения, использующих чистую стратегию ei, где ni количество индивидуумов, использующих стратегию ei, N = ni ; x = (xS, xI, xR ), xr = (xr, xr, xr ) вектор состояний S I R для основной массы населения и для группы риска соответственно.

Через X = {x|xr } обозначим вектор состояний всей популяции [2].

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

–  –  –

• итерации повторяются пока доля инфицированных игроков не станет равной нулю.

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

–  –  –

5. Заключение. Из проведенных вычислений видно, что при высокой контактности с инфицированными игроками эпидемический процесс протекает быстрее. Однако при увеличении интенсивности перехода из подгруппы восприимчивые в подгруппу инфицированных момент начала подъема эпидемии наступает раньше при том же значении контактности. Из приведенных выше таблиц видно, что с течением времени доля индивидуумов, входящих в подгруппу иммунные возрастает. Таким образом можно предположить, что состояние иммунные является устойчивым. В данном примере была проведена проверка эволюционной устойчивости стратегий с помощью механизма G-функции (Fitness-generating function) [4], которая определяется следующим образом:

u(ei, ej )xj, G(V, K, X)|V =ei = j=1 T где u(ei, ej ) = ei Aej математическое ожидание выигрыша, A матрица выигрышей, V виртуальная стратегия, принадлежащая множеству K r. Группа риска и основная масса населения представлены каждая своей функцией Gk. Для группы риска и основной массы населения не было получено эволюционно устойчивых стратегий, но получена нейтральная устойчивость стратегий восприимчивый и иммунный.

–  –  –

1. Губар Е. А., Житкова Е. М. Стабильность популяции в случае сезонного подъема заболеваемости ОРВИ // Устойчивость и процессы управления. Всероссийская конференция, посвященная 80летию со дня рождения В.И. Зубова. СПб.: ВВМ, 2010. С. 144–145.

2. Weibull J. Evolutionary game theory. Cambridge: The MIT Press, 1995. 265 p.

3. Feng Fu, Daniel I. Rosenbloom, Long Wang, Martin A. Nowak.

Imitation dynamics of vaccination behaviour on social networks // Proc. R. Soc. B. 278, 2011. P. 42–49.

4. Vincent T. L., Brown J. S. Evolutionary game theory, natural selection, and darwinian dynamics. Cambridge University Press, 2005.

382 p.

Сударев О. И.

Санкт-Петербургский государственный университет Анализ исходных данных пациентов до ресинхронизирующей терапии Рекомендовано к публикации профессором Котиной Е. Д.

Введение. В настоящее время научная деятельность в медицине, биологии, физике, технике, информатике и других областях науки тесно связана с анализом больших массивов данных. Часто требуется установить взаимосвязь между различными компонентами таких массивов, используя математические методы. Данная задача часто решается в медицине при постановке диагнозов и планировании лечения. Ресинхронизирующая терапия (РСТ) способна принести успех в лечении больных, находящихся в конечной стадии сердечной недостаточности. Положительные изменения со стороны основных параметров гемодинамики и ремоделирования левого желудочка не отмечены у 40–50% больных, подвергнутых РСТ. Актуальной является задача улучшения отбора больных на РСТ [1]. Данная статья продолжает исследование в этом направлении: рассматривается обновленная база данных пациентов, предлагается качественноколичественная сравнительная оценка всех исходных данных, применяется непараметрический критерий серий Вальда Вольфовица.

Постановка задачи. Имеется база исследований по больным сердечной недостаточностью, которым выполняли ресинхронизирующую терапию (всего 53 пациента). Для каждого пациента было проведено несколько исследований. Во время каждого исследования было измерено 96 медицинских показателей, полученных несколькими способами: клинические данные (рост, вес, давление, ЭКГ и т. д.); данные, полученные при помощи эхокардиографии; данные, полученные при помощи однофотонной эмиссионной компьютерной томографии (SPECT) и обработанные программой КАРФИ [2].

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

• 1 группа пациенты с неблагополучными результатами лечения (12 человек);

• 2 группа пациенты с благополучными результатами, у которых к последнему исследованию фракция выброса левого желудочка (ФВ ЛЖ) составила больше 40% (14 человек);

• 3 группа пациенты, у которых прирост ФВ ЛЖ составил больше 10% (7 человек);

• 4 группой назовем пациентов 2 и 3 групп, взятых вместе.

Обозначим пациентов первой группы f 11, f 12, f 13 и т. д, пациентов второй группы f 21, f 22, f 23 и т. д., пациентов третьей группы f 31, f 32, f 33 и т. д. Измеряемые медицинские показатели обозначим x1, x2, x3 и т. д. Таким образом, запись f 1i (xj ) будет означать значение xj -го показателя для i-го пациента первой группы. Необходимо провести анализ исходных данных (данных, полученных до ресинхронизирующей терапии), представить их в наглядной форме, выделить значимые различия в исходных результатах обследования выделенных групп, особенно больных благополучной и неблагополучной групп.

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

Заметим, что различные медицинские показатели имеют различные единицы измерения и различный диапазон допустимых значений.

Естественным подходом будет сравнение с благополучной группой остальных групп.

С этой целью нормируем исходные данные следующим образом:

f 1i = (f 1i (xj ) min f 2k (xj ))/ max f 2k (xj ), f 2i = (f 2i (xj ) min f 2k (xj ))/ max f 2k (xj ), f 3i = (f 3i (xj ) min f 2k (xj ))/ max f 2k (xj ).

Заметим, что в результате данных преобразований все нормированные значения параметров пациентов второй группы f 2i (xj ), i = 1,..., 96 лежат внутри отрезка [0, 1]. При этом нормированные значения параметров пациентов из 1 и 3 групп выходят за пределы интервала [0, 1]. Оценивая количественно процент выброса за пределы отрезка [0, 1] для пациента № 5 из группы 1, получаем 22,97% (см. рис. 1).

Оценив количество значений, располагающихся за пределами отрезка [0, 1], для групп 1 и 3 получим следующие результаты:

– в неблагополучной группе в среднем 14,31% значений лежат за границами интервала [0, 1];

– в группе с приростом ФВ ЛЖ 10% в среднем 10,56% значений лежат за границами интервала [0, 1].

Рис. 1. Нормированные параметры пациента № 5 из первой группы Применение непараметрических критериев. Для выявления параметров, по которым различаются группы 1–4 будем использовать непараметрические критерии.

U-критерий Манна Уитни статистический критерий, применяемый для оценки различий между двумя независимыми выборками по уровню какого-либо признака, измеренного количественно.

Выборкой в данном исследовании является набор данных конкретного медицинского показателя из конкретной группы [3–5].

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

Сущность критерия состоит в отыскании различия в характере распределения двух выборок [4, 5].

Основной гипотезой (обозначаемой H0 ) для использования этих статистических критериев является предположение об однородности двух выборок, то есть о том, что эти две выборки извлечены из одной генеральной совокупности. Альтернативная гипотеза H1 заключается в том, что две выборки извлечены из разных генеральных совокупностей. Каждый критерий применяется при заданном уровне значимости или вероятности ошибки первого рода, то есть вероятности того, что отвергается основная гипотеза H0 в то время, когда она верна [4–6].

Задав уровень значимости равным 0,05 и используя в качестве параметра значения медицинских показателей, получаем следующие результаты.

При помощи U-критерия Манна Уитни:

• для групп 1 и 2 можно принять гипотезу о различии между параметрами LV RV lat, LV lat Sept, LCX perf, коэффициент асимметрии rv;

• для групп 1 и 4 можно принять гипотезу о различии между параметрами LV RV lat, коэффициент асимметрии rv, Bandwidth rv;

• для групп 1 и 3 можно принять гипотезу о различии между параметрами: коэффициент aсимметрии rv, ES time, 6 min walk.

Наглядно эти результаты представлены на рис. 2.

Рис. 2. p-уровни медицинских параметров, выделенных при помощи критерия Манна Уитни

При помощи критерия серий Вальда Вольфовица были получены следующие результаты (см. рис. 3):

• для групп 1 и 2 можно принять гипотезу о различии между параметрами LV RV lat, Rthic-perf, EDV RV, PER LV, FF1/3 LV;

• для групп 1 и 4 можно принять гипотезу о различии между параметрами Rthic-perf, EDV RV, ES time;

• для групп 1 и 3 можно принять гипотезу о различии между параметрами 6 min walk, r-EF QGS, TOT thick, RFR RV.

Заключение. В результате исследований были выделены следующие медицинские показатели: LV RV lat, 6 min walk, ES time, коэффициент асимметрии rv, EDV RV, Rthic-perf.

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

Рис. 3. p-уровни медицинских параметров, выделенных при помощи критерия серий Вальда Вольфовица Литература

1. Слободяник В. В., Тонкошкурова В. В., Котина Е. Д. и др. Перфузионная томосцинтиграфия миокарда синхронизированная с ЭКГ и ресинхронизирующая терапия // Тезисы докладов Научнопрактической конференции Актуальные проблемы ядерной медицины, 2011. С. 37.

2. Котина Е. Д., Овсянников Д. А., Остроумов Е. Н., Плоских В. А.

Свидетельство об официальной регистрации программы для ЭВМ №2010613281 Программа построения кардиологических функциональных изображений (КАРФИ).

3. Реброва О. Ю. Статистический анализ медицинских данных.

Применение пакета прикладных программ STATISTICA. М.: МедиаСфера, 2002. 312 с.

4. Руниор Р. Справочник по непараметрической статистике: Современный подход. М.: Финансы и статистика, 1982. 192 с.

5. Малета Ю. С., Тарасов В. В. Непараметрические методы статистического анализа в биологии и медицине. М.: МГУ, 1982. 178 с.

6. Гублер Е. В., Генкин А. А. Применение непараметрических критериев статистики в медико-биологических исследованиях. Л.: Медицина, 1973. 140 с.

Фотина Л. А., Губар Е. А.

Санкт-Петербургский государственный университет Влияние вакцинации на развитие эпидемического процесса в структурированной популяции

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

Общая масса городского населения разделяется на три основные подгруппы: люди, восприимчивые к вирусу, инфицированные и иммунные. В данной работе рассматривается ситуация, в которой учитываются затраты на вакцинацию, проведенную в подгруппе восприимчивые, и затраты на лечение в подгруппе инфицированные [1].

2. Постановка задачи. Построим математическую модель развития эпидемического процесса с использованием методов эволюционной теории игр. Стратегиями будут являться состояния, в которых находятся индивидуумы в текущий момент времени. Обозначим через K = {S, I, R} множество всех чистых стратегий, где S чистая стратегия восприимчивых, I инфицированных, R иммунных.

Для простоты изложения в данной постановке задачи будем называть индивидуумов игроками. Предполагается, что игроки из каждой трех подгрупп могут взаимодействовать между собой случайным образом, и их взаимодействие может быть описано симметричной игрой двух лиц. Обозначим через ei, ej K чистые стратегии игроков. Тогда xi = ni /N, i = 1, 3, доля индивидуумов из общей массы населения, использующих чистую стратегию ei, где ni, количество индивидуумов, использующих стратегию ei, N = ni, а x = (xS, xI, xR ) частотный вектор (вектор состояний всей популяn ции). Пусть = {(x1,..., xn )| xi = 1, xi 0} множество всех j=1 состояний популяции [2].

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

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

–  –  –

Определение 2. Матричная экологически равновесная точка x является матричным экологически-стабильным равновесием (матричным ESE) [2], если существует окрестность с центром в этой точке такая, что для некоторой точки x(0) решение, получаемое из динамики, удовлетворяет условию x(t) для всех t 0 и асимптотически стремится к x при t.

Определение 3. Стратегия ei K является эволюционно устойчивой стратегией в классе матричных игр (матричное ESS) [2] для равновесной точки x, если для всех n 1 и для всех стратегий ej K, j = i, равновесная точка x матричное ESE.

Теорема. (Достаточное условие для матричного ESS). Пусть матричная игра определена уравнением динамики. Если n = 1 и ei удовлетворяет принципу максимума ESS [2], т. е. функция

G(V, K, x ) принимает максимальное значение при V = ei, V K:

maxV K G(V, K, x ) = G(V, K, x)|V =ei = u(x, x ), то ei будет матричной ESS.

3. Численный эксперимент. Проведем численное моделирование эпидемического процесса с использованием основных определений раздела 2 при следующих значениях параметров: = 1; q = 0,05;

c = 0,8; = 0,5; = 0,9; = 0,875; = 0,05.

На примере чистой стратегии S = (1, 0, 0) покажем как использовать G-функцию для нахождения матричного ESS, при этом x = (1, 0, 0) равновесная точка.

–  –  –

Из рис.1 видно, что траектории решений сходятся к точке R, что соответствует чистой стратегии R = (0, 0, 1). Это означает, что данная стратегия будет являться эволюционно устойчивой [3], что, в свою очередь, подтверждает результат, полученный с использованием G-функции.

4. Стохастическое моделирование эпидемического процесса. Одним из вариантов представления того, как будут изменяться доли населения по подгруппам во время эпидемического процесса, может служить алгоритм Гиллеспи (Gillespie) [5]:

–  –  –

• вычисления алгоритма повторяются до тех пор, пока доля инфицированных игроков не станет равной нулю.

В нашем случае интенсивность перехода из состояния восприимчивые в инфицированные и интенсивность перехода из состояния инфицированные в иммунные имеют те же значения, что и интенсивность переходов для численного эксперимента в разделе 2, но вакцинируется не вся подгруппа восприимчивые, а некоторая доля населения = 0,01.

Полученные результаты проиллюстрируем графиками:

–  –  –

5. Заключение. В результате применения алгоритма Гиллеспи при значениях параметров = 0,9, = 0,875 получаем, что при проведении вакцинации эпидемический процесс длится дольше, так как взаимодействие с инфицированными игроками происходит менее интенсивно.

–  –  –

1. Губар Е. А., Житкова Е. М. Стабильность популяции в случае сезонного подъема заболеваемости ОРВИ // Устойчивость и процессы управления. Всероссийская конференция, посвященная 80-летию со дня рождения В. И. Зубова. СПб.: ВВМ, 2010.

С. 144–145.

2. Vincent T. L., Brown J. S. Evolutionary game theory, natural selection, and darwinian dynamics. Cambridge University Press, 2005.

382 p.

3. Weibull J. Evolutionary game theory. Cambridge: The MIT Press, 1995. 265 p.

4. Sandholm W. H. Population games and evolutionary dynamics.

University of Wisconsin: MIT Press, 2010. 442 p.

5. Feng Fu, Daniel I. Rosenbloom, Long Wang, Martin A. Nowak // Imitation dynamics of vaccination behaviour on social networks.

Proc. R. Soc. B. 278, 2011. P. 42–49.

Щербакова А. А.

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

–  –  –

где AOi значение аккомодационного ответа в i-ом испытании, ACi значение аккомодационного стимула в i-ом испытании, n количество измерений, R собственная рефракция глаза, KAOi = AOi R, HF Ci i R показатель высокочастотного компоненAC та в i-ом испытании, nAO количество неотрицательных значений AO = AOi AOi1, т. е. AOi AOi1 0, i = 1,..., n.

Коэффициент KAO является математическим ожиданием KAOi, SKAO дисперсия KAOi, HF C математическое ожидание HF Ci, SHF C дисперсия HF Ci, остальные коэффициенты: KR и SurKAO не имеют физического смысла и являются дополнительными величинами для дальнейших вычислений.

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

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

2.1. Дискриминантный анализ. Основой классификации будет построение линейной дискриминантной функции вида fk,m = u0 + u1 X1,k,m +... + up Xp,k,m, где Xi,k,m величина переменной для m-го наблюдения в k-ом классе, fk,m значение канонической дискриминантной функции для m-го объекта в группе k, ui коэффициенты [2].

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

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

Одним из способов отбора информативных дискриминантных переменных является пошаговый дискриминантный анализ (ДА). Логика пошагового ДА такова: вначале определяется та переменная, для которой средние значения в априорно заданных группах наиболее различны. На каждом следующем шаге рассматриваются условные распределения оставшихся переменных и определяется та, для которой средние значения в группах наиболее различны. Процесс завершается, когда ни одна из оставшихся переменных не вносит значимого вклада в различение групп. Существуют разные критерии отбора информативных дискриминантных переменных. Каждый критерий придает особый содержательный смысл процессу различения. Наиболее популярная это статистика Уилкса, которая учитывает как различия между группами, так и однородность каждой из групп [1].

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

3. Полученные результаты. Решение задачи можно разбить на три части:

• формирование обучающей выборки, поиск аномальных наблюдений и исключение их из общей выборки;

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

• непосредственное выполнение классификации, т. е. распределение по группам с помощью имеющихся функций.

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

Дискриминантный анализ проводился по следующим двум схемам (см. рис. 1, 2).

<

–  –  –

На рис 1. 2.

обозначено: 1 норма (Н), 2 слабые устойчивые (СлУ), 3 сильные устойчивые (СУ), 4 сильные неустойчивые (СН), 5 слабые неустойчивые (СлН), 6 требуют дополнительного исследования (ТДИ).

Так как разбиение сразу на шесть групп не дает хорошего результата, то на каждом шаге проводилось разделение наблюдений на две группы (что указано на схемах). Для проведения дискриминантного анализа использовался статистический пакет SPSS [3]. Проводился дискриминантный анализ, включающий все факторы, а также пошаговый дискриминантный анализ; выбор факторов, включенных в дискриминантную функцию, производился на основе значения лямбды Уилкса. В результате было получено 20 дискриминантных функций (по пять для каждого случая), на основе которых была решена задача классификации. Можно было заметить, что на каждом шаге различные переменные дали наибольший вклад в классификацию, поэтому выделить наиболее информативные дискриминантные переменные не представляется возможным. Попытки исключения из анализа некоторых переменных также не давали улучшения результатов.

Для непосредственного разделения на группы была написана программа на языке С++, использующая исходный файл с набором коэффициентов и полученные линейные дискриминантные функции. Далее было проведено сравнение полученных групп с исходными. Наибольшая точность была получена при проведении дискриминантного анализа по схеме 2 (см. рис. 2), который для определения канонической функции использовал все дискриминантные переменные (точность 68%). Но, считая, что группы СУ и СН, а также СлУ и СлН близки, можно найти точность классификации и не принимая за ошибку неправильное распределение наблюдений по этим парам групп. Тогда наибольшая точность составляет 78%.

Результаты исследований будут применены в СПб ГУЗ ДЦ № 7 для упрощения диагностики глазных заболеваний у детей.

Литература

1. Айвазян С. A. Прикладная статистика: классификация и снижение размерности. М.: Финансы и статистика, 1989. 607 с.

2. Бессокирная Г. П. Статистические методы и анализ данных // Социология: 4М, 2003. № 16. С. 25–35.

3. Бююль А., Цефель П. SPSS: искусство обработки информации.

М.: ДиаСофт, 2005. 608 с.

4. Ким Дж. О., Мюллер Ч. У., Клекка У. Р. Факторный, дискриминантный и кластерный анализ. М.: Финансы и статистика, 1989.

215 с.

4. Информационные и компьютерные технологии Артемов А. Г.

Санкт-Петербургский государственный университет Вопросы трехмерной реконструкции объекта по двум его изображениям Рекомендовано к публикации доцентом Макеевым И. В.

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

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

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

2. Постановка задачи. Пусть имеется два цифровых изображения некоторого трехмерного объекта. Пусть найдены пары точек xi xi, i = 1,..., n. Найдем множество трехмерных точек {Xi } таких, что xi есть изображение Xi на первом изображении, xi на втором. Работать будем с однородными координатами.

В качестве математической формализации понятия камеры будем использовать стандартную модель с точечной диафрагмой (pinhole camera model) [1]. В общем случае матрица камеры имеет вид P = KR I| C, либо же f 0 px P = K [R|t], t = RC, где K = 0 f py калибровочная матрица, R матрица поворота, C вектор смещения центра камеры относительно начала мировой системы координат.

Точки xi и xi связаны xi лежит на эпиполярной линии F xi, где F матрица отображения, переводящего каждую точку одного изображения в соответствующую эпиполярную линию другого [1].

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

Фундаментальная матрица обладает следующими важными свойствами:

rank(F ) = 2, T xi F xi = 0, i = 1,..., n.

3. Алгоритм. Для решения поставленной задачи необходимо выполнить следующую последовательность шагов:

1. Найти фундаментальную матрицу F из пар связанных точек.

2. Построить матрицы камер P и P.

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

4. Реализация алгоритма. В этом пункте предлагаются подробные описания каждого шага.

4.1. Вычисление фундаментальной матрицы. Вычислять фундаментальную матрицу будем с помощью нормализованного 8-точечного алгоритма, подробно описанного в [2]. В частности:

1. Нормализация координат: xi = T xi, xi = T xi, где T нормализующее преобразование, т. e. перенос начала координат в центр тяжести и последующее сжатие, такое, что среднее расстояние до нового начала координат равно 2.

2. Поиск фундаментальной матрицы F для нормализованных координат как решения переопределенной линейной системы уравнений относительно её коэффициентов.

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

T

4. Денормализация: F = T F0 T.

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

–  –  –

4.4. Реализация. Алгоритм нахождения облака трехмерных точек был реализован на языке C++ с использованием библиотеки OpenCV 2.3.1 [4]. Снимки были получены с помощью веб-камеры Logitech HD Webcam C270. Калибровка камеры производилась также средствами библиотеки OpenCV. Для визуализации облака точек использовалась программа CloudCompare [5].

4.5. Сравнение результатов при различных zh. Исходная пара изображений c расставленными точками показана на рис. 1, полученные облака точек при различных zh на рис. 2.

Правое Левое Рис. 1. Исходные изображения

W zh = zh = 1 Рис. 2. Полученные облака точек Как видно из приведенного примера, при zh = W полученные трехмерные точки довольно точно соответствуют действительности.

При zh = 1 такого результата добиться не удалось: облако точек искажено гораздо сильнее.

Кроме того, была выявлена следующая особенность: при zh = W среднее число обусловленности однородных систем, решаемых при триангуляции, составило 121 для данного примера. При zh = 1 величина его оказывается гораздо больше (6394). Вероятно, именно поэтому погрешности, с которыми были выбраны точки, приводят к большим ошибкам при вычислении решения.

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

Литература

1. Hartley R., Zisserman A. Multiply view geometry in computer vision. 2nd edition. Cambrige University Press, Cambridge, 2003.

656 p.

2. Hartley R. In defence of 8-point algorithm.// IEEE Transaction on Pattern Recognition and Machine Intelligence, 1997. P. 580–593.

3. Richard I. Hartley and Peter Sturm. Triangulation // Computer Vision and Image Understanding Vol. 68, No. 2, 1997. P. 146–157.

4. Open Computer Vision Library. http://opencv.itseez.com/

5. CloudCompare. 3D point cloud and mesh processing software. Open Source Project. http://www.danielgm.net/cc/ Гришкин В. М., Королев А. И., Сухмель В. А., Тимошенко Д. М.

Санкт-Петербургский государственный университет

–  –  –

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

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

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

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

2.1. Предварительная обработка сигнала. Прежде чем выделять какие-либо речевые признаки, сигнал следует подвергнуть процедуре предобработки. Первоначально оценивается величина ОСШ (отношение сигнал/шум) и уровень реверберации. Затем, если указанные параметры сигнала находятся в эмпирически рассчитанных допустимых пределах (таблица 1), система переходит к этапу сегментации на участки речь/не речь. Для разметки речевых участков используется алгоритм детектирования речевой активности, который основан на двух подходах: нахождении речи по огибающей энергетической характеристики сигнала и определении границ вокализованных участков по траектории основного тона [1]. После получения разметки речевых участков считается их общая продолжительность, которая вводится как третий параметр качества записи, называемый длительностью чистой речи.

Таблица 1. Пороги оценки качества фонограммы Параметр оценки Допустимый качества полуинтервал ОСШ 10 дБ Реверберация 600 мс Длительность чистой речи 700 мс По фонограмме, полученной от диктора, осуществляется верификация, только если параметры качества речевой записи будут находиться в полуинтервалах из таблицы 1.

В противном случае система отказывается верифицировать диктора.

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

В качестве речевых признаков предлагается использовать четыре формантные траектории, вычисляемые с помощью вейвлетпреобразования из [2]. Полученная матрица признаков разбивается на кадры по 96 мс, что соответствует средней длительности фонемы русского языка, и формируется последовательность речевых характеристик для каждой фонограммы. Для определения принадлежности фонограмм одному диктору обе последовательности сравниваются по методу динамического искажения времени (Dynamic Time Warping, DTW) [3], где в качестве оценки степени схожести двух кадров используется метрика из [4] n ci i i + cai a1 a2, (, a) = i i i=1 j это частота, а aj амплитуда i-ой форманты j-ой последогде i i вательности; cai и ci соответствующие весовые коэффициенты.

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

В качестве речевых признаков берутся коэффициенты MFCC (Mel-frequency cepstrum coecients) вместе со своими первыми и вторыми производными. Для построения модели диктора применяется метод полной изменчивости (Total Variability, TV) совместно с линейным дискриминантным анализом, как описано в работе [5]. Данный метод является одним из лучших решений для компенсации канала и внутренней вариативности диктора на сегодняшний момент. Задача классификации решается с помощью машины опорных векторов [6].

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

1. Datastrip микрофон плохого качества, произнесения девяти различных ФИО, 756 фонограмм, 15 дикторов.

2. Цифры 0–9 GSM канал, произнесения цифр от 0 до 9, 2242 фонограммы, 142 диктора.

3. Предложения микрофон, произнесения пяти длинных предложений, 3351 фонограмма, 43 диктора.

4. ФИО + цифры 0–9 GSM канал, произнесения уникальных ФИО и одинаковых цифр от 0 до 9, 2242 фонограммы, 142 диктора.

2.5. Обобщенное решение. После того, как каждый из методов принял решение в виде вероятности принадлежности фонограмм одному диктору, полученные решения необходимо объединить в одно. Для этой цели используются различные методы композиции алгоритмов. В этой статье сравнение проводится между наивным байесовским классификатором (NaiveBayes) [7] и методом адаптивного бустинга (AdaBoost) [8]. В таблице 2 представлены равновероятностные ошибки (РО) исходных алгоритмов и методов композиции.

Таблица 2. Результаты тестирования методов обобщенного решения РО DTW РО TV РО Naive РО Ada База метода, % метода, % Bayes, % Boost, % Datastrip 7,9 10,6 6,9 6,6 Цифры 0–9 7,2 8,3 7,0 7,0 Предложения 2,7 2,6 2,0 2,2 ФИО и цифры 0–9 5,9 7,1 5,0 4,9 Несколько лучшие результаты показал алгоритм AdaBoost, при этом обучение байесовского классификатора оказалось вычислительно более сложной задачей.

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

В качестве критериев вариативности рассматривались статистические величины, вычисляемые на наборах признаков. В качестве признаков были выбраны формантные траектории в силу их устойчивости к шумам и помехам [2].

В рассмотрение входили:

1. Интерквартильный размах (разность между 0,75-квантилем и 0,25-квантилем);

2. Среднее абсолютное отклонение;

3. Динамический диапазон;

4. Стандартное отклонение;

5. Энтропия формантных траекторий;

6. Трёхмерная энтропия, рассчитываемая на трех формантах;

7. Псевдоэнтропии (функции от величины энтропии и характеристик сигнала).

Здесь и далее рассматривается информационная энтропия, вычисляемая на отсчётах формантных траекторий. Вычисление информационной энтропии производится по гистограмме сигнала, ячейки которой рассматриваются в качестве алфавита. Подробнее вычисление данной величины описано в [9].

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

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

Таблица 3. Результаты тестирования РО на РО на Слабо вариБаза полной базе, урезанной ативные % базе, % записи, % Datastrip 6,6 5,4 21,0 Цифры 0–9 7,0 6,9 1,7 Предложения 2,2 2,2 0,3 ФИО и цифры 0–9 4,9 4,9 0,2

4. Выводы. В данной работе рассмотрена гибридная система верификации с возможностью предварительной оценки качества фонограммы и парольной фразы для улучшения качества работы методов. На базе ФИО и цифры 0–9, приближенной к реальным условиям использования системы, достигнут приемлемый уровень равновероятностной ошибки в 4,9%. Ошибку верификации можно значительно снизить, например, используя несколько записей в качестве эталона.

Литература

1. Симончик K. C., Галинина О. С., Капустин А. И. Алгоритм обнаружения речевой активности на основе статистик основного тона в задаче распознавания диктора // Научно-технические ведомости СПбПТУ. Изд-во Политех. ун-та, 2010. № 4(103). C. 18–23.

2. Коровин А. С., Королев А. И., Тимошенко Д. М. Алгоритм нахождения образующих частот речевого сигнала // Процессы управления и устойчивость: Труды 41-й международной научной конференции аспирантов и студентов / Под ред. Н. В. Смирнова, Г. Ш. Тамасяна. СПб.: Издат. Дом С.-Петерб. гос. ун-та, 2010.

С. 442–448.

3. Geppener V. V., Simonchik K. K., Haidar A. S. Development of an automatic speaker-verication system using the dynamic timewarping algorithm // Pattern Recognition and Image Analysis, 2005.

Vol. 15, No. 2. P. 397.

4. Ручай А. Н. Разработка текстозависимой системы идентификации диктора по голосу // Системная интеграция и безопасноть: Сборник научной сессии ТУСУР. Томск: В-Спектр, 2009.

С. 347–352.

5. Dehak N., Dehak R., Kenny P. et al. Support vector machines versus fast scoring in the low-dimensional total variability space for speaker verication // INTERSPEECH, 2009. P. 1559–1562.

6. Vapnik V., Chapelle O. Bounds on error expectation for support vector machines // Neural Computation, 2000. Vol. 12, No. 9.

P. 2013 2036.

7. Статистические (байесовские) методы классификации.

http://goo.gl/teJvM

8. Лекции по алгоритмическим композициям.

http://goo.gl/hi0UX

9. Шеннон К. Работы по теории информации и кибернетике.

М.: Наука, 1963. С. 461–463, 669–687.

Гришкин В. М., Якушкин О. О.

Санкт-Петербургский государственный университет

–  –  –

1. Введение. В последнее десятилетие активно развивалась сервероцентрическая бизнес-модель программного обеспечения по требованию (SaaS) [1]. Одной из причин такого вектора развития была потребность разделения процесса исполнения задач и предоставления результатов на растущем спектре пользовательских устройств.

Для реализации SaaS архитектуры применяется модульный подход к разработке программного обеспечения SOA (сервис-ориентированная архитектура), основанный на слабо связанных (англ. loose coupling) заменяемых компонентах, оснащённых стандартизированными интерфейсами взаимодействия [2]. Все чаще, наряду с классическими службами, взаимодействующими по протоколу SOAP (простой протокол доступа к объектам), встречаются RESTful сервисы, соответствующие ограничениям стиля архитектуры передачи состояния представления.

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

Наличие прослойки виртуальной машины позволило многим крупным компаниям создать распределенные PaaS (платформы в виде услуги) для удаленного исполнения ориентированных на них служб.

В целях обеспечения безопасности и контроля крупных публичных PaaS систем, исполнение отдельных сервисов, разработанных специально для работы с конкретным оборудованием, труднореализуемо и не получило широкого распространения. Однако, в рамках конкретных проектов для достижения наилучшей производительности используются сервисы, созданные с учетом особенностей платформ на которых их исполняют. Примерами служат Google, Facebook и другие веб-сервисы с высокой сетевой и информационной нагрузкой [3, 4].

2. Постановка задачи. Сегодня созданию сервисов на языках низкого уровня (здесь будем рассматривать исключительно C++) препятствует сложность в разработке и трудность в масштабируемости. Однако, разработка native приложений на C++ с выходом нового стандарта C++11 значительно упростилась [5]. Это подтверждается заявлениями представителей IT корпораций о ренессансе языка и его продвижением в рамках профессионального сообщества [6]. Существенное значение имеет и объем открытого исходного кода на С++, которого гораздо больше, чем на каком-либо другом языке [7], что делает его прочным фундаментом для разработки.

Существует три слоя библиотек программирования, которые предоставляют различные возможности для реализации компонентов сетевых архитектур на C++. Это интегрированные в операционные системы; предоставляющие кроссплатформенные абстракции для работы с сетью (ACE [8], Boost [9], MQ [10]); вспомогательные библиотеки для организации работы веб-приложений (mongoose [11], Wt [12]).

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

В этой работе коснемся некоторых из них:

• разработка кроссплатформенной сервис-ориентированной платформы;

• создание модульной архитектуры на основе слабо связанных элементов-сервисов;

• отлаживание систем межсервисных коммуникаций.

Также рассмотрим ряд примеров сервисов на C++.

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

Используя Boost, OpenSSL был разработан сервер, состоящий из

• загрузчика библиотек,

• цикла принятия и обработки запросов,

• интерфейса управления.

Рис. 1. Процесс работы сервера

Работа сервера описывается следующим алгоритмом (см. рис. 1):

• запуск;

• чтение файла настроек для обеспечения работы цикла обработки запросов;

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

• инициализация сервисов;

• ожидание и обработка запросов;

• освобождение ресурсов и отключение.

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

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

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

Рис. 2. Процесс работы с классом http_service

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

2):

• создание;

• запуск;

• настройка;

• основной жизненный цикл сервиса:

– предоставление сервису полученного запроса для анализа, (сервис должен ответить, что он готов сделать с данным запросом: полностью обслужить, посодействовать в обслуживании или проигнорировать);

– вызов основной функции сервиса;

• сигнал остановки сервиса;

• освобождение ресурсов.

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

Для упрощения разработки сервисов, работающих по протоколу HTTP, был создан наследник базового сервиса класс http_service.

В нем активно использовались компоненты разработанных библиотек.

Следующим шагом было создание демонстрационного проекта.

В рамках него разработан ряд HTTP сервисов:

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

2. Сервис просмотра файловой системы сервера. Предоставляет возможность отображать заданные фрагменты файловой системы сервера в сеть.

3. Сервис файлового хранилища. Создает среду для управления личными файлами пользователей.

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

5. Сервис потоковой видеотрансляции. Предоставляет возможность вещания и просмотра живых мультимедийных потоков.

Основным средством общения с HTTP сервисами являются веббраузеры. В связи с этим, на языках HTML, CSS и JavaScript с использованием библиотеки jQuery был разработан унифицированный интерфейс для доступа к сервисам обработки изображений, потоковой видеотрансляции и файлового хранилища.

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

4. Заключение. Пример разработанной сервис-ориентированной системы на C++ может служить моделью-прототипом для реализации процесса разделения исполнения задач и вывода результатов на пользовательских устройствах. Данный проект использовался при создании удаленного доступа к одному из высокопроизводительных кластеров факультета ПМ – ПУ и показал свою эффективность [13].

На базе созданного прототипа планируется создание распределенной системы, объединяющей отдельные серверы-узлы в единую вычислительную сеть.

Литература

1. Software as a service on Wikipedia.

http://en.wikipedia.org/wiki/Software_as_a_service

2. Biske T. SOA Governance. Birmingham: Packt Publishing Ltd, 2008.

228 p.

3. Google: cluster computing and MapReduce. http://code.google.

com/intl/ru-RU/edu/submissions/mapreduce-minilecture/ listing.html

4. HipHop for PHP.

https://github.com/facebook/hiphop-php/wiki/

5. C++ and beyond 2011: Herb Sutter. http://channel9.msdn.com/ posts/C-and-Beyond-2011-Herb-Sutter-Why-C

6. C++ renaissance at Microsoft. http://mariusbancila.ro/blog/ 2011/06/20/cpp-renaissance-at-microsoft/

7. Compare languages at ohloh.

https://www.ohloh.net/languages?query=&sort=code

8. The adaptive communication environment.

http://www.cs.wustl.edu/~schmidt/ACE.html

9. Boost C++ libraries. http://www.boost.org/

10. 0MQ: The intelligent transport layer. http://www.zeromq.org/

11. Mongoose – easy to use web server.

http://code.google.com/p/mongoose/

12. C++ library for developing web applications.

http://www.webtoolkit.eu/wt

13. Cloudobserver svn on google code. http://code.google.com/p/ cloudobserver/ Иванов А. Н.

Санкт-Петербургский государственный университет Численная реализация матричного формализма1 Рекомендовано к публикации профессором Андриановым С. Н.

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

Указанные свойства обеспечивают ряд преимуществ данного подхода по сравнению с традиционными пошаговыми методами интегрирования:

• вычисление промежуточных состояний динамической системы не производится;

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

• представление всех вычислительных операций в виде суммирования и произведения числовых матриц;

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

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

1 Работа выполнена в рамках договора о сотрудничестве между СПбГУ и ин

–  –  –

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

3.2. Описание реализации. Для построения интересующей нас системы уравнений (5) программным путём необходимо решить ряд задач.

1. Разложение произвольной функции F(t, X) в ряд по компонентам векторов X[k] при преобразовании системы (1) в (2).

2. Реализация операций кронекеровской степени и взятия частных производных в соотношении (5).

Все эти задачи реализованы как подсистема символьных вычислений. Функции представляются в виде разложений в ряды Тейлора.

При этом операция взятия частной производной по компонентам векторов X[k] выражается через поиск соответствующего коэффициента в ряде Тейлора.

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

4.1. Подсистема символьных вычислений. Основным элементом в логике работы программы является символьный полином.

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

Вычисление кронекеровской степени вектора X[k] осуществляется на основе возведение полинома в степень (x1 +... + xn )k.

4.2. Графический интерфейс. Пользовательский интерфейс программы (рис. 1) организован по принципу таких пакетов, как MATLAB или FreeMat, имеет три окна: переменные, история команд, командная строка. Программа позволяет производить все описанные выше операции, а также сохранять данные в файл и загружать их.

Рис. 1. Пользовательский интерфейс программы

5. Вычислительный эксперимент. Рассмотрим применение описанного подхода на конкретных примерах.

5.1. Модель хищник-жертва. Численность конкурирующих популяций можно описать уравнением Лотки Вольтерры dx dy = ay + cxy, = bx + dxy, dt dt которое в линейном случае является уравнением гармонического осциллятора. Приведём процесс построения решения при помощи разработанной программы.

a=-1; b=1; c=-1; d=1;

f1 = a*x1 + c*x0*x1;

f2 = b*x0 + d*x0*x1;

system(array(f1, f2), 1)

order 1:

0 -1 solve(1, 0.1, ans) 0.54030242274894 -0.841470909817685 0.841470909817685 0.54030242274894

Результатом является матрица, задающая преобразование начальной точки (x, y) за временной интервал, равный 1 секунде:

x 0, 54030242274894 0, 841470909817685 x0 =.

y 0, 841470909817685 0, 54030242274894 y0

5.2. Длительная эволюция заряженных частиц. Подобный подход может быть успешно применён для моделирования длительной эволюции динамических систем. В рамках проекта EDM (поиск электрического дипольного момента) рассмотрена некоторая структура накопительного кольца, состоящая их квадруполей, цилиндрических конденсаторов и свободных промежутков. Каждый элемент описывается системой дифференциальных уравнений в криволинейной системе координат, для которых построены соответствующие матрицы. Преобразование, отвечающее за прохождение частицами всех элементов, строится как последовательная конкатенация отображений с последующей их симплектификацией. На рис. 2 приведён фазовый портрет (x, x ) (x одна из координат) некоторой частицы.

Рис. 2. Фазовый портрет, 1 000 000 000 оборотов

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

Литература

1. Андрианов С. Н. Динамическое моделирование систем упарвления пучками частиц. СПб.: Изд-во СПбГУ, 2002. 376 c.

2. Andrianov S. N. Role of parallel and distributed computing in beam physics // Nuclear Instruments and Methods, 2004. Vol. 519.

P. 37–41.

3. Иванов А. Н. Символьные вычисления в моделировании динамики пучков заряженных части // Процессы управления и устойчивость: Труды 42-й международной научной конференции аспирантов и студентов / Под ред. А. С. Ерёмина, Н. В. Смирнова.

СПб.: Издат. Дом С.-Петерб. ун-та, 2011. С. 127–133.

Кузнецов П. М., Горин А. В., Иванов А. Н.

Санкт-Петербургский государственный университет Модификация алгоритма визуальной одометрии с применением оптического потока Рекомендовано к публикации доцентом Гришкиным В. М.

1. Введение. В английской литературе задача построения роботом карты прежде неизвестного окружения вместе с одновременным нахождением своей позиции носит название SLAM (Simultaneous Localization and Mapping). Помимо методов решения задачи SLAM, основанных на данных от сонаров и лазерных дальномеров, в последнее десятилетие стали популярными варианты с применением камер.

Такую вариацию задачи часто называют Visual SLAM. В дальнейшем, чтобы не использовать английскую аббревиатуру, будем называть эту задачу визуальной одометрией. Несмотря на заявляемые авторами [1] возможности работы в режиме реального времени (в условиях ограничений, вводимых камерами, работа в реальном времени означает выдачу результатов с частотой близкой к 30Гц), подобные реализации визуальной одометрии зачастую не справляются с возложенными на них обязательствами ввиду того, что вычислительным ядром робота чаще всего является довольно слабый компьютер (изза ограничения в потребления электроэнергии).

Наиболее трудозатратными с точки зрения времени вычисления в подобных подходах являются этапы:

• нахождения и сопоставления особых точек, на котором обычно используются такие алгоритмы, как SURF (Speeded Up Robust Feature) и SIFT (Scale-Invariant Feature Transform);

• оптимизации полученной карты, где применяются различные варианты фильтра Калмана, либо некоторые варианты SBA (Sparse Bundle Adjustment).

В данной статье предлагается модификация алгоритма визуальной одометрии с применением оптического потока, вычисленного по методу Лукаса Канаде [2].

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

1. Методы, использующие монокулярную камеру, к примеру [3].

2. Методы, использующие стерео связку камер, [4].

Основное преимущество методов с несколькими камерами заключается в более простой задаче триангуляции (перевода точек из плоскости изображения в трехмерное пространство). Однако для её решения необходима предварительная калибровка связки камер. Кроме того, дополнительно налагается ограничение на синхронность получения кадров от камер, так как даже минимальный интервал в съемке при движении может привести к существенным ошибкам. Отметим, что несмотря на некоторые отличия (например, отсутствие в методах на связках камер масштабной неопределенности, присущей монокулярным методам) подходы обеих категорий имеют много общего. В каждом случае требуется отследить особые точки на некотором наборе изображений. На основе полученных следов можно найти взаимное расположение камер, с которых были получены изображения, с точностью до определенного семейства гомографических преобразований пространства [5]. Более того, можно оценить взаимную структуру наблюдаемых точек пространства, соответствующих полученным следам. При условии наличия связки камер, используя известную калибровку связки, можно также построить трехмерное облако точек для каждого кадра. Аналогичные облака точек получают, используя RGBD камеру (такие сенсоры, как Microsoft Kinect, ASUS Xtion и т. п., позволяют получить не только кадр цветного изображения, но и кадр карты глубины, которую простыми преобразованиями можно привести к виду трехмерного облака точек). На основе этих наборов точек на двух последующих кадрах можно уточнить оценку взаимного расположения этих кадров, применяя итеративный алгоритм ближайших точек (ICP) [5, 6]. Встречаются и другие подходы, в которых происходит слияние визуальной одометрии с данными от других сенсоров для увеличения точности результатов и сокращения сдвига. Последняя проблема присуща всем методам нарастающего позиционирования. Среди сенсоров, применяемых в таких случаях, чаще всего встречаются энкодеры колес, гиростабилизаторы и GPS-приёмники.

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

Чаще всего для этого применяется один из следующих алгоритмов:

SIFT (Scale-Invariant Feature Transform) и SURF (Speeded Up Robust Feature). Оба этих метода заключаются в поиске особых точек изображения и построения для каждой такой точки ее дескриптора, который, в свою очередь, является в некоторой степени инвариантом по отношению к изменению масштаба, освещенности и аффинным преобразованиям. Авторы метода SURF, который в некоторой степени наследует идеологию SIFT, заявляют, что он в несколько раз быстрее своего предшественника и более устойчив к различного рода преобразованиям. Однако даже скорость SURF’а не позволяет гарантировать выдачу оценки визуальной одометрии на частоте, близкой к реальному времени. Стремясь обеспечить инвариантность к масштабу, оба этих метода исследуют изображение в поиске особых точек сразу на нескольких уровнях гауссовой пирамиды изображения, что и приводит к резкому увеличению количества операций.

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

Предложенный ниже метод в некоторой степени учитывает эту особенность.

3. Предлагаемая модификация. Как уже было сказано, идея модификации алгоритма заключается в ускорении этапа получения следа особой точки с учетом того, что от кадра к кадру не происходит радикальных изменений. В таком случае вместо построения дескрипторов для особых точек, найденных на большом числе масштабов, эффективней найти оптический поток для каждой из особых точек оригинального изображения. Для выделения набора особых точек можно использовать один из быстрых алгоритмов нахождения углов на изображении, например, алгоритм Харриса или алгоритм минимальных собственных чисел. Вернёмся к вопросу о вычислении потока. Для решения этой задачи применим метод Лукаса Канаде, реализованный через постепенное уточнение оценки потока при спуске по пирамиде, как это предложил Буге в [7]. Суть метода заключается в поиске для каждой найденной на первом изображении I особой точки u соответствующее ей положение точки v = u + d на следующем изображении J, или, что тоже самое, в поиске смещения в пикселах d для точки u при переходе из I в J. После построения пирамиды для изображений {I L }L=0,...,Lm и {J L }L=0,...,Lm, где I 0 = I и J 0 = J, оптический поток вычисляется на самом глубоком уровне пирамиды Lm, а полученный результат итеративно подставляется на следующий уровень в качестве предварительной оценки оптического потока. Рассмотрим теперь операции, выполняемые между уровнями L + 1 и L. Предположим, что g L = [gx gy ]T LL оценка оптического потока, полученная на уровне L после ее вычисления на уровнях с Lm по L + 1. Тогда для вычисления потока на уровне L достаточно вычислить остаточное смещение dL = [dL dL ]T, которое минимизиxy рует функцию uL +y uL +x y x

–  –  –

Таким образом, за счет первоначальной оценки g L остаточное смещение dL получается довольно маленьким и, как следствие, его легко вычислить через стандартный метод Лукаса Канаде. В результате, даже при условии малого размера смещения на каждой итерации конечное смещение d получается достаточным для учёта значительного перемещения проекций близких к камере точек при движении.

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

4. Реализация и тестирование. Для тестирования существующих алгоритмов была собрана мобильная роботизированная платформа со стерео связкой из двух вебкамер Logitech C100, а также сенсором Microsoft Kinect. Вычислительным ядром робота является ноутбук с процессором Intel Atom D525 и тактовой частотой 1,8 ГГц Рис. 1. Фотография мобильной роботизированной платформы для тестирования, а также результаты вычисления оптического потока и визуальной одометрии на примере изображений коридора общежития и встроенным видеопроцессором Intel GMA 3150. На указанном ноутбуке была развернута система ROS (Robot Operating System) и протестированы следующие библиотеки визуальной одометрии: libviso, libmv, rgbdslam, vslam, scenelib, ScaViSLAM. Также были реализованы и протестированы алгоритмы SIFT, SURF и описанный выше метод построения оптического потока. Сравнительные результаты работы этих трех методов приведены в таблице 1. Примеры работы алгоритма продемонстрированы на рис. 1. Все результаты соответствуют однопоточной работе на процессоре.

Таблица 1. Некоторые характеристики работы описанных методов Название метода Время работы Частота SIFT 2500 – 3500 мс 0, 5 Гц SURF 1500 – 2500 мс 0, 5 Гц Оптический поток 150 – 200 мс 5–7 Гц

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

Литература

1. Engelhard N., Endres F., Hess J., Sturm J., Burgard W. Real-time 3D visual SLAM with a hand-held RGB-D camera // Proc. of the RGB-D Workshop on 3D Perception in Robotics at the European Robotics Forum, Vasteras, Sweden, 2011.

2. Lucas B. D., Kanade T. An iterative image registration technique with an application to stereo vision // Proceedings of Imaging Understanding Workshop, 1981. P. 121–130.

3. Yamaguchi K., Kato T., Ninomiya Y. Vehicle ego-motion estimation and moving object detection using a monocular camera // Proc. of the 18th Int. Conf. on Pattern Recognition, 2006. P. 610–613.

4. Kitt B., Geiger A., Lategahn H. Visual odometry based on stereo image sequences with RANSAC-based outlier rejection scheme // IEEE Intelligent Vehicles Symposium, San Diego, USA, 2010.

5. Hartley R., Zisserman A. Multiple view geometry in computer vision.

Second edition ed. Cambridge University Press, 2008. 607 p.

6. Milella A., Siegwart R. Stereo-based ego-motion estimation using pixel-tracking and iterative closest point // Proc. of the 4th IEEE Int. Conf. on Computer Vision Systems, 2006.

7. Bouguet J.-Y. Pyramidal implementation of the Lucas–Kanade feature tracker description of the algorithm // Intel Corporation Microprocessor Research Labs, 2000.

Максимов А. Ю.

Санкт-Петербургский государственный университет Развитие идеи автоматизации пользовательской деятельности Рекомендовано к публикации доцентом Добрыниным В. Ю.

1. Введение. С учетом постоянно растущего числа пользователей персональных компьютеров увеличивается необходимость автоматизации пользовательской деятельности, включающей в себя автоматизацию производственных процессов, бизнес-процессов, проектирования, планирования, организации, управления и т. д. В данной работе предлагается решение, позволяющее упростить в вышеперечисленных областях выполнение многих задач. Необходимость автоматизации существует уже долгое время, и на данный момент задача эмуляции пользовательской активности имеет множество решений. Чаще всего для описания действий, которые требуется совершить, пишутся скрипты. Например, для того, чтобы открыть некоторое окно (например, Program Files) и переместить его куда-либо (например, на 50 пикселей правее) пишется скрипт, который можно условно представить в виде следующего псевдоскрипта:

int handle = Window.Open("C:\Program Files");

Point pnt = Window.GetPos(handle);

Window.Move(pnt, new Point(pnt.x + 50, pnt.y));

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

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

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

3.1. AutoHotKey. Это продукт с открытым исходным кодом, обладающий богатым функционалом, среди которого присутствуют возможности: автоматизировать процессы, посылая нажатия клавиш клавиатуры и кнопок мыши; писать скрипты для клавиатуры и мыши (вручную, либо используя утилиту для автоматической записи активности); задавать горячие клавиши для клавиатуры, джойстика и мыши (любая клавиша, или их набор может стать горячей ). А также возможно распознавание аббревиатуры; создание формы запроса данных, пользовательских интерфейсов и меню; переназначение клавиш и кнопок устройств; преобразование любого скрипта в exe-файл, который может быть запущен на компьютерах, где не установлена программа [1].

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

управление буфером обмена (копирование информации в буфер и из него, сохранение в файл); назначение горячих клавиш для каждой записи; дописывание и редактирование записи [2].

3.3. AutoIt. Это freeware Basic-подобный скриптовый язык, разработанный для автоматизации работы с пользовательскими интерфейсами Windows. Приложение достаточно маленькое и может быть запущено на любых версиях Windows без дополнительного программного обеспечения. Изначально разрабатывалось для надежной автоматической настройки огромного числа компьютеров и, с течением времени, стало мощным языком, поддерживающим сложные выражения, пользовательские функции, циклы и т. д. Основной функционал включает возможности: запускать на выполнение Windows и DOS программы; симулировать нажатия комбинаций клавиш клавиатуры (поддерживается основная масса раскладок клавиатуры); симулировать перемещения указателя мыши и нажатия на ее кнопки; перемещать, менять размер и управлять параметрами отображения окон; непосредственно взаимодействовать с управляющими элементами окна (получать/менять надпись, перемещать, отключать и т. п.) работать с буфером обмена для пересылки его текстового содержания; читать, менять, создавать ключи и значения реестра [3].

4. Реализованный программный продукт PowerEML. После анализа недостатков описанных выше программ было написано приложение PowerEML, сочетающее в себе богатство функционала и простоту использования. Продукт представляет собой интерфейс, предполагающий написание скрипта, за основу синтаксиса которого был взят язык C. Таким образом, разработанный язык поддерживает все основные управляющие конструкции, такие как циклы (for, while, do-while), ветвление (if-else, if-else if, switch), конструкцию обработки ошибок и некоторые специальные конструкции. Оператор goto был преднамеренно оставлен за рамками проекта во избежание серьезных трудностей при отладке. Поддерживаются различные типы данных (примитивные: int, double, string, bool,... ; сложные: массивы, списки, ассоциативные массивы,... ). Реализована поддержка функций, в том числе есть возможность написания рекурсивных алгоритмов. Для упрощения написания скрипта было принято решение не различать регистры, что позволяет сильно ускорить процесс отладки. Основные возможности программы включают в себя:

• управление мышью: перемещение курсора, передвижение объектов, удержание, управление колесом мыши, клик (с возможностью настройки времени нажатия, точности попадания и т. д.);

• привязка действий мыши к элементам управления и заданным координатам;

• эмуляция нажатия комбинаций клавиш клавиатуры;

• определение местонахождения объектов на экране, цветов указанных пикселей или их последовательностей;

• полноценная работа с MySQL и MSSQL;

• скачивание файлов из Web;

• обработка содержимого и взаимодействие с элементами HTML посредством xPath;

• чтение/запись файлов, работа с каталогами;

• работа с буфером обмена;

• распознавание Captcha;

• распознавание голосовых команд.

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

5. Описание методов, алгоритмов и экспериментов. Чтобы показать возможности использования программы PowerEML был проведен ряд статистических экспериментов, в ходе которых были получены любопытные результаты.

5.1. Сбор статистических данных социальной сети. Для получения набора тестовых данных было обработано более 10000 случайных анкет одной из социальных сетей. Была собрана вся информация, лежащая в открытом доступе, включая информацию о взаимосвязях между анкетами. Для хранения собранной информации использовалась БД MySQL. Сбор осуществлялся с применением приложения PowerEML: был использован встроенный браузер, извлечение информации осуществлялось с помощью обработки HTMLкода страниц посредством xPath. Объем полученных данных составил свыше 100mb. Эксперимент заключался в том, чтобы, используя полученную статистическую выборку, проверить теорию 6 рукопожатий. После сбора данных о связях анкет для каждой из них был применен алгоритм Дейкстры [4] для получения кратчайшего пути между двумя выделенными вершинами графа, построенного по взаимосвязям анкет. В итоге для каждой анкеты S получился набор данных вида {(x1, y1 ), (x2, y2 ),... }, где yi доля анкет (среди общего количества анкет в выборке), с которыми связана анкета S, таких, что минимальный путь между ними пролегает через xi 1 других анкет. Величины yi при одинаковых xi для различных анкет суммировались, а затем высчитывалось среднее значение yi.

5.2. Анализ данных и сбор статистики с использованием сервиса Sophia Search [5]. По вводимым ключевым запросам, интерфейс получал в ответ облако тегов. Слова и фразы, содержащиеся в нем, можно назвать ассоциациями, связанными с введенным запросом. Таким образом, описанное приложение PowerEML можно использовать для автоматического создания словарей ассоциаций, словарей синонимов и т. д., а также для дальнейшего анализа текстовой информации с использованием полученных связей.

6. Результаты. Рассмотрим результаты экспериментов.

6.1. Эксперимент с социальной сетью. На рис. 1 представлены пары (xi, yi ) для всех обработанных анкет.

Рис. 1. Диаграмма длин связей анкет

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

6.2. Эксперимент с сервисом Sophia Search. В качестве иллюстрации результата эксперимента с сервисом Sophia Search можно привести пример облака ассоциаций со словом microsoft (см. рис. 2).

–  –  –

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

Литература

1. AutoHotKey. http://www.autohotkey.com/

2. AutoClickExtreme.

http://www.autoclickextreme.com/ru/ind.html

3. AutoIt. http://www.autoitscript.com/site/autoit/

4. Алгоритм Дейкстры.

http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры

5. SophiaSearch Home Page. http://www.sophiasearch.com/ Мезенцева П. В.

Санкт-Петербургский государственный университет Применение онтологии предметной области в задаче информационного поиска Рекомендовано к публикации доцентом Матросовым А. В.

Введение. Информационный поиск (Information Retrieval) это комплексная деятельность по сбору, организации, поиску, извлечению и распространению информации при помощи компьютерных технологий [1].

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

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

Такое представление текстов как простого набора слов ( bag of words ) имеет большое количество очевидных недостатков, затрудняющих поиск релевантных текстов:

• избыточность в пословном индексе используются словасинонимы, выражающие одни и те же понятия;

• слова текста считаются независимыми друг от друга, что не соответствует свойствам связного текста;

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

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

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

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

Постановка задачи. Требуется реализовать алгоритм поиска информации на web-сайте на основе семантической сети онтологии предметной области.

В качестве предметной области выберем раздел Образование на сайте факультета ПМ – ПУ СПБГУ.

Как было замечено во введении, методы онтологического поиска не могут применяться без сочетания их с пословными методами информационного поиска. В качестве модели пословного поиска будем использовать векторную модель поиска (Vector Space Model).

Согласно этой модели каждому документу d коллекции сопоставляется вектор w(t1, d).

.

d =,.

w(tM, d)

–  –  –

Общее описание алгоритма поиска на основе онтологии.

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

На основе этой идеи рассмотрим алгоритм поиска, состоящий из подготовительных и основных этапов.

Подготовительные этапы выполняются однократно до введения запроса пользователем.

1. Построение семантической сети онтологии S(O) предметной области в виде мультиграфа G(О), учитывающего важность объектов онтологии и отношений между ними.

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

3. Построение семантической сети документа S(T) и соответствующего ей графа G(Т) по найденным понятиям как задача огрубления графа G(О).

Основные этапы.

1. Выделение ключевых слов из запроса пользователя Q и поиск множества понятий онтологии, соответствующих этим ключевым словам c(Q).

2. Построение семантической сети запроса S(Q) и соответствующего ей графа G(Q) на основе этих понятий как задача огрубления графа G(O).

3. Вычисление оценки релевантности каждого документа запросу, формализующей близость семантических сетей S(T) и S(Q).

4. Вывод релевантных запросу документов.

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

–  –  –

где Q={q1,...,qN } множество тестовых запросов, |Q| число элементов этого множества, Ij ={d1,...,dmj } упорядоченное множество истинно релевантных документов запросу qj, P recision(Rjk ) количество документов из подмножества Ij от d1 до dk, которые встретились среди первых k документов результата.

Для оценки применения онтологии в задаче информационного поиска приведем значение характеристики MAP при применении только векторной модели поиска, только онтологического подхода и при применении их комбинации. Результаты для 50 тестовых запросов представлены в таблице 1.

Таблица 1. Оценка результатов работы поиска Векторная Онтологический Комбинированный модель подход подход MAP 0,265327 0,494117 0,595232 Как видно из таблицы 1 применение онтологии повышает точность работы поисковой системы.

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

Таблица 2. Вычисление характеристики Recall(%) Векторная Онтологический Комбинированный модель подход подход Recall (%): 64,4724 55,3967 79,9042 Выводы.

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

–  –  –

1. Добров Б. В., Иванов В. В. Онтологии и тезаурусы: модели, инструменты, приложения, 2008. http://www.intuit.ru/ department/expert/ontoth

2. Маннинг К. Д., Рагвахан П., Шютце Х. Введение в информационный поиск. М.: Вильямс, 2011. 520 с.

3. Карпенко А. П. Оценка релевантности документов онтологической базы знаний [Электронный ресурс] // Наука и образование: электронное научно-техническое издание, 2010, Вып. 9.

http://technomag.edu.ru/doc/157379.html Нвохири А. М., Чернобровкин Д. И.

Санкт-Петербургский государственный университет Разработка вебометрических инструментов и их апробация на веб-сайтах нигерийских университетов Рекомендовано к публикации доцентом Печниковым А. А.

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

В данной статье рассмотрим академический фрагмент Веба Нигерии. Столь необычный сегмент Веба был выбран целью исследований потому, что

1. Нигерия является самой населенной страной африканского континента.

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

Для сбора, визуализации и обработки информации об исходящих ссылках был использован программный комплекс BeeBot. Более подробно его состав и принципы работы будут рассмотрены далее.

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

Этот проект Испанской исследовательской группы Cybermetrics Lab Webometrics Ranking of World Universities [1] один из наиболее известных вебометрических проектов. Он посвящен вебометрическим исследованиям сайтов вузов и научно-исследовательских институтов мира. Сайты ранжируются на основании комбинации таких вебометрических показателей, как размер (количество страниц), видимость (количество уникальных гипертекстовых ссылок с других веб-ресурсов, обнаруживаемых поисковыми системами), количество полнотекстовых файлов, количество ссылок на научные статьи, размещенные на сайте и обнаруживаемые Google Scholar.

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

Краткое описание программы BeeBot. Рассмотрим BeeBot в деталях. BeeBot это многофункциональный программный комплекс для вебометрического анализа [2].

На данный момент в его состав входят:

1. BeeCrawler краулер для сбора ссылок и управления (удаления/добавления ссылок в базу данных). Имеет встроенный графический интерфейс для просмотра и управления ссылками.

2. BeeDB База данных для хранения всей собранной информации о ссылках.

3. BeeKeeper управление режимом краулинга и апробация адаптивной работы краулера для решения задачи о многоруком бандите.

4. BeeGraph модуль для визуализации веб-графа, используя BeeDB, текстовые файлы или файлы в формате GraphML.

Данный программный комплекс впоследствии будет совершенствоваться и расширяться. Планируется добавить инструменты для анализа графов, инструменты для расширенного управления собранными ссылками и т. д.

Основные технологии, которые были использованы при создании BeeBot’a MSSQL Server Express, Entity Framework и LINQ для BeeDB, C# версии.Net 4.0 для краулера, для пользовательского интерфейса была использована технология WPF. Для визуализации графов используется библиотека Graph Sharp, для парсинга htmlдокументов используется библиотека HTMLAgility Pack.

С помощью BeeCrawler’a были собраны исходящие ссылки с сайтов университетов Нигерии. Интересный результат был получен при сопоставлении расположения университетов и количества ссылок с внешним научным сообществом.

Нигерийский Веб и связи с Англией, США и Австралией. По данным Национальной университетской комиссии Нигерии (далее NUC) в стране насчитывается 118 университетов, из них 36 федеральных, 37 университетов штатов и 45 частных университетов [3]. NUC государственный орган, который дает разрешение на учреждение высших учебных заведений, предлагающих образовательные программы, и проводящий аккредитацию всех учебных программ университетов Нигерии. Вследствие того, что список доменных имен, указанных в [3], является неполным и неточным, он был принят лишь в качестве основы и многократно дополнялся и уточнялся в процессе исследования. Уточнение списка продолжается, однако в статье мы остановимся на целевом множестве, содержащем 97 доменных имен официальных сайтов университетов Нигерии.

Этот список занимает слишком много места, поэтому приведем только несколько примеров с указанием порядковых номеров:

1. Abubakar Tafawa Balewa University, Bauchi (www.atbu.edu.ng),

10. Federal University, Otuoke, Bayelsa (www.fuotuoke.edu.ng),

20. University of Benin (www.uniben.edu.ng),

60. African University of Science & Technology, Abuja (aust.edu.ng),

97. Western Delta University, Oghara (www.wduniversity.net).

Гиперссылки с веб-сайтов нигерийских университетов на сайты университетов США, Англии и Австралии (далее зарубежные страны ) были собраны и проанализированы с помощью BeeBot.

Обратные ссылки с сайтов зарубежных стран на сайты нигерийских университетов были собраны с помощью свободно распространяемой программы Webometric Analyst [4].

В отношении университетов Нигерии можно сказать, что количество исходящих и входящих гиперссылок невелико: в сумме 583 исходящих и 312 входящих гиперссылок. При этом 39 сайтов не имеют входящих ссылок с сайтов зарубежных стран, 69 исходящих ссылок.

Среди зарубежных стран самая сильная связь с нигерийскими университетами была у США (67% от общего количества входящих и исходящих ссылок), Англии 28%, Австралии 5%. У 34 университетов нет никаких входящих и исходящих ссылок.

Вебометрический рейтинг Webometrics и корреляции со связями нигерийских университетов с вузами Англией, США и Австралией в Вебе. В рейтинге Webometrics 90 нигерийских университетов ранжированы c использованием подходов Cybermetrics Lab, описанных выше.

Для экономии места приведены только первые пять официальных сайтов университетов, имеющие наивысший ранг по версии Cybermetrics Lab:

Рис. 1. Связь сайтов университетов Нигерии с сайтами вузов Англии, США и Австралии

1. University of Benin (www.uniben.edu).

2. University of Agriculture Abeokuta (www.unaab.edu.ng).

3. University of Ibadan (www.ui.edu.ng).

4. University of Nigeria (www.unn.edu.ng).

5. Obafemi Awolowo University (www.oauife.edu.ng).

При ранжировании университетов по количеству гиперссылок пришлось убрать некоторые университеты, у которых отсутствовали ссылки на зарубежные сайты. Итого в нашем рассмотрении было 73 сайта (см. рис. 1).

Было проведено ранжирование:

1. По общему количеству входящих и исходящих ссылок.

2. По количеству входящих ссылок.

3. По количеству исходящих.

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

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

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

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

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

Литература

1. Web of World Universities. http://www.webometrics.info

2. Печников А.А., Чернобровкин Д.И. Адаптивный краулер для поиска внешних гиперссылок // Интернет конференция по проблемам теории и практики управления.

http://ubs.mtas.ru/bitrix/components/bitrix/forum.

interface/show_file.php?fid=5520

3. National Universities Commission.

http://www.nuc.edu.ng/pages/universities.asp

4. Webometric Analyst Web Analysis Software.

http://lexiurl.wlv.ac.uk Нефёдов Д. Э.

Санкт-Петербургский государственный университет Вопросы компьютерного зрения в управлении движением гусеничного робота Рекомендовано к публикации профессором Веремеем Е. И.

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

В качестве рабочего объекта принимается робот на гусеничной основе с бортовой видеокамерой, имеющей разрешение 752 582 пикселов. Для формирования программной поддержки используется язык C++ (компилятор gcc) в операционной среде Linux Ubuntu

11.10. Применяется библиотека компьютерного зрения OpenCV 2.1.

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

Так выглядит получение координат на изображении камеры объектов трёхмерного пространства:

–  –  –

3. Выделение объектов по заданному шаблону и цвету.

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

Алгоритм выделения шаблона состоит в следующем:

1. Находим ключевые точки с помощью SURF, SIFT.

2. Подсчитываем дескрипторы.

3. Сопоставляем дескрипторы с помощью Fast Library for Approximate Nearest Neighbors (FLANN).

4. Запоминаем совпадения дескрипторов шаблона и дескрипторов изображения с камеры.

5. Ищем однородные координаты границ объекта с помощью RANSAC.

Рис. 1. Определение шаблона (SURF)

6. Рисуем границы объекта в видео потоке.



Pages:     | 1 | 2 || 4 | 5 |   ...   | 6 |
Похожие работы:

«ХИМИЧЕСКИЙ АНКЕР ФИКСАЦИЯ КРЕПЕЖНЫХ ЭЛЕМЕНТОВ В РАЗЛИЧНЫХ ОСНОВАНИЯХ РЕМОНТ ПОВРЕЖДЕННЫХ, РАЗБИТЫХ И РАССВЕРЛЕННЫХ ОТВЕРСТИЙ МЕСТО ФИКСАЦИИ МОЖНО ОКРАШИВАТЬ И ПОЛИРОВАТЬ РЕШЕНИЕ СЛОЖНЕЙШИХ ПРОБЛЕМ ЗА 3 МИНУТЫ ДЛЯ ДОМАШНЕЙ МАСТЕРСКОЙ ПРОСТ В ИСПОЛ...»

«ЕЛСУКОВ Антон Витальевич ФИЗИКО-ХИМИЧЕСКИЕ ОСНОВЫ ЦИКЛИЧЕСКИХ И ИЗОГИДРИЧЕСКИХ СПОСОБОВ ПОЛУЧЕНИЯ ХЛОРИДА И НИТРАТА КАЛИЯ Специальность 02.00.04 физическая химия Диссертация на соискание ученой степени кандидата химических наук Научный руководитель: д...»

«ЖАЛДАК ЭЛЬВИРА РИНАТОВНА КОМПОЗИТНЫЕ ПЛЕНОЧНЫЕ ЭЛЕКТРОДЫ НА ОСНОВЕ ГЕКСАЦИАНОИЛИ ГЕКСАХЛОРОМЕТАЛЛАТОВ ДЛЯ ВОЛЬТАМПЕРОМЕТРИЧЕСКОГО ОПРЕДЕЛЕНИЯ ОРГАНИЧЕСКИХ СОЕДИНЕНИЙ 02.00.02 – Аналитическая химия Автореферат диссертации на соискание ученой степени кандидата химических наук Казань – 2015 Работа выполнена на кафедре аналитической химии...»

«РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ОТЧЕТ ИНСТИТУТА ФИЗИКИ им. Л. В. Киренского о научной и научно-организационной деятельности в 2003 г. Красноярск, 2004 Институт физики им. Л.В. Киренского Сибирского отделения Российской академии наук создан в октябре 1956 г. Исполняющий обязанности директора Института – академик РАН В.Ф.Шабан...»

«ПАСПОРТ БЕЗОПАСНОСТИ в соответствии с регламентом (EС) № 1907/2006 (REACH)   Дата обработки: 04.05.2016 Напечатано: 09.05.2016 Версия: 3   Cтраница 1/9 Panzym XXL РАЗДЕЛ 1: Идентификация химической продукции и сведения о производителе или поставщике 1.1. Ид...»

«ОТЗЫВ официального оппонента на диссертационную работу Попова Вячеслава Валериевича "Гигантский магнитный импеданс в аморфных микропроводах в диапазоне сверхвысоких частот", представленную на соискание ученой степени кандидата физико-математических наук по с...»

«V ИТЭФЧ42 ИНСТИТУТ ТЕОРЕТИЧЕСКОЙ И ЭКСПЕРИМЕНТАЛЬНОЙ ФИЗИКИ Б.С.ВОЛКОВ, А.Г.ДОЛГОЛЕНКО, В.АЛ1АТВЕЕВ. О.П.ФЕДОТОВ АВТОМАТИЧЕСКАЯ ОБРАБОТКА СНИМКОВ 180— ЛИТРОВОЙ КСЕНОНОВОИ КАМЕРЫ ИТЭФ МОСКВА 197? Ш €81.142.5:539.1.07 М-1Ч Рассматривается новый координатный метод обработки сн...»

«ДОКЛАДЫ АКАДЕМИИ НАУК РЕСПУБЛИКИ ТАДЖИКИСТАН 2012, том 55, №3 АСТРОФИЗИКА УДК 523. 6 Член-корреспондент АН Республики Таджикистан Х.И.Ибадинов, А.Г.Сафаров ИССЛЕДОВАНИЕ СКОРОСТИ ИЗВЕРЖЕНИЯ КРУПНОЙ ПЫЛИ ИЗ ЯДРА КОМЕТ ПО НАБЛЮДЕНИЯМ ИХ АНОМАЛЬНОГО ХВОСТА Институт астрофизики АН Республики Таджикистан По наблюдениям аномального хвоста определена скоро...»

«Электрохимическая модификация поверхностных свойств углеродного волокна на основе полиакрилонитрилла # 09, сентябрь 2013 DOI: 10.7463/0913.0620998 Страхов И. С., Губанов А. А., Устинова М. С., Кривцов Д....»

«ХИМИЯ РАСТИТЕЛЬНОГО СЫРЬЯ. 2004. №1. С. 31–34. УДК 547.474:630.892.4 ПОЛУЧЕНИЕ ПЛЕНКООБРАЗУЮЩИХ МАТЕРИАЛОВ ИЗ СУБЕРИНА КОРЫ БЕРЕЗЫ ПОВИСЛОЙ И.Г. Судакова, Б.Н. Кузнецов*, И.П. Иванов, Н.М. Иванченко Институт химии и химической технологии CO РАН, ул. К. Маркса, 42, Красноярск...»

«OPENGOST.RU www.OpenGost.ru Портал нормативных документов info@opengost.ru ФЕДЕРАЛЬНАЯ СЛУЖБА ПО ГИДРОМЕТЕОРОЛОГИИ И МОНИТОРИНГУ ОКРУЖАЮЩЕЙ СРЕДЫ (РОСГИДРОМЕТ) РД РУКОВОДЯЩИЙ ДОКУМЕНТ 52.24.406-2006 МАССОВАЯ КОНЦЕНТРАЦИЯ СУЛЬФАТОВ В ВОДАХ. МЕТОДИКА ВЫПОЛНЕНИЯ ИЗМЕРЕНИ...»

«ДОГОВОР ВОЗМЕЗДНОГО ОКАЗАНИЯ УСЛУГ №_ с. Львы (Ростов Великий), Ярославская область _ 2016г. Закрытое акционерное общество Ростовские угодья, в лице исполнительного директора Каменской Людмилы Ярославны, действующего на основании доверенности от 01.04.2016, именуемое в дальнейшем Исполнитель, и в лице, именуемое в дальнейшем Заказчик, с друго...»

«ХИМИЯ, 11 класс Анализ результатов, Март 2014 г. АНАЛИЗ РЕЗУЛЬТАТОВ краевой диагностической работы ПО ХИМИИ 11 класс (18 марта 2014 года) Краевая диагностическая работа по химии предназначена для учащихся 11 (12) классов образовательных учреждений Краснодарского края, выбравших сдачу выпускного экзамена по химии в ф...»

«Всероссийская олимпиада школьников по химии V – заключительный – этап Задания второго теоретического тура Уважаемые участники! Во второй теоретический тур включены четыре блока задач: "Неорганическая химия", "Органическая х...»

«Государственная итоговая аттестация по образовательным программам основного общего образования в форме государственного выпускного экзамена. Физика (устный экзамен) 2014-2015 учебный год Методические материалы для подготовки и проведения государственного выпус...»

«Министерство образования Республики Беларусь Учебно-методическое объединение по естественнонаучному образованию РЖДАЮ ^ ^ ^ а м е с т и т е л ь Министра образования ^ Беларусь и. Жук ЧІ6 Ітші. зационный № ТДФизиология человека и животных Типовая учебная программа для учреждений высшего обра...»

«МАТЕМАТИЧЕСКИЙ АНАЛИЗ Лектор: проф. С. К. Водопьянов 1–2-й семестры 1. Вещественные числа 1.1. Совокупности чисел, известные из школьного курса математики: натуральные числа N = {1, 2, 3,.,}, целые числа Z = {0, ± 1, ± 2, ± 3,.,}, рациональные числа. Геометрическая интерпретация...»

«Заключительный этап Всесибирской олимпиады, 2016 Физика, 7 класс Возможные решения с баллами. Максимальный балл за задачу – 10.1) Школьник проводит опыты с шарами на горизонтальной плоскости. Он стави...»

«Ракитин Вадим Станиславович МОНООКСИД УГЛЕРОДА В АТМОСФЕРЕ МЕГАПОЛИСОВ МОСКВЫ И ПЕКИНА Специальность 25.00.29 Физика атмосферы и гидросферы Автореферат диссертации на соискание ученой степени кандидата физико-математических наук Москва, 2012 г. Работа выполнена в Федеральном го...»

«Неорганическая химия: элементы и их соединения Виртуальная выставка читального зала физико-математических и естественных наук Химики лучше других понимают, как устроен мир. Лайнус Полинг, Нобелевский лауреат Неорганическая химия: элементы и их соединения Г1 А799 Ардашн...»

«С.Л. Василенко Симбиоз математики и гармонии Главная задача математики – разгадать формулу гармонии Сам по себе симбиоз1 как взаимодействие, взаимопроникновение и взаимно-полезное существование (совместная жизнь) проистекает от гармонизирующего начала. Подобно единению науки–искусства в симбиозе закономерностей гармонии и мате...»

















 
2017 www.ne.knigi-x.ru - «Бесплатная электронная библиотека - электронные матриалы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.