На правах рекламы:
ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Авторитетность издания

ВАК - К1
RSCI, ядро РИНЦ

Добавить в закладки

Следующий номер на сайте

2
Ожидается:
17 Июня 2024

Статьи из выпуска № 2 за 2017 год.

Упорядочить результаты по:
Дате публикации | Заголовку статьи | Авторам

1. Effective algorithm for constructing associative rules [№2 за 2017 год]
Author: Billig V.A.
Просмотров: 10274
Конструирование ассоциативных правил является одним из наиболее важных алгоритмов извлечения знаний из БД. Все современные алгоритмы так или иначе связаны с алгоритмом Apriori, предложенным в работах Р. Агравала и его соавторов, опубликованных более чем 20 лет назад и ставших сегодня классикой. Известные эффективные реализации алгоритма связаны со сжатием БД и представлением структуры данных в виде дерева, что позволяет эффективно вычислять поддержку ассоциативных правил и другие их характеристики. Предлагаемый алгоритм ConApriori не использует вышеназванную идею. Транзакции БД рассматриваются как перечисление, заданное шкалой. Это позволяет практически мгновенно вычислять базисную для алгоритма операцию, определяющую, является ли некоторое множество подмножеством другого множества. Вычисления сводятся к нескольким логическим командам компьютера. Перечисление позволяет также рассматривать транзакцию во внутреннем представлении как одно или несколько чисел, сохраняя в то же время смысл элементов транзакции в их внешнем представлении. Другая идея, используемая в алгоритме, позволяет конструировать большинство достоверных правил на основе ранее построенных достоверных правил. В статье дается обоснование корректности алгоритма и приводится оценка его сложности. Анализируется эф-фективность алгоритма в сравнении с другими известными реализациями. Рассматривается также возможность распараллеливания алгоритма.

2. Параллельные вычисления при реализации web-инструментария распознавания образов на основе методов прецедентов [№2 за 2017 год]
Авторы: Фомин В.В., Александров И.В.
Просмотров: 10513
Предлагается программное решение, направленное на улучшение качества распознавания образов и повышение эффективности инструментария машинного обучения посредством реализации grid-технологий. Формулируются стратегические направления разработки инструментария распознавания образов в виде программной системы, основанной на принципах распределенных систем, распараллеливания и адаптивной настройки вычислительных ресурсов. Рассматривается структура организации web-инструментария распознавания образов с использованием концепции библиотеки алгоритмов. Даются алгоритмические решения распараллеливания алгоритмов обучения и распознавания на базе классических методов интеллектуального анализа данных, которые хорошо зарекомендовали себя на практике. К таким алгоритмам относятся методы прецедентов или методы, основанные на метриках близости. Они обладают большим потенциалом к распараллеливанию вычислительных процессов и разработке параллельных алгоритмов их реализации. Поиски путей повышения производительности вычислительной техники, особенно при реализации web-инструментария на основе ресурсоемких вычислительных алгоритмов машинного распознавания и прогнозирования, привели к решению создать grid-систему. Рассматриваемые в статье архитектура и реализация grid-системы предполагают распараллеливание и организацию распределенных вычислений на многомашинной основе с применением интернет-технологий, что позволяет получить практически те же вычислительные мощности, что и на многопроцессорных компьютерных системах, но с гораздо меньшей стоимостью. В статье решается задача повышения эффективности вычислительных ресурсов при возможности реконфигурирования структуры интернет-соединений, в том числе процедуры настройки структуры вычислительной сети, подключаемых каналов связи и выделенных серверов в зависимости от исходных алгоритмов и данных. Представлены зависимости параметров времени выполнения операций от дисциплины обслуживания, адаптирующей систему к запросам пользователей. При этом задачи ранжируются по ресурсоемкости и под них выделяются соответствующие их рангу вычислительные мощности.

