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

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

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

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

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

Алгоритм обнаружения:

1. Считываем среднее значение объекта по каждому из трех кодов: R, G и B.

2. Считываем кадры из видеопотока и по соотношению между R, G, B определяем удовлетворяющие данному соотношению пикселы.

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

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



Алгоритм определения объекта:

1. Загружаем кадры из видеопотока в трех экземплярах (оригинал, глубиной 8 бит с 1 каналом, глубиной 8 бит с 3 каналами).

2. Задаем пороговую величину для определения контуров, используя оригинальное изображение и изображение с 1 каналом.

3. Создаем элемент CvMemStorage, который будет хранить последовательность координат контуров.

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

5. Очерчиваем границы и считаем за объекты замкнутые контуры.

4. Вычисление расстояний, координат и угла поворота робота.

–  –  –

Для определения угла используется следующая схема (рис. 3):

F E лежит на линзе, OF фокусное расстояние камеры, DE проекция на линзу, A и B маячки. Зная фокусное расстояние OF и F D можно получить угол F DO = arctg(OF/F D), ODE = F DO.

Параллельным переносом от DE формируем линию AC. Поскольку заранее известно расстояние между маячками AB и вычислены дистанции до маячков OA и OB, то по теореме косинусов: угол OAB = arccos((AB 2 +AO2 OB 2 )/(2AB·AO)). Углом поворота робота на горизонтальной плоскости будет BAC = OAB OAC. Данный метод требует экспериментальной отладки.

5. Определение и обход препятствий. После определения препятствия O и расчета расстояния до него, робот R подъезжает к нему на фиксированную дистанцию d1 (рис. 4). Берется ширина робота и добавляется три сантиметра (d2). Робот должен отклониться на угол между d1 и d3. Преодолев расстояние d3 = d1/ cos Q, робот начинает ориентироваться по маячкам.

Рис. 4. Обход препятствия

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





–  –  –

1. Документация по библиотеке OpenCV.

http://opencv.itseez.com/

2. Документация по библиотеке OpenCV 2.1 от старых разработчиков. http://opencv.willowgarage.com/documentation/cpp/

3. Bradski G., Koehler A. Learning OpenCV: computer vision with the OpenCV library. Sebastopol, CA: O’Reilly, 2008. 578 p.

4. Форсайт Д., Понс Ж. Компьютерное зрение. Современный подход. М.: Вильямс, 2004. 928 с.

Рябуша В. А.

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

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

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

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

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

2. Основные модели облачных технологий. Облачные технологии могут быть представлены посредством трех основных моделей [2, 3]:

• программное обеспечение как услуга (SaaS, Software-as-a-Service). Данная модель предполагает предоставление программного обеспечения в облачной инфраструктуре посредством тонкого клиента, такого, как веб-браузер. При данной модели все вычисления предоставляемого приложения производятся в облачной инфраструктуре, а конечному пользователю предоставляются только результаты вычислений. Иллюстрацией такой модели может служить веб-почта, доступ к которой осуществляется посредством интернет браузера;

• платформа как услуга (PaaS, Platform-as-a-Service). В данной модели для конечного пользователя предоставляется доступ в облачной инфраструктуре к инструментальным средствам, посредством которых возможна установка, разработка, тестирование и выполнение прикладного программного обеспечения. К таким инструментам можно отнести, например, системы управления базами данных, платформы для разработки ПО, системы построения корпоративных порталов. В данной модели все вычисления, как и в модели SaaS, происходят на удаленной облачной инфраструктуре. На базе данной модели возможно построение приложений модели SaaS;

• инфраструктура как услуга (IaaS, Infrastructure-as-a-Service).

В модели такого рода конечному пользователю предоставляется возможность построения и использования облачной инфраструктуры, находящейся на удаленных серверах. Это становится возможным посредством предоставления виртуальных серверов. Используя облачные сервисы, построенные на данной модели, пользователи могут разворачивать и полностью контролировать виртуальные сети, виртуальные серверы, использовать системы хранения данных поставщика услуг. Для управления этими инфраструктурами провайдер предоставляет пользователю программный интерфейс (API). На базе данной модели возможно построение приложений модели PaaS и SaaS.

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

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

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

РУ работают под управлением систем диагностики и контроля. В качестве примера подобной системы можно указать систему EPICS [4]. Обычно для построения ВУ [5, 6] за основу берут систему управления РУ. Сигналы, поступающие на сенсоры РУ, и процессы, проходящие в РУ, в ВУ эмулируются и замещаются реализованными математическими и компьютерными моделями. Для реализации этих моделей возможно использовать математические пакеты такие, как MATLAB [7], либо непосредственное программирование на языках программирования.

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

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

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

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

Построение Виртуального ускорителя на базе облачных инфраструктур может способствовать решению всех вышеуказанных проблем. Это возможно за счет построение инфраструктур на базе виртуальных машин (ВМ) и виртуальных сетей.

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

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

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

При необходимости добавления в систему Виртуального ускорителя новых элементов на базе новых вычислительных единиц в систему добавляется новая виртуальная машина. Данная операция не требует увеличения аппаратной базы, так как на одном аппаратном вычислительном узле (АВУ) (физическом сервере) может располагаться несколько ВМ. С другой стороны, при увеличении аппаратной базы можно достичь увеличения производительности системы без перестройки системы путем перераспределения ВМ по АВУ. Также в данной облачной модели есть возможность использования шаблонов ВМ. Если реализовать типовые элементы системы ВУ на базе отдельных шаблонных ВМ, то для разработчиков системы предоставляется возможность расширять систему, выстраивая ее из наработанных деталей, как конструктор, что может значительно сократить время конструирования и расширения системы.

2. Делает возможным высокую распределенность системы, в том числе и географическую. При необходимости дополнительных аппаратных мощностей возможно распределения элементов системы в рамках ВМ по нескольким удаленным вычислительным центрам посредством использования технологий Virtual Private Network (VPN) (см. рис. 1).

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

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

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

6. Дает возможность легко перемещать экземпляры системы на сторонние аппаратные базы. В состав системы входят компоненты ВУ, представляющие собой ВМ, виртуальные сети, объединяющие ВМ, и управляющую этими ВМ и виртуальными сетями облачную систему, которая сама по себе может быть реализована на ВМ (см. рис. 1). Все это составляет облачную инфраструктуру. Понятно, что перенести или скопировать облачную инфраструктуру, состоящую из файлов и каталогов много легче, чем перенести реальную инфраструктуру на новую аппаратную базу.

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

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

Литература

1. Chao A. W., Tigner M. Handbook of accelerator physics and engineering. Singapore: World Scientic Publishing Company, 1999.

740 p.

2. Buyya R., Broberg J., Goscinski A. Cloud computing: principles and paradigms. New Jersey: John Wiley & Sons, Inc., 2011. 637 p.

3. Delgado V. Exploring the limits of cloud computing. Stockholm:

Kungliga Tekniska Hogskolan, 2010. 82 p.

4. EPICS. http://www.aps.anl.gov/epics

5. Shishlo A., Shu P., Galambos J., Pelaia T. The EPICS based virtual accelerator –– concept and implementation // Proceedings of the 2003 Particle Accelerator Conference, PAC, 2003. P. 2366–2368.

6. Harada H., Shigaki K., Noda F. et. al. Virtual accelerator as an operation tool at J-PAR 3 GEV rapid cycling synchrotron (RCS) // Proceedings of EPAC 2006. Edinburgh: EPAC, 2006. P. 2224–2226.

7. Chiu P. C., Kuo C. H., Chen J. et. al. Virtual accelerator development for the TPS // Proceedings of IPAC’10. Kyoto: IPAC,

2010. P. 2728–2730.

Севостьянов Р. А.

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

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

2. Описание робота. Аппаратную платформу робота (рис. 1) составляет плата Craftduino с микроконтроллером ATmega168 и несколькими модулями расширений: силовой модуль Motor Shield V3 для управления электромоторами и XBee Shield с установленным модулем XBee для обеспечения беспроводной связи. В качестве шасси используется платформа ROVER 5 с двумя 7,2V электромоторами. На ведущих колесах установлены квадратурные энкодеры, выдающие 1000 импульсов на три оборота. Также установлена видеокамера с беспроводным передатчиком с частотой 900 МГц. Для обеспечения питания используется три литий-полимерных аккумулятора: 7,4V для основной платы, 7,4V для силового модуля и 11,1V для видеокамеры и передатчика. Камера установлена с применением двух сервоприводов, что позволяет поворачивать ее в вертикальной и горизонтальной плоскости.

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

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

Рис. 1. Робот

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

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

Управляющий пакет для электромоторов имеет размер 6 байтов и структуру, представленную на рис. 2.

Рис. 2. Структура управляющего пакета для электромоторов

В структуру пакета входят:

• байт Begin означает начало управляющего пакета для моторов.

Он всегда содержит значение 0xAA;

• байты DirR и DirL отвечают за направление вращения правого и левого мотора, соответственно (1 вперед, 0 назад);

• байты VoltR и VoltL содержат значение напряжения, которое необходимо подать на правый и левый мотор, соответственно;

• байт Sum контрольная сумма, которая высчитывается как исключающее ИЛИ, примененное к предыдущим четырем байтам.

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

Рис. 3. Структура управляющего пакета для сервоприводов

В структуру пакета входят:

• байты Begin и Sum аналогичны соответствующим байтам управляющего пакета для электромоторов. Байт Begin всегда содержит значение 0xAB;

• байты New1 и New2 содержат флаг, сигнализирующий о том, нужно ли менять положение данного сервопривода или нет;

• байты Pos1 и Pos2, соответственно, содержат положение, в которое нужно перевести данный сервопривод.

Для программирования микроконтроллера платы CraftDuino используется язык С/C++ [2]. Структура программ довольно проста.

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

Модуль XBee подключен к серийному порту платы Craftduino, таким образом, прием управляющих команд происходит именно через него. Микроконтроллер ожидает, пока в буфере появится 6 доступных байтов, после чего записывает их в массив, сверяет контрольную сумму и выводит на серийный порт код подтверждения байт Begin. Затем, в зависимости от байта Begin, подается соответствующее напряжение и направление на электромоторы, либо изменяется положение сервоприводов.

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

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

Каждые 10 миллисекунд происходит пересчет текущей скорости.

Длина окружности колеса равна примерно 188,5 мм. Таким образом, три оборота колеса составляют около 565,5 мм, а один импульс энкодера соответствует 0,566 мм. От момента начала своей работы программа каждые 10 миллисекунд получает количество импульсов, выданные каждым энкодером, и высчитывает скорость, умножая полученное число на 0,566. Соответственно, результат, умноженный на 10, дает текущую скорость в см/с. Текущие значения скоростей можно получить, передав на микроконтроллер код 0x80. В ответ на это микроконтроллер выдаст скорости правого и левого моторов.

Стоит отметить, что максимальное время выполнения основного цикла программы микроконтроллера (функции loop()) составляет около 400 микросекунд, что является приемлемым значением для управления в режиме реального времени.

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

