Поручиков М.А. Анализ данных. М. А. Поручиков
 Скачать 1.28 Mb.
|
|
БЫСТРОДЕЙСТВИЕ СИСТЕМ АНАЛИЗА ДАННЫХ Общие сведения При проектировании систем анализа данных важно представлять, какое время будет затрачено на решение вычислительных задач. В общем случае быстродействие систем анализа данных зависит от многих факторов: - вычислительной сложности использованных алгоритмов; - способа программной реализации алгоритмов; - аппаратного обеспечения. Вычислительная сложность Вычислительная сложность – это зависимость трудоемкости вычислений от объема обрабатываемых данных. Например, вычислительная сложность алгоритма линейного поиска n n O = ) ( , а алгоритма бинарного поиска – n n O log ) ( = ( рис. 52). Рис. 52. Вычислительная сложность алгоритмов поиска Очевидно, что один и тот же объем данных будет обработан быстрее алгоритмом с меньшей вычислительной сложностью. Например, вычислительная сложность алгоритма вычисления произведения матриц «по определению» 3 ) ( n n O = , а алгоритма 76 Штрассена – 81 , 2 ) ( n n O = . Очевидно, что один и тот же объем данных будет обработан быстрее алгоритмом с меньшей вычислительной сложностью Предположим, что имеются два алгоритма, имеющие соответственно вычислительную сложность ) ( 1 n O и ) ( 2 n O . Для сравнения их вычислительной сложности необходимо найти значения предела ) ( ) ( lim 2 1 n O n O n ∞ → (24) При этом если значение выражения (24): - равно ∞ , то вычислительная сложность функции ) ( 1 n O больше, чем вычислительная сложность функции ) ( 2 n O ; - равно 0, то вычислительная сложность функции ) ( 2 n O больше, чем вычислительная сложность функции ) ( 1 n O ; - равно некоторому числу, то функции ) ( 1 n O и ) ( 2 n O имеют одинаковую вычислительную сложность. Пример Пусть имеются два алгоритма с вычислительной сложностью соответственно n e n O = ) ( 1 , 2 2 ) ( n n O = , тогда ( ) ( ) ∞ = = ′ ′ = = ∞ → ∞ → ∞ → ∞ → n e n e n e n O n O n n n n n n n 2 lim lim lim ) ( ) ( lim 2 2 2 1 Следовательно, вычислительная сложность первого алгоритма больше вычислительной сложности второго алгоритма. Экспериментальное определение вычислительной сложности Допустим, что реализован некоторый модуль системы анализа данных, предназначенный для обработки информации. Для использования этого модуля в реальных задачах необходимо четко представлять его вычислительную сложность. Для определения вычислительной сложности необходимо провести эксперимент, в ходе которого нужно измерить время обработки этим модулем некоторого объема исходных данных. 77 В результате эксперимента будут получены точки вида «объем данных - время обработки» (рис. 53, а). Аппроксимировав экспериментальные данные какой-либо функцией, можно построить прогноз трудоемкости вычислений для любого, в том числе большего объема данных (рис. 53, б). Рис. 53. Прогнозирование вычислительной сложности Программное обеспечение square_matrix_multiply Программное обеспечение square_matrix_multiply предназначено для исследования факторов быстродействия систем анализа данных на примере операции умножения квадратных матриц. Пользователь может варьировать размеры матриц, количество вычислительных потоков (рис. 54). Дополнительно может быть задан размер серии экспериментов. Программное обеспечение выполняет ряд экспериментов, в ходе которых проводится измерение времени, затраченного на умножение матриц. Рис. 54. Схема эксперимента Программное обеспечение реализовано в виде приложения для операционной системы Windows (рис. 55). Размер матриц Программное обеспечение square_matrix_multiply Число потоков Размер серии Время вычислений a) б) 78 Рис. 55. Интерфейс программного обеспечения square_matrix_multiply Запуск эксперимента производится нажатием кнопки «Запуск». Результатом эксперимента является набор данных, включающий как условия эксперимента, так и экспериментальные данные. Результаты эксперимента можно сохранить в текстовый файл формата csv с помощью нажатия кнопки «Сохранить». Прервать выполнение экспериментов можно с помощью кнопки «Стоп». Вопросы для самоконтроля 1 Перечислите факторы быстродействия систем анализа данных. 2 Дайте определение понятия «вычислительная сложность». 3 Приведите принцип сравнения вычислительной сложности алгоритмов. 79 4 Приведите пример сравнения вычислительной сложности алгоритмов. 5 Приведите алгоритм экспериментального определения вычислительной сложности. 6 Приведите алгоритм прогнозирования быстродействия. Задачи 1 Сравните вычислительную сложность алгоритмов с n n n O log ) ( = и 2 ) ( n n O = 2 Решите задачу. Проведен ряд экспериментов по измерению времени, затрачиваемого на обработку массива данных (табл. 30). Таблица 30. Экспериментальные данные Размер массива данных, кбайт Время обработки, с 10 6 20 10 30 19 40 26 50 36 60 48 70 62 80 88 90 96 100 115 Найдите функциональную зависимость времени обработки данных от размера массива данных. 3 Решите задачу. Экспериментальным путем определено, что зависимость времени t (секунды), затрачиваемого на обработку файла данных объемом S Мбайт, подчиняется закону 2 2 , 5 S t ⋅ = (25) Определите: 1) время, которое будет затрачено на обработку файла объемом 5 Мбайт; 2) объем файла, который будет обработан за 20 с. 80 Лабораторная работа «Быстродействие систем анализа данных» Общие сведения Целью работы является приобретение навыка анализа быстродействия систем обработки данных. Задачи: 1 Определение вычислительной сложности алгоритма. 2 Прогнозирование затрат времени на обработку данных. В качестве инструментального средства используется программное обеспечение square_matrix_multiply, описанное ранее на с. 77. Исходные данные Таблица 31. Варианты задания Вариант Размер матриц Количество вычислительных потоков Мин. Макс. Шаг Мин. Макс. Шаг 1 100 1000 100 1 3 1 2 200 1100 100 1 4 1 3 400 1200 100 1 5 1 4 600 1300 100 1 3 1 5 800 1400 100 1 4 1 6 500 1800 200 1 5 1 7 300 1900 200 1 3 1 8 400 1900 200 1 4 1 9 500 2000 200 1 5 1 10 300 2000 200 1 3 1 Порядок выполнения 1 Подготовка: 1.1 Выберите задание (табл. 31). 1.2 Загрузите программное обеспечение square_matrix_multiply из курса «Анализ данных» СДО университета [2]. 1.3 Опишите вычислительную систему: процессор, оперативная память, операционная система. 2 Проведение эксперимента: 2.1 Запустите программу square_matrix_multiply. 81 2.2 Задайте условия эксперимента (размер матриц, количество вычислительных потоков) в соответствии с заданием. Установите число экспериментов, равное трём. 2.3 Проведите эксперименты и сохраните их результаты. В ходе экспериментов сделайте копию экрана с изображением вкладок «Процессы» и «Быстродействие» диспетчера задач Windows. 2.4 Выполните предварительную обработку экспериментальных данных – усреднение результатов по серии экспериментов. Предварительную обработку удобно проводить с помощью инструмента «Сводные таблицы» программного обеспечения Microsoft Excel. 2.5 Постройте графики зависимости (для разного числа потоков) времени выполнения вычислений от размера матриц. Пример приведен ниже (рис. 56). Рис. 56. Зависимость времени вычислений от размера матриц 2.6 Определите функцию, описывающую вычислительную сложность использованного в программе square_matrix_multiply алгоритма. Для этого можно воспользоваться инструментом «Линия 82 тренда» при построении диаграмм в Microsoft Excel. Построить тренд для случая одного вычислительного потока. Пример приведен ниже ( рис. 57). Рис. 57. Аппроксимация экспериментальных данных 3 Анализ результатов: 3.1 Сделайте выводы о влиянии объема исходных данных и фактора распараллеливания на время решения вычислительной задачи. 3.2 Сделайте выводы о влиянии объема исходных данных и фактора распараллеливания на время решения вычислительной задачи. 3.3 Сравните время, необходимое для решения задачи умножения матриц размером 10000x10000 при одном вычислительном потоке с помощью алгоритма, использованного в программе square_matrix_multiply и c помощью алгоритма Штрассена ( 81 , 2 ) ( n n O = ). 3.2 Продемонстрируйте преподавателю полученные результаты. При наличии замечаний провести повторные эксперименты. 4 Отчет о работе: 83 4.1 Составьте отчет. 4.2 Преобразуйте отчет в формат PDF. 4 .3 Создайте архив в формате ZIP, содержащий отчет и таблицу с расчетами и графиками (файл Excel). 4 .4 Прикрепите архив в раздел «Отчет по лабораторной работе №6» (быстродействие систем анализа данных) курса «Анализ данных» СДО университета [2]. 4.5 При наличии замечаний от преподавателя скорректируйте отчет. Содержание отчета Отчет должен содержать: 1 Титульный лист: наименование работы, вариант задания, ФИО студента, номер учебной группы, дата выполнения работы. 2 Реферат. 3 Оглавление. 4 Задание. 5 Описание выполненной работы. 6 Условия эксперимента: 6.1 Исходные данные. 6.2 Описание вычислительной системы. 7 Эксперименты: 7.1 Копия экрана (диспетчер задач, вкладка «Процессы»). 7.2 Копия экрана (диспетчер задач, вкладка «Быстродействие»). 7.3 Экспериментальные данные. 8 Обработка экспериментальных данных: 8.1 Результаты усреднения экспериментальных данных. 8.2 Графики зависимости времени выполнения вычислений от размера матриц, зависимости времени выполнения вычислений от количества вычислительных потоков. 8.3 Функция, описывающая вычислительную сложность использованного алгоритма. 9 Выводы. 10 Список использованных источников (нормативные документы). 11 Приложения. Отчет должен быть оформлен в соответствии с действующими стандартами университета [18, 19]. 84 ЗАКЛЮЧЕНИЕ В данном учебном пособии рассмотрены основы анализа данных. Об интересе к сфере анализа данных свидетельствует не только рост числа научных исследований, но и еще два фактора: 1 Популярность соответствующих массовых онлайн-курсов. По состоянию на декабрь 2015 года на образовательной платформе Coursera [24] было представлено 1764 курса, более 100 из которых посвящено сфере анализа данных. 2 Появление большого количества конкурсов по анализу открытых данных. Наиболее полная информация о подобных конкурсах содержится в разделе «Конкурсы» портала «Открытые данные России» [25]. Читателям, заинтересованным в систематизации и углублении знаний в сфере анализа данных, можно рекомендовать прохождение курсов «Machine Learning» Стэнфордского университета (автор Andrew Ng) [25] и «Введение в машинное обучение» Высшей школы экономики (авторы К.В. Воронцов и Е. Соколов) [27]. 85 БИБЛИОГРАФИЧЕСКИЙ СПИСОК 1. Российская Федерация. Министерство образования и науки. Приказ от 14 января 2010 г. №27 «Об утверждении и введении в действие федерального государственного образовательного стандарта высшего профессионального образования по направлению подготовки 080500 бизнес-информатика (квалификация (степень) "бакалавр")» [Текст] : офиц. текст. — М. : Минюст РФ, 2010. — 15 с. 2. Курс: Анализ данных [Электронный ресурс] : [б. и.], 2013. - Электрон. текстовые дан. on-line. - Загл. с титул. экрана. - URL : http://do.ssau.ru/moodle/course/view.php?id=442 (Дата обращения 23.12.2015). 3. Hilbert, M. The world's technological capacity to store, communicate, and compute information [Text] / M. Hilber, P. López. // Science, Volume 332, Issue 6025, April 2011, Pages 60-65. 4. CMS releases new batch of research data from LHC | CMS Experiment [ Электронный ресурс] : [б. и.], 2016. - Электрон. текстовые дан. on-line. - Загл. с титул. экрана. - URL : http://cms.web.cern.ch/news/cms-releases-new-batch-research-data-lhc ( Дата обращения 25.04.2016). 5. Boeing 787s to create half a terabyte of data per flight, says Virgin Atlantic [ Электронный ресурс] : [б. и.], 2016. - Электрон. текстовые дан. on-line. - Загл. с титул. экрана. - URL : http://www.computerworlduk.com/news/data/boeing-787s-create-half- terabyte-of-data-per-flight-says-virgin-atlantic-3433595/ ( Дата обращения 25.04.2016). 6. Machine learning | artificial intelligence | Britannica.com [ Электронный ресурс] : [б. и.], 2015. - Электрон. текстовые дан. on- line. - Загл. с титул. экрана. - URL : http://global.britannica.com/technology/machine-learning ( Дата обращения 23.12.2015). 7. Анализ данных – обучение в Яндексе [Электронный ресурс] : [б. и.], 2015. - Электрон. текстовые дан. on-line. - Загл. с титул. экрана. - URL : https://academy.yandex.ru/events/data_analysis ( Дата обращения 23.12.2015). 8. Deep Blue [Text] / M. Campbell, J. Hoane Jr., F.-h. Hsu [et al.] // Artificial Intelligence, Volume 134, Issue 1-2, January 2002, Pages 57-83. 86 9. Building watson: An overview of the deepQA project [Text] / D. Ferrucci, E. Brown, J. Chu-Carroll [et al.] // AI Magazine. Volume 31, Issue 3, September 2011, Pages 59-79. 10. Google Self-Driving Car Project [ Электронный ресурс] : [б. и.], 2016. - Электрон. текстовые дан. on-line. - Загл. с титул. экрана. – URL : https://www.google.com/selfdrivingcar ( Дата обращения 23.12.2015). 11. Fast Artificial Neural Network Library (FANN) [ Электронный ресурс] : [б. и.], 2015. - Электрон. текстовые дан. on-line. - Загл. с титул. экрана. - URL : http://leenissen.dk/fann/wp (Дата обращения 23.12.2015). 12. OpenCV | OpenCV [Электронный ресурс] : [б. и.], 2015. - Электрон. текстовые дан. on-line. - Загл. с титул. экрана. - URL : http://opencv.org (Дата обращения 23.12.2015). 13. UCI Machine Learning Repository: Bank Marketing Data Set [ Электронный ресурс] : [б. и.], 2015. - Электрон. текстовые дан. on- line. - Загл. с титул. экрана. - URL : http://archive.ics.uci.edu/ml/datasets/Bank+Marketing ( Дата обращения 23.12.2015). 14. Data | The World Bank [Электронный ресурс] : [б. и.], 2015. - Электрон. текстовые дан. on-line. - Загл. с титул. экрана. - URL : http://data.worldbank.org (Дата обращения 23.12.2015). 15. Data.gov.ru: открытые данные России [Электронный ресурс] : [б. и.], 2015. - Электрон. текстовые дан. on-line. - Загл. с титул. экрана. - URL : http://data.gov.ru (Дата обращения 23.12.2015). 16. Федеральный закон от 27 июля 2006 г. № 149-ФЗ « Об информации, информационных технологиях и о защите информации» (http://base.garant.ru/12148555). 17. Главная Федеральная служба государственной статистики [Электронный ресурс] : [б. и.], 2015. - Электрон. текстовые дан. on- line. - Загл. с титул. экрана. - URL : https://www.gks.ru (Дата обращения 23.12.2015). 18. СТО СГАУ 02068410-004-2007. Общие требования к учебным текстовым документам [Текст]. — Введ. 2007—10—09. — Самара. : СГАУ, 2007. —30 с. 19. Приказ «Об актуализации стандартов СГАУ (СТО СГАУ) от 14.11.2014 № 381-О. - URL : 87 http://www.ssau.ru/files/science/org/no/osm/changes_sto_ssau.pdf (Дата обращения 21.01.2016). 20. Fern´andez-Delgado, M. Do we need hundreds of classifiers to solve real world classification problems? / M. Fern´andez-Delgado, E. Cernadas, S. Barro. [Text] // Journal of Machine Learning Research 15 (2014) 3133-3181 URL: http://jmlr.csail.mit.edu/papers/volume15/delgado14a/delgado14a.pdf. 21. UCI Machine Learning Repository [ Электронный ресурс]: [б. и.], 2015. - Электрон. текстовые дан. on-line. - Загл. с титул. экрана. - URL : http://archive.ics.uci.edu/ml/ ( Дата обращения 23.12.2015). 22. Data clustering: A review [Text] / Jain, A.K.a, M.N.b Murty, P.J.c Flynn [et al.] // ACM Computing Surveys, Volume 31, Issue 3, 1999, Pages 264-323. 23. Xu, R. Survey of clustering algorithms (Review) [Text] / R. Xu, D. Wunsch II, // IEEE Transactions on Neural Networks, Volume 16, Issue 3, May 2005, Pages 645-678. 24. Coursera – бесплатные онлайн-курсы от ведущих университетов мира | Coursera [Электронный ресурс] : [б. и.], 2015. - Электрон. текстовые дан. on-line. - Загл. с титул. экрана. - URL : https://www.coursera.org (Дата обращения 23.12.2015). 25. Конкурсы | Data.gov.ru [Электронный ресурс] : [б. и.], 2015. - Электрон. текстовые дан. on-line. - Загл. с титул. экрана. - URL : http://data.gov.ru/competitions (Дата обращения 23.12.2015). 26. Машинное обучение – Стэнфордский университет | Cousera [Электронный ресурс] : [б. и.], 2015. - Электрон. текстовые дан. on- line. - Загл. с титул. экрана. - URL : https://www.coursera.org/learn/machine-learning (Дата обращения 23.12.2015). 27. Введение в машинное обучение – Высшая школа экономики | Cousera [Электронный ресурс] : [б. и.], 2015. - Электрон. текстовые дан. on-line. - Загл. с титул. экрана. - URL : https://www.coursera.org/learn/introduction-machine-learning (Дата обращения 23.12.2015). Учебное издание Михаил Алексеевич Поручиков АНАЛИЗ ДАННЫХ Учебное пособие Редактор Т.К. Кретинина Доверстка Т.С. Зинкина Подписано в печать 02.06.2016. Формат 60х84 1/16. Бумага офсетная. Печать офсетная. Печ. л. 5,5. Тираж 100 экз. Заказ . Арт. 31/2016. ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «САМАРСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ имени академика С.П. КОРОЛЕВА» (Самарский университет) 443086 САМАРА, МОСКОВСКОЕ ШОССЕ, 34. Изд-во Самарского университета. 443086 Самара, Московское шоссе, 34. |