3. Принцип минимизации эмпирического риска на основе агрегирующих функций средних потерь для решения задач регрессии [№2 за 2017 год]
Авторы: Шибзухов З.М., Димитриченко Д.П., Казаков М.А.
Просмотров: 6780
В настоящей работе предлагается расширенный вариант принципа минимизации эмпирического риска для решения задачи регрессии. Он строится на основе применения усредняющих агрегирующих функций для вычисления эмпирического риска вместо среднего арифметического. Это оправданно, если распределение потерь имеет выбросы или существенно искажено, отчего оценка риска как средних потерь с самого начала является смещенной. Поэтому в таких случаях при оптимизации параметров в задаче регрессии изначально следует использовать робастную оценку среднего риска. Подобные оценки среднего риска можно построить, используя усредняющие агрегирующие функции, которые являются решением задачи минимизации штрафной функции за отклонение от своего среднего значения. Такой подход для представления агрегирующих функций среднего позволяет, с одной стороны, определить значительно более широкий класс функций среднего, а с другой, определить дифференцируемые функции среднего, которые аппроксимируют недифференцируемые функции среднего, такие как медиана или квантиль. В результате появляется возможность построить градиентные методы решения задачи регрессии, в определенном смысле аппроксимирующие робастные методы, такие как Least Median и Least Quantile. В настоящей работе предлагается новая градиентная схема для решения задачи минимизации среднего риска. Она является аналогом схемы, применяемой в алгоритме SAG в случае, когда риск вычисляется при помощи среднего арифметического. Приведен иллюстративный пример построения робастной процедуры оценки параметров в задаче линейной регрессии на базе использования усредняющей функции среднего, аппроксимирующей медиану.

4. Рекурсивный алгоритм точного расчета ранговых критериев проверки статистических гипотез [№2 за 2017 год]
Авторы: Агамиров Л.В., Вестяк В.А., Агамиров В.Л.
Просмотров: 10143
В статье рассматривается методика генерации точных распределений ранговых непараметрических критериев средствами компьютерной комбинаторики. Актуальность работы обусловлена затруднениями в определении точных распределений критических значений ранговых критериев проверки статистических гипотез из-за того, что точные таблицы, рекуррентные формулы для многих критериев не существуют, а аппроксимации часто дают неудовлетворительный результат при ограниченных объемах наблюдений. Задача расчета распределения ранговых критериев заключается в переборе всех возможных вариантов перестановок выборок и в расчете ранговых статистик, а также накопленных частот их появления. Для ее решения разработана программа генерации перестановок элементов выборок ранговых непараметрических критериев, основанная на рекурсивном алгоритме прямого перебора вариантов перестановок вектора порядковых статистик со следующим ограничением числа вариантов: во всех вариантах перестановок элементы одной и той же выборки не могут меняться местами, что является универсальным условием для всех точных распределений ранговых критериев. В работе приводится ссылка на интернет-ресурс, содержащий программный комплекс реализации алгоритма расчета ранговых критериев. В данном комплексе рассмотрены четыре непараметрических критерия: двухвыборочный критерий Уилкоксона, критерий Лемана–Розенблатта, критерий серий и критерий Краскела–Уоллиса, точные распределения статистик которых представляют наибольший интерес для технических задач. Рассматриваемый алгоритм может быть использован и для других ранговых критериев проверки статистических гипотез. В работе представлена разработанная авторами реализация метода генерации точных распределений ранговых непараметрических критериев средствами компьютерной комбинаторики, основанная на рекурсивном прямом переборе вариантов перестановок вектора порядковых статистик с последующей фильтрацией результатов. Таким образом, решена задача определения критических значений ранговых непараметрических критериев для проверки статистических гипотез.

5. Автоматизированная система обработки данных в unix-подобных системах [№2 за 2017 год]
Авторы: Пальчевский Е.В., Халиков А.Р.
Просмотров: 9447
Данная статья посвящена распределенно-модульной обработке информации в автоматизированном режиме. Эта разработка позволяет принимать входящие и исходящие данные на физический сервер в объеме до 2,2 GB/s, при этом распределяя потоковую информацию (весь входящий сетевой трафик на сервер) по физическим и логическим ядрам. Показана нагрузочная зависимость физических ресурсов от входящей информации. Обоснована целесообразность применения разработанного аппаратно-программного комплекса SDP (Speed data processing), а также представлены структура и принципиальная схема работы. На первом этапе создания комплекса осуществляется разработка алгоритма, на втором – его техническая реализация. Приведен фрагмент исходного кода, отвечающего за уведомления на e-mail как о нагрузке на центральный процессор, так и об основных запускаемых процессах. Описан основной функционал со следующими данными: название функции, цель функции, теоретическая нагрузка, лимит передачи данных (в MB/s) и результат выполнения. На третьем этапе проводится тестирование комплекса SDP, представлены среднесуточные результаты за десять дней. Созданный аппаратно-программный комплекс позволяет эффективно обрабатывать входящую и исходящую информацию в автоматическом режиме для увеличения пропускной способности при приеме и отправке данных в СУБД MySQL, в том числе при DoS- и DDoS-атаках. Одной из частей комплекса является web-модуль для управления как с персонального компьютера, так и с мобильного телефона. В мониторинговой части web-модуля реализована возможность уведомления SMS-сообщениями о состоянии загруженности физического сервера. Разработанный аппаратно-программный комплекс показал высокую стабильность при обработке больших объемов данных с минимальной нагрузкой на ЭВМ.