В режиме ручного управления программа отслеживает нажатие клавиш W, A, S, D и посылает роботу соответствующие управляющие команды. После этого ожидается прием сигнала подтверждения (это значит, что микроконтроллер сверил контрольную сумму и подал напряжение на моторы). Если в течение определенного промежутка времени сигнал не получен, пакет отсылается повторно.

Таким же образом, только с помощью ползунков снизу и справа от изображения, можно управлять поворотом камеры.

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

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

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

–  –  –

1. Строим гусеничного Bluetooth-робота с камерой. Часть 3.

http://habrahabr.ru/blogs/DIY/136224/

2. Программирование Arduino. Введение.

http://robocraft.ru/blog/arduino/29.html

3. Программирование Arduino. Структура программы, константы.

http://robocraft.ru/blog/arduino/30.html Селезнева О. В.

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

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

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

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

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

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

Минимум этого отклонения достигается на функции в частотной об

–  –  –

Функцией S здесь обозначаются энергетические спектры шума и исходного изображения соответственно. Поскольку эти величины редко бывают известны, то дробь Sµ (u, v)/Sf (u, v) заменяют на некоторую константу K, которую можно приблизительно охарактеризовать как отношение уровня сигнала к уровню шума.

Функция H(u, v) Фурье-образ искажающей функции. В зависимости от её значений можно получить различные эффекты в выходном изображении.

Поставим задачу о поиске таких H(u, v) и K, для которых получившееся изображение будет наилучшим. Наиболее адекватным критерием оценки качества изображения является зрение человека.

К сожалению, такой метод является в достаточной степени субъективным. Для количественной характеристики существуют различные методы, такие как:

• средняя разность;

• максимальная разность (maximum dierence);

• верность изображения (image delity);

• среднеквадратичная лапласианова погрешность (laplasian mean square error);

• среднеквадратичная погрешность (mean square error);

• максимальная среднеквадратичная погрешность (peak mean square error);

• отношение сигнал/шум (SNR);

• максимум отношения сигнал/шум (PSNR) и др.

–  –  –

где F изображение без шума, F отфильтрованное изображение, n, m размерности матриц.

Иными словами задача сводится к задаче нахождения

–  –  –

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

–  –  –

1. Грузман И. С., Киричук В. С., Косых В. П. и др. Цифровая обработка изображений в информационных системах: Учебное пособие. Новосибирск: Изд-во НГТУ, 2002. 352 c.

2. Сейдж Э., Мелc Дж. Теория оценивания и ее применение в связи и управлении / Пер с англ. под ред. проф. Б. Р. Левина. М.: Связь, 1976. 496 с.

Сердюк Ю. А.

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

–  –  –

Рекомендовано к публикации доцентом Добрыниным В. Ю.

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

Ключевые слова играют важную роль для современных поисковых систем. Например, сервис Яндекс.Новости использует алгоритмы поиска ключевых (опорных) слов для составления пресспортретов при определении типизированных объектов, таких как ФИО, названия организаций, географических названий и прочего [1].

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

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

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

Для этой цели разобьем текст на кластеры, или, как их еще можно назвать, текстовые единицы (textual units). Осуществить это можно различными способами, исходя из удобства разделения или каких-то логических побуждений. К примеру, если документ состоит из статьи, то можно разбивать его по 3–5 предложений или помещать в каждый кластер по определенному количеству идущих подряд слов.

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

После разделения документа необходимо составить словарь коллекции, причем каждому слову будем ставить в соответствие две числовые величины: то количество раз, с которым слово встречалось в документе (term frequency) и количество кластеров, в которых слово присутствовало. Можно заметить, что некоторые слова коллекции распределены равномерно по всему тексту. Такими словами обычно являются стоп-слова [3], которые не несут какой-то особенной смысловой нагрузки и встречаются в тексте независимо от его содержания, однако могут быть и исключения. К примеру, если взять коллекцию статей, посвященную информационному поиску, то слова информационный и поиск могут встречаться достаточно часто, и тогда они будут считаться как нехарактеризующие коллекцию. С другой стороны, если потребуется выделить ключевые слова каждой отдельно взятой статьи, то информация о том, что какая-то отдельная часть посвящена информационному поиску, не окажется полезной.

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

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

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

2.2. Математическая модель метода. Как следует из предыдущего пункта, нам требуется выбрать какой-то критерий, на основе которого можно будет объективно судить о равномерности распределения каждого отдельно взятого термина в документе. В качестве такого критерия возьмем вероятность того, что наш термин содержится ровно в N или менее кластерах при принятии гипотезы о равномерности распределения данного слова (терма).

Предположим, что текст разбит на D кластеров. Для каждого терма известно N число кластеров, содержащих данный терм, T число вхождений терма в документ с учетом повторений (term frequency).

Тогда вероятность p(n, T ) того, что ровно n кластеров содержат наш терм может быть получена вычислением

–  –  –

Сравнивая все наши термы по значению P (N, T ), можно судить о равномерности их распределения в тексте, и, соответственно, о степени значимости для документа. Слова с наименьшим P (N, T ) будут представлять для нас наибольшее значение. Для выделения ключевых слов кластера необходимо сравнить эти значения для входящих в него термов и выделить из них наиболее важные.

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

1. Поскольку при вычислении P (N, T ) формально вычисляется сумма дробей p(n, T ), знаменатели которых равны, рекомендуется сначала найти сумму числителей, а потом уже поделить на общий знаменатель.

2. После составления словаря можно откинуть несколько наиболее часто употребляемых термов. Для вычисления P (N, T ) для таких слов, в связи с достаточно большими значениями N и T, требуется больше времени, чем для других термов, а поскольку стопслова не представляют ценности, то вычисление P (N, T ) для них не целесообразно.

3. После составления словаря можно найти максимальные значения N и T и составить с требуемой размерностью массив чисел Стирлинга, используя рекуррентную формулу и при вычислении p(n, T ) просто считывать уже имеющиеся результаты. Это значительно ускорит процесс вычисления.

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

Для получения наиболее объективных результатов, были взяты статьи из двух энциклопедий: первые 150 из Большой советской энциклопедии [5] и 150 случайных из англоязычной Британники [6]. В данном случае каждая отдельная статья принималась как отдельный кластер. Поскольку в Британнике статьи в большинстве случаев достаточно длинные и иногда могут состоять из нескольких тысяч слов, для эксперимента брались только первые сто термов.

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

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

–  –  –

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

– ключевые слова.

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

Однако существуют документы, для которых данный алгоритм показывает не самые лучшие результаты. К примеру, для новостной коллекции агентства Рейтер [8] полученные ключевые слова зачастую не являлись достаточно релевантными. Скорее всего это связано со сравнительно небольшим размером статей. А поскольку новости были посвящены достаточно широкому кругу тематик, выделить нужные термы было сложнее. Чаще выделялись слова, не несущие особой смысловой нагрузки, а просто достаточно часто употреблявшиеся в тексте (without, else).

3. Заключение. Представленный алгоритм обладает рядом положительных качеств: он не требует каких-то дополнительных баз (словарей, списков стоп-слов) и в большинстве случаев дает достаточно качественные результаты даже для небольшой коллекции любой тематики, на любом языке языка. Однако он достаточно трудоемкий, требует немалого количества времени для вычислений и достаточного объема памяти. Так, если словарь состоит из нескольких тысяч слов, текст разбит на большое количество кластеров, то вероятность P (N, T ) для некоторых термов может иметь первую цифру, отличную от нуля, на 500-ой позиции после запятой и даже дальше.

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

Литература

1. Пресс-портреты – Яндекс.Помощь: новости.

http://help.yandex.ru/news/?id=1111171

2. Bookstain A., Klein S. T., Raita T. Detecting content-bearing words by serial clustering // Proceedings of the Eighteenth Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. 1995. P. 319–327.

3. Стоп-слова и списки стоп-слов.

http://msdn.microsoft.com/ru-ru/library/ms142551.aspx

4. Stirling number of the second kind. http://mathworld.wolfram.

com/StirlingNumberoftheSecondKind.html

5. БСЭ – Яндекс.Словари. http://slovari.yandex.ru/~книги/БСЭ

6. Encyclopaedia Britannica online. http://www.britannica.com/

7. The porter stemming algorithm.

http://tartarus.org/martin/PorterStemmer/

8. Archive reuters-21578. http://www.daviddlewis.com/resources/ testcollections/reuters21578/ Сюэ Юаньюань Санкт-Петербургский государственный университет Компьютерное моделирование системы управления движением автомобиля Рекомендовано к публикации профессором Веремеем Е. И.

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

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

2. Уравнения движения автомобиля. Рассмотрим автомобиль как динамический объект, на вход которого поступают управляющее воздействие u(t), определяемое скоростью поворота управляющей колесной пары, и возмущающее воздействие d(t), в качестве которого выступают соответствующие внешние силы и моменты. В качестве исходных уравнений динамики примем следующую систему [2–4]:

–  –  –

Здесь z угловая скорость по курсу, x угловая скорость по крену, угол курса, угол крена, угол дрейфа, угол поворота колес. Кроме того, использованы обозначения Iz, Ix, Ixz для соответствующих моментов инерции, параметры m, ms представляют массы автомобиля и подвески автомобиля, а остальные обозначения в (1) задают соответствующие динамические коэффициенты, которые зависят от скорости движения.

Будем считать, что измеряемыми динамическими параметрами служат все компоненты вектора состояния автомобиля. Тогда уравнения линейного приближения, представляющие процесс управления автомобилем (АС770) при движении на заданной прямолинейной траектории с постоянной скоростью V = 60 км/ч, принимают вид

–  –  –

k1 = 4,5846, k2 = 4,0866, k3 = 4,3589, k4 = 1,3854, k5 = 18,063;

k1 = 0,4072, k2 = 0,9544, k3 = 1,1255, k4 = 0,3846, k5 = 3,3366.

4. Компьютерная модель замкнутой системы. Для формирования компьютерной модели воспользуемся инструментальной системой Simulink в среде MATLAB. Схема компьютерной модели приведена на рис. 1.

Рис. 1. Simulink-модель замкнутой систем управления курсом На приведенной схеме показаны следующие блоки: блок Constant для ввода в систему желаемого командного сигнала по курсу, блок Integrator Limited, задающий ограничение на угол поворота колес, блоки B и A*u, задающие постоянные матрицы, которые вместе с сумматором используются для формирования правых частей уравнений систем (2). Блок Integrator позволяет определить на выходе вектор состояния. Блок K*u моделирует обратную связь в замкнутой системе.

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

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

5. Результаты компьютерного моделирования. Динамические переменные, полученные в виде соответствующих функций времени в ходе проведения вычислительного эксперимента, для процессов разворота автомобиля на угол 0 = 50 приведены в виде соответствующих графиков угла поворота, угла курса и угла крена на рис. 2, 3.

При c = 0,1 процесс поворота завершается через 4 сек (рис. 2) с достаточно малым перерегулированием. При этом максимальное значение угла крена не превышает 7.

–  –  –

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

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

–  –  –

1. Хачатуров А. А. Динамика системы дорога шина автомобиль водитель. М.: Машиностроение, 1976. 535 с.

2. Guo Konghui. Динамика управления автомобилем. Чанчунь, 1991 (на китайском языке). 683 с.

3. Ротенберг Р. В. Подвеска автомобиля. М.: Машиностроение, 1972. 392 с.

4. Segel L. On the lateral stability and control of the automobile as inuenced by the dynamics of the steering system // ASME Journal of Engineering for Industry, 1966. P. 283–295.

Федотова А. О.

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

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

Одним из популярных подходов к решению этой задачи является метод наименьших квадратов (МНК) [1], однако ему присущи определенные недостатки, препятствующие практическому применению.

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

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

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

На нейрон подаются входные сигналы u1,..., un, которые умножаются на соответствующие весовые множители wi и суммируются вместе с начальным смещением b. Выходной сигнал нейрона n y=f ui wi + b, i=1 где f функция активации. В зависимости от рассматриваемой задачи удобнее использовать ту или иную функцию активации (линейную, сигмоидную, пороговую и пр.).

Одним из главных преимуществ нейронных сетей перед традиционными алгоритмами является возможность их обучения. Если задано некоторое обучающее множество (p1, t1 ),..., (pN, tN ), где pi входные векторы сети, ti соответствующие целевые выходы, то задача обучения нейронной сети сводится к поиску весовых коэффициентов wi таких, чтобы расхождение целевого выхода и выхода нейронной сети было минимальным.

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

–  –  –

Управление u в системе (2) задается в виде обратной связи u = K1 + K2 ( ) + K3, обеспечивающей устойчивость замкнутой линейной системы и отработку заданной курсовой командной поправки.

Линейная модель (2) может быть представлена в матричном виде

–  –  –

где A матрица состояний, B матрица входов, C матрица выходов, x вектор состояния, управление, y выход объекта управления.

В силу особенностей структуры нейронной сети в дальнейшем будет удобно рассматривать дискретный аналог модели (3) с шагом дискретизации t = 0, 02 с:

–  –  –

5. Постановка задачи идентификации. Коэффициенты линейной дискретной модели судна (4), полученные из (1) путем линеаризации, неточны и выступают в качестве неизвестных параметров. Задача идентификации линейной модели судна сводится к поиску компонентов постоянных матриц Ad и Bd размерностей 2 2 и 2 1 соответственно, которые обеспечивают наименьшее значение невязки выхода построенной модели y с измеряемым выходом динамического объекта yp. В качестве меры расхождения выходов y и yp можно рассмотреть среднеквадратическое отклонение. Тогда критерий выбора коэффициентов дискретной линейной подели (4) представляется в виде n (y (k) yp (k)) min, (5) n A,B k=1 где n количество данных обучающего множества (количество последовательных наблюдений за выходом объекта управления yp с тактом t).

6. Архитектуры ИНС и построение обучающих данных.

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

Поставленная задача идентификации будет считаться решенной, если матрица входных весов Wi и матрица весов обратной связи Wl обученной нейронной сети будут совпадать соответственно с матрицами дискретной модели Bd и Ad с заранее заданной точностью = 5% по отношению к известному тестовому варианту.

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

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

–  –  –

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

7. Обучение НС и оценка результатов. Обучение нейронной сети производится в среде MATLAB с использованием метода градиентного спуска с учетом моментов (learngdm). Для оценки функционирования сети выбрана функция среднеквадратического отклонения (mse).

После обучения нейронной сети ее обобщающие свойства были проверены на тестовом множестве, и среднеквадратическое отклонение составило 7, 25 · 109.

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

–  –  –

Таким образом, все полученные коэффициенты удовлетворяют заранее заданной точности = 5%.

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

Литература

1. Дилигенская А. Н. Идентификация объектов управления. Самара: Самар. гос. техн. ун-т., 2009. 136 с.

2. Хайкин C. Нейронные сети. М.: Вильямс, 2006. 1104 с.

3. Веремей Е. И., Корчанов В. М., Коровкин М. В., Погожев С. В.

Компьютерное моделирование систем управления движением морских подвижных объектов. СПб.: НИИ Химии СПбГУ, 2002.

370 с.

Хромов А. А.

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

–  –  –

Рекомендовано к публикации доцентом Сотниковой М. В.

1. Введение. На сегодняшний день существует множество практических задач, для решения которых применяются спектральные изображения. Преимущество в их использовании заключается в том, что они содержат гораздо больше информации по сравнению с обычными RGB-изображениями. Каждый пиксель такого изображения хранит информацию о спектральной отражательной способности объекта. Таким образом, в отличии от обычного изображения, спектральное представляет объект в определенном спектральном диапазоне длин волн. Основным недостатком спектральных изображений является большой размер памяти, требуемой для их хранения. Традиционным подходом к сжатию спектральных изображений является метод главных компонент [1]. Известны некоторые улучшения этого метода, базирующиеся на использовании алгоритмов кластеризации [2]. В настоящей работе предлагается алгоритм сжатия спектральных изображений с использованием вейвлетпреобразования (ВП). Особенностью предлагаемого подхода являются контролируемые потери при сжатии. Эффективность разработанного метода продемонстрирована на конкретном примере.

2. Постановка задачи сжатия спектральных изображений. Спектральное изображение представляет собой трехмерную матрицу данных размером M N L, где M N размер изображения, а L размерность спектрального пространства. Поставим формализованную задачу о сжатии спектрального изображения. Введем следующие обозначения: I0 (x, y, ) исходное спектральное изображение, Ic (x, y, ) сжатое изображение. Здесь x, y координаты пикселя изображения, значение длины волны в определенном спектральном диапазоне. Введем следующий критерий степени сжа

–  –  –

где I0j,i, Ij,i значение исходного и восстановленного по сжатому спектральных изображений для i-го пикселя и j-ой длины волны спектрального диапазона. Характеристика потерь (2) показывает среднее значение квадрата евклидова расстояния между точками оригинального и восстановленного изображений. Таким образом, в дальнейшем будем рассматривать задачу о максимизации критерия (1) при наличии ограничения

F,

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

3. Сжатие спектральных изображений с использованием метода главных компонент. Представим спектральное изобраMN жение в следующем виде: I = {Xi }i=1, Xi RL, где M высота изображения, N длина, а L размерность спектрального пространства. Цель метода главных компонент уменьшить размерность данных с помощью поиска подпространства меньшей размерности, в ортогональной проекции на оси которого разброс данных максимален. Идея метода заключается в вычислении ковариационMN T ной матрицы C = M1N i=1 (Xi µx ) (Xi µx ), где µx математическое ожидание векторов Xi [1], Затем находятся её собственные значения и соответствующие им собственные векторы. Выбираются t векторов (главные компоненты), соответствующих максимальным собственным значениям. Эти векторы определяют направления наибольшей дисперсии данных и формируют базис нового подпространства размерности t. Проекции векторов Xi на координатные оси этого подпространства вычисляются по формуле

–  –  –

где i отброшенные собственные числа матрицы C.

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

4.1. Базовые идеи применения вейвлет-преобразования для сжатия изображений. Вейвлет-преобразование позволяет осуществить переход от исходного изображения к четырем новым изображениям, размеры которых вдвое меньше оригинала. Первое из изображений является усредненным значением оригинала, а три других изображения деталей, удаленных при усреднении [3]. Пиксели сглаженного изображения называются коэффициентами аппроксимации, а пиксели изображений деталей коэффициентами детализации. Вейвлет-преобразование осуществляется с помощью операции фильтрации и прореживающей выборки [4]. Для выполнения фильтрации используется два фильтра высоких и низких частот. При этом фильтрация осуществляется последовательно сначала по столбцам, затем по строкам. После каждого этапа фильтрации выполняется прореживающая выборка. В данной работе применялись фильтры Хаара. Усредненное изображение можно также подвергнуть вейвлет-преобразованию, повысив тем самым глубину разложения. Особенностью вейвлет-преобразования является то, что в областях гладких значений изображения коэффициенты детализации близки к нулевым и ими можно пренебречь, а количество коэффициентов аппроксимации экспоненциально уменьшается с повышением глубины разложения.

4.2. Применение вейвлет-преобразования для сжатия спектрального изображения. В результате применения метода главных компонент, получаем спектральное изображение размером M N t. Применим к каждому слою вейвлет-преобразование.

Получившийся набор коэффициентов подвергнем квантованию по следующему правилу:

• если |c| q, то c = 0,

• если |c| q, то округляем его до k-го знака после запятой так, чтобы |c c | q, где c коэффициенты вейвлет-преобразования, а q коэффициент квантования, одинаковый для всех слоев. Данное правило гарантирует, что квантованные коэффициенты будут отличаться от оригинальных меньше, чем на q. Чем больше q, тем больше коэффициентов обнулится или аппроксимируется целым числом. В результате применения процедуры квантования получаем t разреженных матриц, для хранения которых нужно запоминать только ненулевые элементы и их расположение в матрице.

Исследуем вопрос о выборе коэффициента квантования q.

Для этого рассмотрим два изображения: A1 = {Xi }M N, Xi RL, восстаi=1 новленное после применения метода главных компонент к исходному спектральному изображению, и A2 = {Xi }M N, Xi RL, восстаi=1 новленное после применения метода главных компонент и вейвлетпреобразования к оригиналу:

–  –  –

Здесь CR1 степень сжатия изображения после применения метода главных компонент, CR2 после применения метода ГК и ВП.

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

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

–  –  –

1. Померанцев А. Л. Метод Главных Компонент (PCA).

http://rcs.chph.ras.ru/Tutorials/pca.htm

2. Andriyashin A., Miyata K., Parkkinen J. P. Spectral images archive compression // Процессы управления и устойчивость: Труды 37й международной научной конференции аспирантов и студентов / Под ред. Н. В. Смирнова, Г. Ш. Тамасяна. СПб.: Издат. Дом С.-Петерб. гос. ун-та, 2006. С. 249 254.

3. Уэлстид С. Фракталы и вейвлеты для сжатия изображений в действии. М.: Триумф, 2003. 320 с.

4. Гонсалес Р., Вудс Р. Цифровая обработка изображений. М.: Техносфера, 2006. 1072 с.

Шолохова А. А.

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

Введение. Одним из направлений деятельности управления по работе со страховыми медицинскими организациями (СМО) Территориального фонда обязательного медицинского страхования в Санкт-Петербурге (ТФОМС) является мониторинг выполнения медицинскими организациями (МО) базовых плановых заданий, являющихся плановыми объемами финансирования, которые утверждаются на заседании комиссии по разработке Территориальной программы обязательного медицинского страхования. Плановые задания устанавливаются в начале календарного года по периодам в разрезе СМО и могут быть изменены в течение года.

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

Алгоритм. Блок-схема поступления данных в управление по работе со СМО ТФОМС и обработки данных программой представлена на рис. 1.

Рис. 1. Блок-схема обработки данных Данные поступают из Комитета по здравоохранению в СанктПетербурге и Контрольно-ревизионного управления в таблицах приложения Microsoft Oce Excel. Получаемые данные избыточны, поэтому для устранения избыточности данных созданную базу данных приложения Microsoft Oce Access приводят к третьей нормальной форме.

В базе данных «Мониторинг выполнения медицинскими организациями базовых плановых заданий» МО и СМО, участвующие в программе ОМС, идентифицируются с помощью кодов, которые используются в отделе информационных систем ТФОМС.