6. Однородная распределительная задача на основе моделей адаптивного поведения муравьиной колонии [№2 за 2017 год]
Авторы: Лебедев Б.К., Лебедев О.Б., Лебедева Е.М.
Просмотров: 9019
В данной работе предлагается решение однородной распределительной задачи. Приводится постановка этой задачи, рассматриваются основные группы алгоритмов ее решения – приближенные и точные, а также их достоинства и недостатки. Описана предлагаемая новая парадигма кoмбинатopной oптимизации, базирующаяся на моделировании адаптивного поведения муравьиной колонии. Решением однородной распределительной задачи является ее графическое представление в виде двудольного графа. Для решения данных задач были предложены новые механизмы. Основу метаэвристики алгоритма на основе муравьиной колонии составляет комбинация двух техник. Базовая техника состоит в поиске наилучшего решения с использованием механизмов адаптивного поведения муравьиной колонии. Муравей строит какое-то конкретное решение, при этом используется встроенная процедура, в основе которой лежит конструктивный алгоритм. Построенный на графе поиска решений двудольный граф – основное отличие предлагаемого муравьиного алгоритма от существующей канонической парадигмы. При нахождении оптимальных решений оптимизационных задач, которые допускают представление решений в виде двудольных графов, данный подход будет достаточно эффективным. Проведенные исследования показали, что муравьиный алгоритм позволяет получать более качественные решения, чем известные алгоритмы. Сравнив результаты, можно сказать, что они улучшились на 3–4 %.

7. Сжатое представление строгих ассоциативных правил в анализе данных [№2 за 2017 год]
Авторы: Быкова В.В., Катаева А.В.
Просмотров: 9320
Современные методы и средства поиска ассоциативных правил в больших массивах данных приводят к значи- тельному множеству правил, многие из которых являются избыточными. Избыточные ассоциативные правила не представляют ценности, но могут вводить в заблуждение. Для решения этой проблемы предложен алгоритм MClose, являющийся модификацией алгоритма Close. Известно, что с помощью алгоритма Close можно построить минимаксный базис для строгих ассоциативных правил (правил с достоверностью 1). Минимаксный базис интересен для экспертов тем, что каждое входящее в него правило имеет минимальную посылку и максимальное следствие. Однако минимаксный базис может содержать избыточные ассоциативные правила. Алгоритм MClose позволяет в процессе построения минимаксного базиса устранять избыточные правила. Результирующий базис назван сжатым строгим базисом. Удаленные ассоциативные правила всегда можно получить из сжатого строгого базиса с сохранением их поддержки и достоверности без обращений к анализируемому массиву данных. Алгоритм MClose основан на соответствиях Галуа и выводимостях, подобных аксиомам Амстронга, которые используются в теории реляционных БД для функциональных зависимостей. Как показали вычислительные эксперименты, алгоритм MClose по времени работы сопоставим с алгоритмом Close. Однако он примерно в два раза уменьшает число ассоциативных правил минимаксного базиса. В работе дано описание программы, в которой представлены алгоритмы MClose и Close.

8. Формирование вариантов развиФормирование вариантов развития энергетики Вьетнама методами комбинаторного моделирования [№2 за 2017 год]
Авторы: Еделев А.В., Зоркальцев В.И., Доан Ван Бинь, Нгуен Хоай Нам
Просмотров: 8041
В статье рассмотрен подход комбинаторного моделирования к исследованию вариантов развития энергетики страны. Основу подхода составляет представление развития моделируемой системы в форме направленного графа, узлы которого соответствуют возможным состояниям системы в отдельные моменты времени, а связи характеризуют допустимость переходов из одного состояния в другое. Методы комбинаторного моделирования, являясь наглядной формой представления динамических дискретных ветвящихся альтернатив, позволяют имитировать долгосрочный процесс развития исследуемой системы при различных возможных внешних и внутренних условиях, учитывая дискретность будущих состояний системы, определять рациональную стратегию развития исследуемой системы. Процедуры формирования и анализа графа развития энергетики страны реализованы в виде пакета прикладных программ «Корректива». Анализ графов развития больших размеров проводится с помощью распределенных вычислений. Приводится описание исследования устойчивого развития энергетики Вьетнама и его энергетической безопасности с 2015 по 2030 гг., выполненного в 2015 г. Институтом энергетической науки Вьетнамской академии науки и технологий. На основе данных этого исследования показано применение методов комбинаторного моделирования для формирования и анализа вариантов устойчивого развития энергетики Вьетнама с учетом требований энергетической безопасности. Создан граф развития топливно-энергетического комплекса Вьетнама, состоящий из 531 442 узлов. Его обсчет проводился в распределенной вычислительной среде, состоящей из вычислительных узлов высокопроизводительного кластера Института динамики систем и теории управления имени В.М. Матросова Сибирского отделения Российской академии наук. На основе результатов расчета была определена оптимальная стратегия развития энергетики Вьетнама, обеспечивающая минимум затрат на развитие и функционирование топливно-энергетического комплекса в рассматриваемый период времени.