Дополнительно поступают следующие данные:

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

• возвраты –– сумма средств, возвращенная из МО в СМО, но не учтенная в информационных системах взаиморасчетов по ОМС;

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

К базе данных написано приложение на языке Visual Basic for

Application. Интерфейс приложения состоит из четырех форм:

• мониторинг выполнения МО базовых плановых заданий –– основная форма;

• импорт данных –– форма, позволяющая импортировать данные и просматривать информацию о последних загруженных данных (названия, пути);

• мониторинг в разрезе МО;

• мониторинг в разрезе МО и СМО.

Импорт данных и их обработка выполняются с помощью SQL запросов, прописанных в коде приложения.

Алгоритмы мониторинга выполнения МО плановых заданий в разрезе МО и в разрезе МО и СМО представлены на рис. 2, 3.

–  –  –

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

Результат работы программы в случае мониторинга в разрезе МО — два отношения, первое из которых содержит сведения о МО, выполнивших базовое плановое задание (рис. 4), а второе –– сведения о не выполнивших (рис. 5).

Указанные отношения имеют следующие атрибуты:

• наименование МО — название медицинской организации;

• план –– плановое задание медицинских организаций на выбранный период;

• % –– процент выполнения планового задания на период;

• дата –– дата выполнения планового задания (в отношении 1) или дата последнего оплаченного счета (в отношении 2);

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

Результатом работы программы в случае мониторинга в разрезе МО и СМО является отношение, представленное на рис. 6.

Рис. 4. Результат мониторинга в разрезе МО: МО, перевыполнившие плановое задание

–  –  –

Отношение имеет следующие атрибуты:

• наименование –– название медицинской организации;

• СМО –– наименование страховой медицинской организации;

• план –– плановое задание МО по указанной СМО;

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

• % –– процент выполнения планового задания на период.

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

Литература

1. Правила обязательного медицинского страхования.

http://www.rg.ru/2011/03/10/oms-pravila-dok.html

2. Гандерлой М., Харкинз С. С. Автоматизация Microsoft Access с помощью VBA. М.: Вильямс, 2006. 416 с.

3. Дейт К. Дж. Введение в системы баз данных. М.: Вильямс, 2005.

1328 с.

Щеглов А. К.1, Щеглов Д. К.2 Санкт-Петербургский государственный университет ОАО Конструкторское бюро специального машиностроения Концепция модернизации системы управления эксплуатацией объектов наземной космической инфраструктуры на современном этапе развития информационных технологий Рекомендовано к публикации профессором Смирновым Н. В.

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

Непременным условием решения любой из задач космической деятельности является гарантированная возможность проведения запусков космических аппаратов (КА), которая, в том числе, определяется состоянием ключевых объектов наземной космической инфраструктуры (НКИ) [2].

В современных экономических условиях функционирование системы эксплуатации (СЭ) НКИ характеризуется [3, 4]:

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

• усложнением эксплуатационных процессов и расширением информационных связей между элементами СЭ;

• систематической модернизацией составных частей существующих объектов НКИ в сокращенные сроки и/или под конкретный запуск КА;

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

• привлечением в состав кооперирования по созданию объектов НКИ соисполнителей ранее не работавших в системе стандартов системы вооружения и военной техники;

• увеличением удельной доли расходов на информационный обмен между элементами СЭ объектов НКИ относительно расходов на материальные потоки.

Применение современных информационных и коммуникационных технологий (ИКТ) позволяет качественно модернизировать существующую систему управления (СУ) эксплуатацией НКИ [5].

2. Система управления эксплуатацией объектов НКИ с точки зрения системного анализа. Предлагается классифицировать СЭ объектов НКИ как открытую организационно-техническую систему.

Разработка любой СУ предполагает, прежде всего, определение управляемых объектов (УО) и управляющих воздействий (УВ).

Основными элементами СЭ объектов НКИ, на которые может быть оказано какое-либо воздействие, являются:

• персонал, обеспечивающий функционирование СЭ;

• собственно объекты НКИ и их составные части;

• эксплуатационные процессы (процессы взаимодействия персонала и объектов НКИ).

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

Если УО объект НКИ, то управлять можно состоянием объектов НКИ и их составных частей. В качестве УВ в этом случае выступают управленческие и технические мероприятия, совокупности и комбинации которых, по сути, являются эксплуатационными процессами (ЭП).

К основными ЭП, по нашему мнению, целесообразно отнести:

• техническое обслуживание изделий объектов НКИ;

• доработки (модернизация) изделий объектов НКИ;

• оценка технического состояния объектов НКИ и входящих в их состав объектов надзора;

• восстановление технической готовности объектов НКИ при возникновении неисправностей и отказов;

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

• метрологическое обеспечение эксплуатации объектов НКИ;

• другие виды обеспечения эксплуатации объектов НКИ.

При реализации ЭП управление нацелено на их операционные свойства: результативность, ресурсоемкость, оперативность. Влияние на них осуществляется путем перераспределения ресурсов, изменения структуры процессов и условий их реализации.

3. Контуры управления эксплуатацией объектов НКИ.

Управление эксплуатацией объектов НКИ, по нашему мнению, целесообразно разделить на следующие контуры управления:

• техническим состоянием объектов НКИ;

• запасами элементов замены оборудования объектов НКИ;

• эксплуатационными процессами;

• персоналом в СЭ.

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

1. Управление техническим состоянием (ТСт) подразумевает наличие соответствующей системы мониторинга ТСт непосредственно в составе объекта НКИ [2]. Базы данных мониторинга ТСт обеспечивают решение обратных задач теории управления измеряемости и идентифицируемости. Целью управления ТСт является обеспечение безотказного функционирования объектов НКИ на заданном интервале времени.

На практике обычно применяются следующие стратегии управления ТСт:

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

• управление по фактическому состоянию;

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

2. Управление запасами элементов замены осуществляется системой обеспечения запасами (СОЗ). Под СОЗ понимается совокупность мест сосредоточения запасов, материальных и информационных потоков.

Интеграция СОЗ с системой мониторинга ТСт, осуществляемая на основе современных ИКТ, позволяет перейти к адаптивной стратегии управления запасами. Это подразумевает включение в состав

СОЗ следующих моделей:

• оценивания и прогнозирования технического состояния элементов оборудования объектов НКИ;

• расчета показателей надежности объектов НКИ с учетом восстановления в ходе ремонтно-профилактических и ремонтновосстановительных работ.

3. Управление эксплуатационными процессами направлено на поиск и применение наиболее эффективных способов эксплуатации объектов НКИ (под эффективностью понимается комплексное свойство целенаправленного процесса применения объекта, а не самого объекта). Основными (количественными) показателями эффективности ЭП является расход времени и ресурсов всех видов в процессе эксплуатации объекта НКИ.

4. Планирование и оперативное управление. Процессный подход подразумевает наличие в составе комплексной СУ эксплуатацией объектов НКИ двух групп процессов: планирования эксплуатации и оперативного управления эксплуатацией.

Планирование эксплуатации это разработка УВ, переводящего СЭ из положения на момент планирования в требуемое положение на конец планового периода.

Оперативное управление это управление, осуществляемое непосредственно в ходе решения конкретных задач по эксплуатации объектов НКИ, для парирования отклонений, вызванных различными причинами (отказы, ошибки персонала, стихийные бедствия и т. п.).

Оперативное управление ЭП осуществляется посредством изменения заданий персоналу и перераспределения ресурсов.

Таким образом, для эффективного управления ЭП необходимо традиционно решать задачи двух типов:

• выработать оптимальный план выполнения работ, входящих в процесс;

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

Удобным научно-математическим инструментарием для решения задач управления ЭП, являются сетевые модели, которые можно разделить на:

• детерминированные, в том числе, метод CPM (Critical Path Method, критического пути) и методы управления на основе сетей Петри;

• стохастические, например, метод PERT (Program Evaluation and Review Technique, анализа и оценки программ) и метод GERT (Graphical Evaluation and Review Technique, анализа и графической оценки).

5. Архитектура интегрированной информационной СУ эксплуатацией объектов НКИ. Обобщенная архитектура этой системы, разработанная на базе всех изложенных выше рассуждений, представлена на рис. 2.

Рис. 1. Архитектура интегрированной СУ эксплуатацией объектов НКИ

Как видно из рис. 2, предлагается следующий подход к построению системы:

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

2. Каждой задаче из сформированного множества поставить в соответствие программный (или аппаратно-программный) модуль, обеспечивающий ее решение.

3. Провести агрегацию всех модулей с целью организации интегрированной информационной СУ эксплуатацией.

6. Заключение. В данной работе проведено некоторое обобщение и систематизация современных представлений о модернизации существующей СУ эксплуатацией объектов НКИ с учетом возможностей передовых ИКТ. Предложенный подход к построению интегрированной информационной СУ в целом является универсальным. В зависимости от постановки задачи он может применяться не только для любых видов изделий, но и для создания СУ этими изделиями на различных этапах их жизненного цикла.

Литература

1. Федеральный закон О космической деятельности от 29.11.1996, № 147-ФЗ.

2. Управление наземной космической инфраструктурой на основе мониторинга ее состояния: монография / Перминов А. Н. СПб.:

ВКА имени А. Ф. Можайского, 2005. 320 с.

3. Данилова Л. Г., Королькова О. В., Щеглов Д. К. Особенности построения системы управления эксплуатацией объектов наземной космической инфраструктуры // В. сб. трудов IV Общероссийской НТК Молодежь. Техника. Космос.. СПб.: БГТУ Военмех, 2012. С. 264–269.

4. Громыко Ю. В. Реструктурация космической отрасли как насущная проблема.

http://www.situation.ru/app/j_art_1183.htm

5. Стенограмма выступления руководителя ФКА в ГД 07.10.2011.

http://www.eifgaz.ru/popovkin42-11.htm Ялов А. Л.

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

1. Генетические алгоритмы. Ниже будут рассмотрены основные тезисы генетических алгоритмов (ГА) и приведено краткое описание стандартного ГА.

1.1. Основные тезисы. ГА это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию [1].

ГА заимствуют из биологии [2]:

• понятийный аппарат;

• идею коллективного поиска экстремума при помощи популяции особей;

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

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

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

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

1.2. Стандартный ГА. Стандартный вариант генетического алгоритма был предложен Фразером [3]. Как показали последующие исследования, данный метод оказался эффективным не только при решении реальных инженерных проблем, но и при исследовании биологических проблем, например, при моделировании иммунной системы [4]. Канонический генетический алгоритм характеризуется следующими особенностями:

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

2. Задается функция оптимальности, определяющая эффективность каждого найденного решения.

3. Каждой хромосоме xi присваивается значение эффективности µ(xi ) в соответствии с функцией оптимальности и вероятность воспроизведения pi, которая зависит от эффективности данной хромосомы.

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

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

5. Процесс останавливается, если получено удовлетворительное решение, либо если исчерпано отведенное на эволюцию время.

Если процесс не окончен, то вновь повторяются процессы оценки и воспроизведения новой популяции.

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

Ptotal = x1 Pind + x2 Pdep. Задача заключается в поиске таких x1 и x2, чтобы EER (Equal Error Rate) [5] общего решения была минимальна.

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

3.1. Входные данные. Файл с 3 млн. строк вида ai ; bi ; ci, где ai, bi значения в процентах, полученные в результате работы данных алгоритмов (Pind и Pdep ), ci (bool) совпадает или не совпадает объект с образом.

3.2. Реализация. Задача выполнялась в среде MATLAB при следующих эволюционных показателях:

• вектор искомых параметров ограничен

–  –  –

где функция Хевисайда. Цель минимизировать F (X);

• размер популяции 100 особей на каждой итерации алгоритма;

• на каждой итерации 80% особей создаются путем скрещивания, 20% путем мутации;

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

• скрещивание происходит рассеянным образом: генерируется случайный двоичный вектор соответствия родителей, например, [0, 0, 1, 0, 0, 1,..., 1, 1, 0, 1, 0], где 0 элементы одного родителя, 1 элементы другого родителя;

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

• критерий остановки 100 малоотличающихся поколений.

3.3. Итоги. Плюсы метода для данной задачи:

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

2. При большой размерности задачи быстрая обработка (по отношению к другим методам).

3. Легкость программирования.

Отметим минус метода для данной задачи: при небольшой размерности задачи долгое время обработки (по отношению к другим методам).

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

Таблица. Сравнение алгоритмов

–  –  –

1. Wikipedia. http://wikipedia.org

2. Вороновский Г. К., Махотило К. В., Петрашев С. Н., Сергеев С. А.

Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности. Х.: ОСНОВА, 1997. 112 с.

3. Fraser A. S. Simulation of genetic systems // J. of Theor. Biol., 1962.

Vol. 2. P. 329–346.

4. Скурихин А. Н. Генетические алгоритмы // Новости искусственного интеллекта, 1995. № 4, C. 6–46.

5. Anil K. Jain, Patrick Flynn, Arun A. Ross. Handbook of biometrics.

Springer Science+Business Media, LLC, 2008. 564 p.

Aleynik S. V., Grishkin V. M., Korolev A. I., Sukhmel V. A., Timoshenko D. M.

Saint-Petersburg State University Automatic preprocessing technique for detection of corrupted speech signal fragments for the purpose of speaker verication

1. Introduction. Audio recording (input signal for speaker verication system) can be achieved using various sources. It can be GSM channel, audio-recorder in a closed studio or outside, etc. Unfortunately, as a result at the input of our system we often have a mixture of distorted speech signal with various additive noises. Two classic approaches to handle this problem are well-known. First, it is increasing of algorithms robustness: feature compensation [1], models adaptation [2], score normalization [3], etc. Second, it is using dierent noise cancellation techniques [4] at the input stage. Although all these methods generally lead to a better system performance, the verication quality degrades when the noise level is high or when input signal is seriously distorted. At the same time it has been found in practice that real-world audio signals in many cases are partially (not totally) corrupted. For example, GSMbursts or telephone bells are short-time noises that may be detected easily. Also strongly clipped fragments of speech signal usually adjoin with not-clipped fragments. So it is clear that “preprocessing technique” which detects corrupted (i.e. distorted or with a high level of noise) fragments of input signals and then rejects them from the next stages of processing, may be useful for automatic speaker verication performance.

In the presented paper we tested the performance of our preprocessing technique with the use of speaker verication system based on i-vectors, described in [5, 6]. This paper is organized as follows. In Section 2, we provide a brief description of the preprocessing technique, components, and workow. In Section 3, we discuss every detector more precisely.

Simulation results are presented in Section 4 as an eciency proof.

Finally, in Section 5 we draw conclusions from this work.

2. Preprocessing technique. The structure of proposed preprocessing is presented in Fig. 1, and contains dierent components, such as three levels of detectors, two resampling units and two logic units.

–  –  –

3. Detectors. The structure of detectors used is presented in this section.

3.1. Clicks detector. One of the click detection methods we used is proposed in [7].

3.2. Overloads detector. We consider here “overloading” as “sharp sign changing” caused by integer overow. In practice, one of the most frequently used quantization in digital audio processing is 16-bit quantization. So every digital signal sample is “short int” value (ANSI) within the limits from 32768 to 32767. In this case if we process our signal in oating point format, and the result is out of [32768, 32767] range we will get “sharp sign changing” when we try to transform our signal to 16-bit value at the output stage, for example. The most common overloading detection algorithm is described in [5, 6].

3.3. Clipping detector. Clipping often occurs when an amplier is overdriven and attempts to deliver an output signal beyond its maximum capability. In digital clipped signal a number of samples are grouped near the maximum and/or minimum of the signal dynamic range borders (soft clipping) or simply equal to the borders (hard clipping).

There are deferent approaches to detect clipping [5, 6]. In our preprocessing system we (as well as in [8]) use signal histogram.

3.4. SNR evaluation module. SNR is one of the most common and important factors that aects the quality of speaker recognition system. Thus, information about integral SNR value along the whole signal and the value of SNR in particular frequency domains is critically important. In this paper we us an adaptive algorithm for robust SNR evaluation, described in [9] and based on INR value estimation.

3.5. Beep detector. Beeps are well-known telephone single-tone or dual-tones harmonical impulses. An important point is that amplitude of beep signal is high and frequency of carrier harmonic(s) is very stable (in contrast with a speech signal). In the presented preprocessing system there are two algorithms to detect beeps: rst is based on the number of maximums in spectrum and second is based on the constancy of the maximums amplitudes. Both of these algorithms are described in [4].

3.6. Tone detector. Beep detector detects single-tone signals well enough, but to increase the detection quality we developed separate algorithm for such kind of the signals. In this algorithm we use longterm and fast-term averaging of the magnitude spectrum as in [4].

3.7. Music detector. In the present work we used well-known music detection algorithm based on spectral peaks analysis[10, 11].

3.8. Voice activity detector. A number of voice activity detection techniques have been proposed over the past decade. In our preprocessing we use VAD algorithm based on power envelope dynamics described in [12, 13].

4. Experiments and results. To study how our preprocessing technique inuences the verication system quality we carried out a series of experiments. In the experiments we used speaker verication system based on i-vectors described in [5, 6]. Classical MFCC-39 were used as feature vectors, the UBM and Total variability matrix dimensions were taken as 512 and 400 correspondingly. The system was trained on NIST SRE 99-2008 database, total number of les for training were about 60000. For verication system and preprocessing technique testing we took phonogram base of telephone conversations in GSM channel (610 phonograms, 151 speakers) and the base of microphone interviews (467 phonograms, 120 speakers). It is important to note that we do not delete noises and corrupted signal fragments from the phonogram: tones and beeps (DTMF signals, for example), switching clicks, background noise and music, etc. The verication experiment was repeated several times with dierent set of preprocessing detectors as it shown in the table (“” and “+” means “on” or “o” for the corresponding detector).

Table 1. Equal error rates for the dierent detectors combinations Clicks Overloads Music Beeps Tones VAD EER, % 21.

2 + 11.3 + + 9.9 + + + 9.8 + + + + 9.8 + + + + + 8.4 + + + + + + 6.8 The results demonstrate that we achieved signicant increase in speaker verication using the whole set of detectors. Voice activity detector (VAD) is the most ecient one. This fact also indicates that VAD must be the last detector in the sequence of the detectors when the other interfering noises are already detected. The rest of the detectors also lead to the verication quality performance.

5. Conclusions. In this study an automatic preprocessing technique for corrupted audio signal detection was presented. The experimental results prove the ecient of the described algorithms and methods. This technique is suitable for cases with partially corrupted input signal. Our investigation shows that performance of a speaker verication system may be signicantly increased using proposed technique. However, it should be kept in mind that some algorithms (and/or parameters: levels, time intervals, etc.) require further experimental evaluation.

–  –  –

1. Vair C., Colibro D., Castaldo F. et al. Channel factors compensation in model and feature domain for speaker recognition // Speaker and Language Recognition Workshop, 2006. P. 1–6.

2. Reynolds D. A., Quatieri T. F., Dunn R. B. Speaker verication using adapted Gaussian mixture models // Digital Signal Processing, 2000.

Vol. 10. P. 19–41.

3. Auckenthaler R., Carey M., Lloyd-Thomas H. Score normalization for text-independent speaker verication systems // Digital Signal Processing, 2000. Vol. 10. P. 42–54.

4. Bitzer J., Brandt M. Speech enhancement by adaptive noise cancellation: problems, algorithms and limits // Audio Engineering

Society Conference: 39th International Conference: Audio Forensics:

Practices and Challenges, 2010.

5. Dehak N., Kenny P., Dehak R. et al. Front-end factor analysis for speaker verication // IEEE Transactions on Audio, Speech and Language Processing, 2011. Vol. 19(4). P. 788–798.

6. Senoussaoui M., Kenny P., Dehak N., and Dumouchel P. An i-vector extractor suitable for speaker recognition with both microphone and telephone speech // Proc. IEEE Odyssey Workshop, 2010. P. 28–33.

7. Esquef P., Karjalainen M. Detection of clicks in audio signals using warped linear prediction // 14th Int. Conference on Digital Signal Processing, 2002. Vol. 2. P. 1085–1088.

8. Otani T., Tanaka M., Ota Y., Ito S. Clipping detection device and method. US Patent 20100030555 A1, 2010.

9. Hirsch H. G. Estimation of noise spectrum and its application to SNR-estimation and speech enhancement // ICSI Technical report TR-93-012, 1993.

10. Widmer G., Seyerlehner K., Pohle T., Schedl M. Automatic music detection in television productions // Proc. of the 10th Int. Conference on Digital Audio Eects, 2007. www.cp.jku.at/ research/papers/Seyerlehner_etal_DAFx_2007.pdf

11. Lokhanova A., Simonchik K., Kozlov A. Music detection alogorithm in problems of speech processing // Proc. of DSPA, 2010. Vol. 1.

P. 210–213.

12. Marzinzik M., Kollmeier B. Speech pause detection for noise spectrum estimation by tracking power envelope dynamics // IEEE Trans. on Speech Audio Process, 2002. Vol. 10(2). P. 109–118.

13. Ramirez J., Segura J. C., Benitez M. C. et al. A new adaptive long-term spectral estimation voice activity detector // Proc. of EUROSPEECH, 2003. P. 3041–3044.

14. Riemer T. E., Weiss M. S., and Losh M. W. Discrete clipping detection by use of a signal matched exponentially weighted dierentiator // Proc. of the IEEE Southeastcon, 1990. P. 245–248.

Kato K., Klyuev V.V.

University of Aizu, Aizu-Wakamatsu, Japan

–  –  –

Abstract. Google App Engine is a very useful tool provided by Google to make web applications easily. App Engine lets us run web applications on Google’s infrastructure and App Engine Framework supplies three languages to design high quality applications. We have been working with Google App Engine for one year. We discuss the pros and cons of dierent technologies utilizing Python. Thus recommendations for the novice users are provided.

1. Introduction. Book [1] presents key techniques of Google App Engine. The main idea of this tool is to remove cost barries from building and developing software and data-lacked web sites. Resource provieded to Google’s cloud of servers are much cheaper compared to resources the users need to purchase on his own.