9. Постановка задачи формирования направлений развития автоматизированных систем организационного типа и алгоритм ее решения [№2 за 2017 год]
Авторы: Лясковский В.Л., Бреслер И.Б., Алашеев М.А.
Просмотров: 8501
В статье рассматриваются постановка задачи формирования направлений развития автоматизированных систем обработки информации и управления организационного типа и алгоритм ее решения. Необходимость решения данной задачи обусловлена тем, что многие автоматизированные системы создаются и эксплуатируются в течение десятилетий, при этом в процессе эксплуатации меняются требования, предъявляемые к этим системам, поэтому возникает потребность в периодическом формировании решений по приведению состояния автоматизированной системы в соответствие новым требованиям. В качестве основного показателя эффективности формируемых решений принят комплексный показатель, характеризующий степень автоматизации функциональных процессов, реализуемых в системе. В качестве ограничений выступают требования к обязательной автоматизации наиболее важных функциональных процессов и своевременности их выполнения, а также предельно допустимые финансовые и временные ресурсы процесса развития автоматизированной системы. Проведенный анализ алгоритмической сложности решения задачи показывает невозможность ее решения путем рассмотрения всех возможных вариантов из-за экспоненциальной зависимости количества решений от размерности исходных данных. В связи с этим разработан эвристический алгоритм, позволяющий существенно сократить количество рассматриваемых вариантов и получить рациональное решение задачи при относительно небольшой вычислительной сложности. Предложенный алгоритм позволяет обосновать решения по разработке и изготовлению комплексов средств автоматизации для оснащения органов управления из состава автоматизированных систем обработки информации и управления организационного типа, а также продления ресурса действующих в системе средств автоматизации. Предполагается реализовать алгоритм в автоматизированной системе поддержки принятия решений, представляющей собой программный комплекс, функционирующий на ПЭВМ потребительского класса.

10. Оценка эффективности методов решения задач обеспечения устойчивости функционирования распределенных информационных систем [№2 за 2017 год]
Автор: Есиков Д.О.
Просмотров: 10129
Для принятия обоснованных решений в части организации процессов хранения и обработки данных для обеспечения устойчивости функционирования распределенных информационных систем предложено применять комплекс разработанных математических моделей оптимизации распределения элементов ПО функциональных задач по узлам сети, распределения информационных ресурсов по центрам хранения и обработки данных, состава технических средств системы хранения и обработки данных, распределения резерва информационных ресурсов по центрам хранения и обработки данных. Показано, что данные задачи относятся к классу задач дискретной оптимизации с булевыми переменными. Для решения формализованных задач предложено и экспериментально проверено применение метода ветвей и границ и генетических алгоритмов. Для повышения эффективности этого метода рекомендован алгоритм предварительного определения порядка ветвления переменных путем однократного решения приближенным методом задачи, двойственной по отношению к исходной. Проведена экспериментальная проверка эффективности метода ветвей и границ для решения задач обеспечения устойчивости функционирования распределенных информационных систем, в том числе с использованием алгоритма предварительного определения порядка ветвления переменных. Дана оценка влияния исходных данных на общую производительность метода ветвей и границ. Определены наиболее эффективные для решения разработанных задач стратегии ветвления переменных. Предложены варианты основных операторов, а также схемы начальной инициализации исходной популяции генетического алгоритма для решения задач обеспечения устойчивости функционирования распределенных информационных систем. Для повышения качества получаемого генетическим алгоритмом решения обосновано использование адаптивной схемы репродукции особей и островной схемы организации вычислений. Экспериментально проверена эффективность предложенных генетического и островного генетического алгоритмов и определены параметры генетических алгоритмов, обеспечивающие максимальное качество получаемого решения. Подтверждена возможность управления точностью получаемого решения за счет изменения параметров алгоритма при введении ограничений на время решения. Дана сравнительная оценка метода ветвей и границ и островного генетического алгоритма при решении формализованных задач, определены области их эффективного применения.

| 1 | 2 | 3 | Следующая →