Google App Engine is a tool to use Google’s cloud of severs. We can start to make a web application by using Google App Engine. The App Engine can provide the contents of web sites, however, the App Engine particularly is designed for Dynamic applications. We can use Task Queue to return a response more faster and make the application by Python, Java, or Go. But Google released Python earlier than Java, so the Python software development kit consists of the larges number of tools compared do the Java software development kit. The App Engine supports the secure connection and the App Engine’s application can use custom appspot.com domain at the same time. When the secure connection is used, it takes long time for decryption request and encryption response. We developed a chatting application as an example to demonstrate the major techniques of Google App Engine. Ours code may be helpful to support novice uesers of this tool.

2. Chatting application. The application uses the webapp framework. Webapp is one of frameworks provided by Google App Engine.

It is simple and we can use it to make web applications easily for beginners. On the other hand, webapp might not be suitable to extensive programing. In extensive programing, we should use Django. Django is also one of frameworks and Django has a lot of functions. Ours example application uses also a logging module. The logging module is one of libraries in Python. We need it to record messages in logs.

According to the scenario to use the chatting application, users should initially create accounts. After that they, we can chat with all members.

The chat records consists of a sentence, the user name, and date. The application’s template is like a search engine temlate, because it has a query. When you write a message in the query eld, the message will be recorded under the query as a key. The message’s structure includes message (user name), day of the week, date, month of the year. This information is necessary to imprement the search function. We can check who is the member in the application by the members link. If the person who we do not know as registered in the application, we can check that person. In the chat session, we care who are member and we do not want to chat with a stranger.

We can access Google App Engine’s Home Page or related sites from ours application because there are some links about Google App Engine or Python are in place. Thus, we can also study Google App Engine by using our application.

3. How to use the chatting application When a user uses this application, rst, he must make an account. Then he needs to input the name, user name, and password. After compliting this job, the user can log in the application and chat with log in members. If users access the application without log in, they can not use this application and will be asked to log in. When they make an account, they are requested to input the color. This template is to understand who did write this sentence quickly and it is boring that the color in chat is only one that is black.

Thus, the chosen color is very important to chat in the application. Users can check informationabout the others users that is the name, user name, password, and color.

4. Functions in the chatting application. We developed another functions on this application. They are the members function and sites function. As an illuusration, we provide the code for thesfunctions to demonstrate how easy to design this functionality.

4.1. Members function We can check information about the chat members. Members links are to do this. If a new member made his account, his Name, Account name, and Color are visible. The Password is surely hidden. Below, we put code displaying members list and example by processed results. Code is written in Python and HTML. The code show the work about color function and members function.

4.2. Example code by Python

def post(self):

self.session = Session() name = self.request.get(’name’) acct = self.request.get(’account’) pw = self.request.get(’password’) color = self.request.get(’color’) logging.info(’Adding account=’+acct) We are able to get the data that is written by the users for color and use the data on all most functions.

4.3. Example code by HTML tr tdfont color="{{ user.color }}"{{ user.name }}/font/td tdfont color="{{ user.color }}"{{ user.account }}/font/td tdfont color="{{ user.color }}"****/font/td tdfont color="{{ user.color }}"{{ user.color }}/font/td /tr We are be able to use the color that was sellected each datas.

Figure 1. Example Members function screen shot

4.4. Sites function There are the links to resources to lean Google App Engine. There are three links to Python, App Engine, and Google App Engine.

5. Conclusion Google App Engine is very good for beginners because the developers and users do not have to download the tools to make web application like web server, database by using, the Google App Engine’s software developer kits. If someone need to create a powerful web application quickly, you should utilize Google App Engine. Ours chatting application is a demonstration of the powers and simplisity of this tool.

References

1. Charles Severance, Using Google App Engine. United States of America: O’Reilly Media, 2009.

Zeng Yi-Ching Li12, Vitaly Klyuev1, and Shih-Hung Wu2 University of Aizu, Aizu-Wakamatsu, Japan1 Chaoyang University of Technology,Taiwan2 *: Contact author

Opinion Extraction from Chinese Web Blog Corpora

Abstract

In recent years, blogs have become a popular communication tool among internet communities. Blogs allow users to express their ideals, comments and share them with others. Many authors write opinions about things in their blogs. Opinion analysis in Chinese is a challenging task. In this paper, we discuss blog opinion analysis issues.

To nd opinion terms in blogs, we segment the sentences utilizing open source software. After that we utilize a sentiment dictionary. We use a support vector machine to dene the opinions in the blogs. It detects both the positive and negative opinions in the selected blogs. We use blog documents provided by PIXNET (Taiwanese Internet service provider company) to test our approach.

1. Introduction Nowadays blogs are very popular on the web publishing platform. Usually authors express their views about something in the blogs. How to extract and analyze these views? This question is the most interesting for the researchers. There are many scientic papers focusing on English opinion analysis.

In this paper, we are talking about opinion analysis of Chinese blogs.

We developed a opinion analysis system. We collected blog documents provided by PIXNET (Taiwanese Internet service provider company) to do experiments. The system extracts opinions form blogs and denes them as positive, negative or neutral. To segment sentences, the system uses the ICTCLAS (Institute of Computing Technology, Chinese Lexical Analysis System). The NTUS dictionary (National Taiwan university Sentiment Dictionary) is utilized to detect opinion terms in every blog.

We discuss the pros and cons of the approach implemented.

2. Related Work This section discusses previous works done in the opinion mining area. Web blogs are very good data source for opinion analysis.

Changhua [1] investigated the emotion classication of web blog corpora using a support vector machine (SVM) and conditional random eld (CRF) machine learning techniques.

Wei [2] presented an opinion retrieval algorithm that retrieves blog documents according to the opinions and comments given in queries. He adopted a support vector machine (SVM) classier that uses unigrams (single words) and bigrams (two neighbour words) as features.

Ruifeng [6] presented an opinion analysis system based on linguistic knowledge which is acquired from small-scale annotated texts and raw topic-relevant webpages. He used CFOW (Context-free Opinion Word) to do Supervised Learning and nd opinion words.

Magdalini [7] presented an algorithm which not only analyzes the overall sentiment of a document, but also identies the semantic orientation of specic components of the review that lead to a particular sentiment. It uses the HAC (High Adjective Count) algorithm to identify potential opinion features.

Daniel [8] reviewed literature aimed at gathering opinion, sentiment and information from blogs. In his paper,he noticed that use frequency of appearance of terms is widely used as a measure of interest in a topic in blogs.

Hung [9] developed a sentiment analysis system that is suitable for Chinese reviews. Hung did sentiment analysis of certain product reviews written by customers using PMI (pointwise Mutual Information) algorithm. Xiaoying [10] compared analysis between Machine-learning Methods and Language-modeling Methods.

Aforementioned approaches and techniques have the pros and cons Our approach is to use an opinion dictionary to access the knowledge and SVM to classify blog opinion. It should help to classify opinions more a accurate. Core components of our prototype include an subsystem, opinion word extraction opinion ere dictionary and opinion.

3. Approach to extract and analyse opinions The user view implemented in the approach is the same as in the TREC Blog task A user enters a query to express the topic of interest and expects to see a list of blog posts that express an opinion (positive or negative) about the topic.

We collected the world wide web blogs, then we used a stop-word remover and ICTCLAS [4] system. In the past research, N-gram approach was in common use for traditional Chinese. In our approach, the use of a segmentation system is the central point. We dene opinion words applying the NTUSD opinion dictionary. We translate blog terms into vectors then apply SVM to train the model. SVM is easier to use than Neural Networks, and it is a powerful technique for data classication.

Precision, recall and f-measures are applied to evaluate obtained results.

3.1. Opinion Extraction The process to extract the opinion terms from blogs is as follows. At the beginning, we use the ICTCLAS system to segment sentences from blogs, and each term receives a lexical mark on it. Then, we remove stop-words from the blogs. After that we use the NTUSD opinion dictionary to detect positive terms and negative ones. The next step is to dene blogs with positive and negative opinions.

3.2. Opinion word dictionary As we have already mentioned, we are searching for opinions and sentiments in blogs utilizing NTUSD (National Taiwan University Sentiment Dictionary). This dictionary contains positive and negative terms. We mark blogs where opinions are detected.

3.3. Opinion Classication Evaluation of the performance of the system is a labor-intensive and expensive process. The organizers of TREC [11] and NTCIR [12] conferences involve experts for evaluation.

Our evaluation method is a human inspection of retrieved results by the prototype in response to the test set of queries. The number of the assessors is one. The number of queries is 100. We understand that this evaluation is subjective.

We use the libsvm-3.11 SVM tool to train blogs classiers. We dene the SVM format based on description. We need to use terms to create a feature vector. For example, consider the segmented sensoup) (middle) tence with removed stop-words (today) ©(have)  (one) (bread) (delicious) ­ (acidity) (a little) (taste). We need to create a feature vector. There are 10 terms when pre-processing nished.

The blog opinion is positive when its weight is above zero. For blogs without opinions, the weight is 0. For blogs with negative opinions, the weight is a negative value. The aforementioned sentence is a positive so we dene 1. In our example, terms from 0 to 5 and then 7 to 9 have no opinion. The future vector value for each term is i:0. Term 7 has positive opinion, its value is 6:1.

4. Experiments The blogs from PIXNET blogs, a Taiwanese internet service provider (http://www.pixnet.net/) are records in the test dataset. The total number of blogs is 4736. We classify this set into four types.

1. Travel:The authors introduce the places and opinions on them.

2. The author feelings such as happy, sad, etc.

3. Author views on some products, movies etc.

4. Photos with comments.

For training SVM, we used 3504 blogs, and 1232 blogs for experiments (see Table 1). When the training process nished, we used Precision, Recall and F-measures to evaluate the model (see Table 2). We have got the precision at the level of 44% to 46%.

Precision for negative blogs is higher than for positive ones. The content of the opinion dictionary (NTUSD) is the reason for this outcome:

The number of negative opinion terms are large than positive ours, 8276 vs. 2812. Recall for positive blogs is higher than for negative blogs. The reason for this trend is in the training set: The number of positive blogs is large than negative ones. For the no opinion blogs, the precision and recall both higher than for positive and negative: The corresponding terms do not appear in the opinion dictionary (NTUSD). Some of the sentences may have opinion but the segmentation system segments them in the wrong way.

Experimental dataset Table 1.

Positive Negative No opinion Total Training 1624 1420 460 3504 Test 464 508 260 1232 Total 2088 1928 720 4736

–  –  –

­ We use (Greasy) and (not good) as queries to evaluate the

results. First use (Greasy) query. The result blog is this blog (URL:

http://163.17.10.71//pixnet//html//5-7964D.html). In this blog, the author writes comments on the food at this place. The sentence means ”It is very tasty, if you remove his greasy, I believe even more delicious” (This is a translation from chinese). This sentence is a negative sentence. Second use (not good) query. The result blog is (URL:http://163.17.10.71//pixnet//html//0-2520D.html). In this blog, the author writes: Try it is a really fun (This is a translation from chinese). Because the sentence segmentation is done in the wrong way so we made a mistake with opinion. We need to gure out one of segmentation problem.

5. Conclusion In this paper, we chatacterized the technique to dene the positive and negative opinions in blogs. The NTUSD opinion dictionary can really help us to mine opinions. We can use this prototipe to provide the user with suggestions.

Some sentences in our experiments were segmented in the wrong way, we think that applying the combination the N-gram technique and segmentation, we can nd the larger number of opinion words. It may help preserve semantics as a feature helping towards improving the quality of detection of opinions.

References

1. Changhua Yang Kevin, Hsin-Yih Lin, Hsin-Hsi Chen, Emotion Classication Using Web Blog Corpora, eInternational Conference on Web Intelligenc, 2007.

2. Wei Zhang, Clement Yu, Weiyi Meng, Opinion Retrieval from Blogs, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, ACM New York, NY, 2007

3. NTUSD (National Taiwan University Semantic Dictionary) http://nlg18.csie.ntu.edu.tw:8080/opinion/pub1.html

4. ICTCLAS(Institute of Computing Technology, Chinese Lexical Analysis System), http://ictclas.org/

5. Weifu Du, Songbo Tan, Optimizing modularity to identify semantic orientation of Chinese words, Expert Systems with Applications: An International Journal archive Volume 37 Issue 7, 2010

6. Ruifeng Xu, Kam-Fai Wong, Qin Lu1, Yunqing Xia, Wenjie Li1, Learning Knowledge from Relevant Webpage for Opinion Analysis, Web Intelligence and Intelligent Agent Technology, 2008.

7. Magdalini Eirinaki, Shamita Pisal, Japinder Singh, Feature-based opinion mining and ranking, Journal of Computer and System Sciences, 2011.

8. Daniel E. O’Leary, Blog mining-review and extensions: From each according to his opinion, Decision Support Systems, 2011.

9. Hung-Yu Kao, Zi-Yu Lin, A Categorized Sentiment Analysis of Chinese Reviews by Mining Dependency in Product Features and Opinions from Blogs, Web Intelligence and Intelligent Agent Technology, 2010.

10. Xiaoying Xu, Ya Li, Liping Hu, Jianhua Tao, Categorizing Terms’Subjectivity and Polarity Manually for Opinion Mining in Chinese, Aective Computing and Intelligent Interaction and Workshops, 2009

11. TREC, http://trec.nist.gov/tracks.html

12. NTCIR http://research.nii.ac.jp/ntcir/index-en.html

5. Управление социальноэкономическими системами € Басков О. В.

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

–  –  –

Рекомендовано к публикации профессором Ногиным В. Д.

1. Введение. Со второй половины XX века начала интенсивно развиваться теория нечётких множеств. Многие практические задачи оказалось удобно формулировать и исследовать с помощью аппарата нечёткой логики. Известные теоремы стали обобщать на нечёткий случай. Данная работа посвящена обобщению понятия двойственности конусов.

2. Нечёткие конусы. Напомним сначала некоторые определения из теории нечётких множеств.

Определение 1 [1]. Под нечётким множеством A будем понимать множество объектов из некоторого универсального множества X с ассоциированной функцией принадлежности A (x) : X [0, 1].

Число A (x) можно интерпретировать как степень уверенности в том, что x A.

Так как в данной работе речь пойдёт о конусах в пространстве Rm, положим X = Rm.

Определение 2 [1]. Нечёткое множество A является выпуклым, если

–  –  –

Множество, совпадающее со своим замыканием, называется замкнутым.

Определение 4 [3]. Нечёткое множество A называется нечётким конусом, если его функция принадлежности удовлетворяет условию

–  –  –

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

Когда множество A состоит из конечного числа векторов, его выпуклую коническую оболочку называют конечнопорождённым нечётким конусом. Структуру такого конуса раскрывает следующее эквивалентное определение.

Определение 7. Пусть множество A состоит из конечного числа векторов a1,..., ak с соответствующими степенями принадлежности 1 2... k. Выпуклая коническая оболочка множества A нечёткое множество cone A с функцией принадлежности

cone A (x) = max 0; i x cone a1,..., ai, i = 1, k,

где cone a1,..., ai чёткая выпуклая коническая оболочка набора векторов.

Таким образом, выпуклая коническая оболочка конечного числа векторов в нечётком случае представляет собой наслоение конусов с различными степенями принадлежности (см. рис. 1).

Рис. 1. Конечнопорождённый нечёткий конус

–  –  –

При этом полагается Dual C (0) = 1.

Непосредственно проверяется, что, как и в чётком случае, справедливо следующее Утверждение 1. Нечёткий двойственный конус всегда является выпуклым замкнутым конусом.

Также нетрудно обобщаются следующие факты.

Утверждение 2. Пусть заданы два нечётких множества A и B такие, что A B. Тогда Dual A Dual B.

Напомним, что включение нечётких множеств A B определяется соотношением x Rm A (x) B (x).

Утверждение 3. Для всякого нечёткого множества C справедливо Dual C = Dual cone C = Dual cl cone C.

Утверждение 4.

Нечёткий конус, двойственный к двойственному к некоторому заданному нечёткому множеству C, совпадает с наименьшим по включению замкнутым нечётким конусом, содержащим множество C:

Dual Dual C = cl cone C.

–  –  –

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

Dual C:

0, x2 0, 1 x2 Dual Dual C (x) = 1 (2) + arctg, x2 0.

2 |x1 | На рис. 2 иллюстрируется зависимость степени принадлежности вектора соответствующему множеству от угла его наклона.

Заметим, что множество x R2 C (x) состоит из всех векторов с x2 0 и поэтому является незамкнутым. Если изменить функцию C в точках границы этого множества на, получится функция принадлежности замыкания cl C, совпадающая с (2), что иллюстрирует утверждение 4.

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

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

Литература

1. Zadeh L. A. Fuzzy sets // Information Control, 1965. Vol. 8.

P. 338–353.

2. Biacino L. An Extension Principle for Closure Operators // Journal of Mathematical Analysis and Applications, 1996. Vol. 198. P. 1–24.

3. Ammar E. E. Some properties of convex fuzzy sets and convex fuzzy cones // Fuzzy Sets and Systems, 1999. Vol. 106. P. 381–386.

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

С. 427–431.

Богданова О. К., Парилина Е. М.

Санкт-Петербургский государственный университет Марковский процесс распространения продукта в социальной сети

–  –  –

= (1 p)3, 3p(1 p)2, 3p2 (1 p), p3.

Таким образом, на первом шаге математическое ожидание числа активных агентов будет иметь вид

–  –  –

где будем считать 1 = 0.

2.1. Численный пример. Для наглядности рассмотрим данную модель при следующих числовых значениях: r0 = 2, R = 10, c0 = 10, = 0, 9 [5]. С помощью пакета Maple были рассмотрены различные варианты динамики распространения продукта и получены следующие результаты. Максимальную прибыль фирма получит при условии, что на первом шаге назначит максимальную цену при минимальных издержках на рекламу, т. е.

–  –  –

При этом двое из трёх агентов сети перейдут в активное состояние с вероятностью 3p2 (1 p)2 (2 p)2. И для того чтобы оставшийся агент сети приобрёл продукт, фирме необходимо выбрать стратегию

–  –  –

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

3. Заключение. Была рассмотрена социальная сеть, состоящая из конечного числа агентов, которые могут быть активными или восприимчивыми. Смоделирована динамика распространения нового продукта в этой сети с помощью дискретных цепей Маркова. Рассмотрен случай распространения продукта в социальной сети, состоящей из трёх агентов. Рассмотрен численный пример и для него найдена стратегия, максимизирующая общую прибыль фирмы.

Литература

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

С. 432–435.

2. Губанов Д. А., Новиков Д. А., Чхартишвили А. Г. Модели влияния в социальных сетях // Управление большими системами,

2009. Вып. 27. С. 205–281.

3. Майн Х., Осаки С. Марковские процессы принятия решений.

М.: Наука, 1977. 176 c.

4. Bogdanova O., Parilina E. Diusion of new product in social networks // Game Theory and Management. Collected abstracts of papers presented on the fth international conference game theory and management / Ed. by Leon A. Petrosyan and Nikolay A. Zenkevich. SPb: Graduate School of Management SPbU, 2011.

P. 29–31.

5. Богданова О. К., Парилина Е. М. Моделирование динамики распространения продукта в социальной сети // Теория активных систем: Труды международной научно-практической конференции / Под ред. В. Н. Буркова, Д. А. Новикова. М.: ИПУ РАН,

2011. Т. 2. С. 241–244.

Болотина О. В.

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

Введение. Работа посвящена задаче принятия решений в условиях риска. Основными понятиями являются риск, мера риска и когерентная мера риска. Рассматриваются наиболее используемые вероятностные меры: некогерентная мера риска VAR и когерентная Shortfall. Из теории нечетких множеств здесь приведена мера V &M и показаны ее преимущества.

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

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

Количество риска есть функционал на пространстве рисков. Примерами мер риска могут служить ожидаемая полезность, значения VAR, Shortfall и др. В классических задачах теории риска в качестве меры риска использовались также дисперсия и стандартное отклонение. Частным случаем меры риска является цена риска. Каждая мера риска задает свое понятие детерминированного эквивалента, где детерминированный эквивалент случайной величины X (в теории полезности) это значение характеризующее полезность величины X.

При заданной функции ожидаемой полезности U детерминированный эквивалент вычисляется по формуле:

d(X) = U 1 EU (X),

где U 1 функция, обратная к U, E математическое ожидание.

1.2. Когерентные меры риска. Введем вероятностное пространство (, A, P ). Риском (случайной величиной) X будем называть произвольное отображение из пространства элементарных событий на множество вещественных чисел R. Пусть совокупность всех случайных величин на измеримом пространстве (, A).

Перенумеровав некоторым произвольным образом элементы пространства = {1,..., n }, обозначим X(i ) = xi, i = 1,..., n и будем отождествлять случайные величины X с векторами X = (x1,..., xn ) из Rn. Обозначим C+ конус неотрицательных случайных величин, а C конус отрицательных случайных величин, т. е.

C+ = {X : X 0}, C = {X : X 0}.

Множество A будем называть множеством приемлемых рисков, если оно является выпуклым замкнутым конусом в линейном пространстве и A C =, C+ A.

Мерой риска согласно обозначениям называется произвольный функционал f : R.

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

•X Y f (X) f (Y );

• f (X + Y ) f (X) + f (Y );

• f (X) = f (X), 0;

• f (X + aI) = f (X) + a, a R.

Здесь X, Y произвольные случайные величины из, а I единичный вектор.

Как отмечается в [1], мера риска f называется детерминированным эквивалентом, если f (aI) = a, a R. Из свойства положительной однородности вытекает равенство f (0) = 0, которое вместе со свойством инвариантности к сдвигам дает f (aI) = a, a R. Таким образом, когерентные меры риска сами по себе являются детерминированным эквивалентами.

Когерентную меру риска можно определить, используя понятие множества приемлемых рисков. Когерентная мера риска f = fA определяется как f (X) = sup{b R : X bI A}.

1.3. Меры VAR и Shortfall. Одной из наиболее популярных мер риска является VAR. Ее можно определить следующим образом.

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

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

По формуле VARp = Pp p Z, предложенной в [2], рассчитывается VAR портфеля для заданного уровня доверительной вероятности.

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

Shortfall лишен многих недостатков, свойственных VAR. Обозначим, как и при определении VAR, за X потери нашего портфеля через N дней. Тогда

Shortfall (X) = E(X|X q).

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

1.4. Соотношение мер VAR и Shortfall. Рассмотрим пример, иллюстрирующий соотношение VAR и Shortfall. Необходимо определить однодневный VAR и Shortfall с доверительной вероятностью 95% для портфеля стоимостью 10 млн. руб., в который входят акции одной компании. Стандартное отклонение доходности акции в расчете на год равно 25%. Сначала рассчитаем стандартное отклонение доходности акции для одного дня, полагая, что в году 250 рабочих дней = 0,25/ 250 = 0,0158. Далее находим, что уровню доверительной вероятности в 95% соответствует 1,645 стандартных отклонений. Имеем VARp = 259, 91 тыс. руб.



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

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

«ГОСУДАРСТВЕННЫЙ СТАНДАРТ СОЮЗА ССР ПЛ АСТМ АССЫ МЕТОД ОПРЕДЕЛЕНИЯ СОДЕРЖАНИЯ НЕЛЕТУЧИХ И ЛЕТУЧИХ ВЕЩЕСТВ В ЭПОКСИДНЫХ С М О Л А Х И КОМПОЗИЦИЯХ ГОСТ 22456-77 Издание официальное ГОСУДАРСТВЕННЫЙ КОМИТЕТ СТАНД...»

«МАГНИТНЫЕ МОДЕЛИ ЛИТОГО АМОРФНОГО МИКРОПРОВОДА С.А. Баранов*,**,*** * Институт прикладной физики АНМ, ул. Академией, 5, г. Кишинев, MD–2028, Республика Молдова, ** Приднестровский госуниверситет...»

«ПРАВИТЕЛЬСТВО РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ "САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРС...»

«НИЖНЕКАМСКНЕФТЕХИМ Декабрь 2010 Дмитрий Марков markov@lmsic.ru Нижнекамскнефтехим – ведущее предприятие нефтехимии в России и один из крупнейших производителей неТикер NKNC фтехимической продукции в мире. НКНХ входит в группу ТАИФ, консолидирующую более 80 дочерних и з...»

«Управління мережами і послугами телекомунікацій 3 УДК 621.391 Поповский В.В., д.т.н., проф.; Лемешко А.В., д.т.н., доц.; Евсеева О.Ю., к.т.н., докт-т ДИНАМИЧЕСКОЕ УПРАВЛЕНИЕ РЕСУРСАМИ ТКС: МАТЕМАТИЧЕСКИЕ МОДЕЛИ В ПРОСТ...»

«ВЕРХНЕМЕЛОВЫЕ РАДИОЛЯРИИ УРАЛА ЕКАТЕРИНБУРГ РОССИЙСКАЯ АКАДЕМИЯ НАУК УРАЛЬСКОЕ ОТДЕЛЕНИЕ Институт геологии и геохимии имени акад. А.Н. Заварицкого УРАЛЬСКАЯ РЕГИОНАЛЬНАЯ МЕЖВЕДОМСТВЕННАЯ СТРАТИГРАФИЧЕСКАЯ КОМИССИЯ Э.О. Амон ВЕРХНЕМЕЛОВЫЕ РАДИОЛЯРИИ УРАЛА МАТЕРИАЛЫ ПО СТРАТИГРАФИИ И ПАЛЕОН...»

«ОЦЕНКА УСТОЙЧИВОСТИ ОПОЛЗНЕВЫХ СКЛОНОВ ПО ТРАССЕ ПРОЕКТИРУЕМОГО ГАЗОПРОВОДА "ЮЖНЫЙ ПОТОК" ПО ДАННЫМ ТОМОГРАФИЧЕСКИХ ТЕХНОЛОГИЙ ИНЖЕНЕРНОЙ ГЕОФИЗИКИ ГЛАЗУНОВ В.В. Профессор кафедры геофизических и геохимических методов поисков и разведки месторождений полезных ископаемых (ГФХМР) Национального минерально-сырьевого университета "Горный",...»

«И_Н С Т И Т У Т ФИЗИКИ ВЫСОКИ X Э Н Е Р Г ИЙ ИФВ 3 СВМ 73-65 В.Д. Жильченков, В.Д. Матвеев КОММУТАТОРЫ ЭВМ И ПЕРИФЕРИЙНЫХ УСТРОЙСТВ КОЛЛЕКТИВНОГО ПОЛЬЗОВАНИЯ ДЛЯ СИСТЕМ ОБРАБОТКИ ФИЗИЧЕСКОЙ ИНФОРМАЦИИ ИФВЗ Серпухов 1973...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное образовательное учреждение высшего профессионального образования "ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ" Геолого-географический факультет В. Н. Труфанов, М. И. Гамов, Л....»

«Геометрические методы в математической физике Катанаев Михаил Орионович1 Математический институт имени В. А. Стеклова Российской Академии Наук 4 мая 2010 г. 1 Любые замечания, указания на ошибки, неточности и опечатки прошу отправлять на e-mail: katanaev@mi.ras.ru Оглавлени...»

«Естественные науки. № 4 (45). 2013 г. Физика и математическое моделирование 4. Elkin M. D., Grechuhina O. N., Dzhalmuhambetova E. A., Gaisina A. R., Kartashov V. M., Ravcheeva N. A. Strukturno-dinamicheskye modeli i spektralnaya identifikaciya digidroksiuracilov i di...»

«КИМ Александра Валерьевна ИССЛЕДОВАНИЕ ГИДРОФОБНОГО ВЗАИМОДЕЙСТВИЯ АМФИФИЛЬНЫХ МОЛЕКУЛ МЕТОДОМ МОЛЕКУЛЯРНОЙ ДИНАМИКИ 01.04.17 – химическая физика, горение и взрыв, физика экстремальных состояний вещества ДИССЕРТАЦИЯ на соискание учёной степени кандидата физико-математических наук Научный руководитель: доктор...»

«Международные соревнования "Интернет-карусели" Международные соревнования "Интернет-карусели" Карусель-кружок. Математика 5-6 Карусель-кружок. Математика 5-6 2016-2017 учебный год 2016-2017 учебный год Блок 6. Площади и периметры Блок 6. Пло...»

«Государственное образовательное учреждение высшего профессионального образования Московской области "Международный университет природы, общества и человека "Дубна" (университет "Дубна") Кафедра высшей математики УТВЕРЖДАЮ Проректор по учебной работе _С. В. Моржухина “_” _2013 г. ПРОГРАМ...»

«Список победителей XV Российского соревнования юных исследователей "Шаг в будущее, ЮНИОР" (Челябинск, 9-12 апреля 2017 г.) Грамоты за мини-олимпиаду по физике: (Конф.3 08) КОКОВ Всеволод Вячеславович Челябинская область, г. Челябинск МАОУ "...»

«П Р О Т О Н Н Ы Й С И Н Х Р О Т Р О Н ИФВЭ НА Э Н Е Р Г И Ю 70 ГЭВ. С О С Т О Я Н И Е РАБОТ ПО Н А Л А Д К Е, П Е Р В Ы Е Э К С П Е Р И М Е Н Т Ы А. А, НАУМОВ И н с т и т у т ф и з и к и высоких энергий, Серпухов, СССР Введение Протонный синхротрон на 70 Гэв 1,3 Института физики высоких энергий Государственного Комитета по использова...»

«ПОЛУЧЕНИЕ И ХАРАКТЕРИСТИКА ГУМИНОВЫХ ПРЕПАРАТОВ ДЕТОКСИЦИРУЮЩЕГО НАЗНАЧЕНИЯ Ли Сергей Павлович канд. хим. наук, доцент Кыргызский национальный университет имени Ж. Баласагына, 720033, Республика Кыргызстан, г. Бишкек, ул. Фрунзе 547...»

«МАТЕМАТИКА УДК 514.75 ББК 22.151 СТРОЕНИЕ ПОДМНОГООБРАЗИЙ С ЦИКЛИЧЕСКИ РЕКУРРЕНТНОЙ ВТОРОЙ ФУНДАМЕНТАЛЬНОЙ ФОРМОЙ В ЕВКЛИДОВОМ ПРОСТРАНСТВЕ И.И. Бодренко В работе изучается строение n-мерных подмногообразий c цикличес...»

«МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ВЛИЯНИЯ ПРОМЕРЗАНИЯ ГРУНТА В ЗОНЕ РАЗМЕЩЕНИЯ РЕЗЕРВУАРОВ ДЛЯ ХРАНЕНИЯ ТОПЛИВ ТЭС И КОТЕЛЬНЫХ Ж.Ф. Ожикенова, Ф.Т. Махсутбек Ozhikenova92@mail.ru Научный руководитель: Половников В.Ю., к.т.н....»

«УДК 51.001.57 МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ПРОЦЕССА АДСОРБЦИИ УГЛЕКИСЛОГО ГАЗА В.Г. Матвейкин1,2, С.Б. Путин1,2, С.А. Скворцов1, С.С. Толстошеин1 Кафедра "Информационные процессы и управление", ГОУ ВПО "ТГТУ" (1); sergik_ctc@rambler.ru; ОАО "Корпорация...»

«АКАДЕМИЯ НАУК СССР УРАЛЬСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ ХИМИИ НАУЧНЫЙ СОВЕТ ПО НЕОРГАНИЧЕСКОЙ ХИМИИ СЕКЦИЯ ХИМИИ ТВЕРДОГО ТЕЛА ХИМИЯ ТВЕРДОГО ТЕЛА Тезисы докладов школы молодых ученых 30 января — 5 февраля 1989 г. г. Свердловск СВЕРДЛОВСК 1989 АКАДМН Ш К ССОР УРАЛЮЮЕ ОТДВШВИЕ ИНСТИТУТ ЯНКИ НШШЙ СОВЕТ ГО ННОРГШЧВСКОЙ ЛИНИ С В Ш ХИМИИ ТЖРДОГО ТЕМ хи...»

«ИЗВЕСТИЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ T. 56, № 3 ФИЗИКА 2013 ФИЗИКА КОНДЕНСИРОВАННОГО СОСТОЯНИЯ УДК 539.219.3: 004.94: 620.22-419 А.Г. ЛИПНИЦКИЙ, И.В. НЕЛАСОВ, Е.В. ГОЛОСОВ, Ю.Р. КОЛОБОВ, Д.Н. МАРАДУДИН МОЛЕКУЛЯРНО-ДИНАМИЧЕ...»

«Научный журнал КубГАУ, №119(05), 2016 года 1 УДК 51-77 UDC 51-77 01.00.00 Физико-математические науки Physics and Math РАЗРАБОТКА СИСТЕМЫ ОЦЕНКИ КРЕTHE DEVELOPMENT OF COUNTRIES' CREDДИТНОГО РЕЙТИНГА СТРАН IT RATING ASSESSMENT SYSTEM Бабанская Виктория Викторовна Babanskaya Victoria Victorovna студентка student Р...»

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








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

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