Организация распределенного хранилища, оптимизированного под статический анализ (1187410), страница 4
Текст из файла (страница 4)
Коэффициенты для аппроксимации ГолдштейнаВ реализованной модели для данной работы использовалась аппроксимация Корниша-Фишера как наиболее часто встречающаяся для составлениятаблиц квантилей.Чтобы не приходилось выполнять вычисления на каждом шаге добавленияданных в хранилище, можно, зная заранее максимальное количество измерений D и требуемую вероятность репрезентативности α, вычислить всевозможно необходимые для дальнейших вычислений квантили распределения хи-квадрат.3.7.Проблема заполнения пустого хранилищаВ процессе заполнения пустого хранилища возникает следующая проблема: при малом количестве данных высока вероятность того, что этиданные по измерению попадут в один интервал.
В этом случае критерийхи-квадрат не применим, так как мы получаем нулевую степень свободыдля вычисления квантилей. Следовательно, в данной ситуации необходимо принимать решения иным способом. В нашей модели реализованорешение, позволяющее заполнение только первого узла в случае, если вседанные в хранилище принадлежат одному интервалу измерения. Этообеспечит максимальную репрезентативность первого узла. Однако, еслихранилище будет довольно долго заполняться такими данными, возникнетсильная перегрузка на первом узле по сравнению с другими узлами, что,говоря вообще, недопустимо. Но так как в данной работе мы рассматриваем вопрос статистического анализа как основной, мы используемименно это решение.
Если понадобится сохранять равномерность распределения данных в хранилище и другие возможные условия, следует задать «вес» этим условиям и в ситуации, описанной выше, принимать решения согласно «взвешиванию» нарушения условий.3.8.Оптимизация алгоритма распределения данныхПри большом потоке данных для заполнения хранилища нам крайневажна скорость принятия решения. Поэтому нам необходимо как можнолучше оптимизировать наш алгоритм.
Сделаем это следующим образом:вместо того, чтобы считать каждый раз две статистических суммы, будемхранить значение суммы после предыдущего шага и вычислять лишь добавку к сумме для случая добавления в общую выборку и добавления вобе выборки.Напомним выражение для статистической суммы при B; и Y; количествезаписей для интервала критерия $ в общей выборке и в выборке первогоузла соответственно. Тогда общее количество данных и количество данныхна первом узле будет:'= ∑X;9 B; и= ∑X;9 Y;соответственно. Запишем выражение для статистической суммы:.=/2Z,/0 = ('+) ∑X89 \/Z (?]/Z (?] ^ _] ) 2`B8 +^_ )]/0 (?] ^ _] ) 2/Z ^/0a b.a +/Z ^/0/0 (?] ^_] )`Y8 +Упростим данную формулу, получим следующее:.=/2Z,/0 = ('+?]h) ∑X89•(?] ^_] ) /Z+_]h/0‘ + 3(').+Теперь значительно проще рассмотреть случай добавления элемента с интервалом измерения r в общую выборку и в обе выборки:.=/2Z^ ,/0.=/2Z^,/0 ^=('+XB82Y821+ 1) 3+ ” + 3(“(B8 + Y8 ) ' + 1'89 ,8•–( ' + + 1) (B– + 1)2 Y82++ ”“(B– + 1 + Y– )'+1=('++?]hX2) ∑89 ,8•–•(?] ^_] ) /Z ^˜(/Z ^/0 ^2) (?— ^ )h(?— ^2^_— )/Z ^Найдем и упростим разницы š' = .=/2Z ^.=/2Z,/0 .
Получим:+,/0+(_— ^ )h/0 ^_]h/0 ^™.‘ + 3('++− .=/2Z ,/0 и š = .=/2Z ^,/0 ^+ 1)+ 2) +−/Z ^/0 ^?— ^ _— ^š =где ∆ =X8•–8•–B82Y821++ ∆ +333B8 + Y8B8 + Y8' ( ' + 1)š' =где ∆ =X˜(?— ^ )h/Z ^+X_—h/0™−?— ^_— /ZB82+3B8 + Y8' ( ' + 1)−˜'8•–/Z ^/0 ^2 (?— ^ )h?— ^ _— ^2/Z ^+(_— ^ )h/0 ^˜/Z ^/0 ?—h™−+_—h/0™.XY82−+ ∆2 + 63( + 1)B8 + Y8'˜/Z ^/0 ?—h?— ^_— /Z+8•–_—h/0™.Таким образом, мы можем дополнительно хранить значения:XB82j' = 3,B8 + Y889XY82j =3B8 + Y889С помощью которых вычислять статистическую сумму за время O(1), а неза O(D). При малых D это упрощение не имеет смысла, однако при D > 20имеет смысл перейти к этому оптимизированному способу расчета.4. Результаты проведенных тестовМодель хранилища была реализована на языке Python.
Выполнялись тесты на сохранение репрезентативности выборки при добавлении в хранилище метеорологических данных: показания среднесуточной температурыза выбранную дату на выбранной станции. Общее количество записей составило 62 млн, что позволяло оценить работу алгоритма случайного распределения и собственного алгоритма на большой общей выборке данных.Сначала были проведены тесты случайного распределения, чтобы выяснить те области параметров хранилища, в которых требуется улучшениерепрезентативности за счет собственного алгоритма.
Затем, были проведены тесты на собственном алгоритме и результаты этих тестов сравнивались с результатами случайного распределения.Отметим, что в нашем случае было 3 параметра, которые варьировались:• Количество загружаемых в хранилище данных N;• Количество узлов в хранилище k;• Количество интервалов измерения, по которому должна сохранятьсярепрезентативная выборка M;Для собственного алгоритма есть еще один варьируемый параметр: минимальная вероятность репрезентативности α•!ž выборки на первом узле.Полученные результаты рассмотрим подробнее.4.1. Тесты для случайного распределенияСначала были проведены тесты для небольшого количества данных:• N от 10 до 10240• K от 2 до 5• M от 12 до 120Для случая малого количества данных результат предсказуем: случайноераспределение дает непредсказуемый результат по вероятности репрезентативности:1,21Вероятность0,80,60,40,20110100100010000100000Количество данных на узлеРисунок 6. Зависимость вероятности репрезентативности выборки наузле от количества узлов для M = 60, k = 2Следует отметить, что для каждого набора параметров было проведено 10независимых измерений и в анализе использовался средний результат.Также отметим, что ошибка вычислений вероятности составила 0,01.Для случая других параметров результаты те же:1,11Вероятность0,9K = 2, M = 60K = 3, M = 60K = 4, M = 60K = 5, M = 120,80,70,60,55505005000Количество данных в хранилищеРисунок 7.
Зависимость вероятности репрезентативности данных напервом узле от количества данных в хранилище для разного количествасерверовСитуация похожа как и для разного количества серверов (рис. 7), так и дляразного количества интервалов (рис. 8).Из этих графиков видно, что есть зависимость репрезентативности выборки от количества серверов и от количества интервалов.
Но её характерисследовался на большом количества данных и будет описан ниже.Из рисунков 6 – 8 видно, что при малом количестве данных вероятностьрепрезентативности выборки на первом узле не может быть удовлетворительной. Однако, данная область мало интересна для случая распределенного хранилища, так как количество записей, равное 10 000 не являетсясколь угодно близким к реальному количеству записей в хранилище.1,11Вероятность0,9MMMMMM0,8= 120= 60= 40= 30= 20= 120,70,60,55505005000Количество данных в хранилищеРисунок 8. Зависимость вероятности репрезентативности распределения данных на первом узле от количества данных в хранилище для разных количеств интерваловДалее был проведен тест для большего количества данных, а именно следующих значений параметров:• N от 10 000 до 10 240 000• K от 2 до 4• M от 12 до 120В результате было получено следующее (рис.9 и рис. 10).
Видно, что качество выборки улучшается с количеством данных, но остается зависимостьот количества узлов (рис. 9) и количества интервалов распределения (рис.10).Особенно непредсказуемый результат получается для случая малого количества интервалов измерения.1,05Вероятность10,95K = 2, M = 60K = 3, M = 60K = 4, M = 600,90,850,81,00E+0041,00E+0051,00E+0061,00E+0071,00E+008Количество данных в хранилищеРисунок 9. Зависимость вероятности репрезентативности выборки отколичества данных в хранилище для различных количеств узлов1,1Вероятность10,9M=M=M=M=M=M=0,80,712060403020120,60,59000900000,000000001Количество данных в хранилищеРисунок 10. Зависимость вероятности репрезентативности от количества данных в хранилище для разного количества интервалов измеренияТакже были проведены измерения для большего количества данных (до62 000 000) и построен общий график зависимости вероятности репрезентативности выборки от количества данных и от количества интервалов критерия.
Количество серверов было фиксированным и равным 4. Сам графикприведен на рис. 11.Рисунок 11. График зависимости вероятности репрезентативности выборки от количества данных и количества интервалов измеренияИз общего графика видно, что вероятность репрезентативности низкая умалого количества интервалов измерения даже при большом количестведанных. Следовательно, это та область, где случайное распределение даетплохой результат репрезентативности.Приведем еще отдельно график зависимости вероятности репрезентативности от количества узлов в хранилище для случая N = 62 000 000 и M = 60(рис. 12).1,110,90,80,70,60,50,40510152025Рисунок 12.
Зависимость вероятности репрезентативности выборкиот количества узлов в хранилищеВыделить общую область для сравнения алгоритмов затруднительно потой причине, что результат работы нашего алгоритма зависит от заданногопорога минимальной вероятности репрезентативности. Однако, рассмотрев несколько случаев значения этой вероятности, вполне можно сравнитьрезультаты работы обоих алгоритмов. Что и будет сделано в следующемпункте.4.2. Тесты для собственного алгоритма распределенияТесты для собственного алгоритма распределения проводились следующим образом: был включен контролирующий модуль, в котором независимо от модуля распределения подсчитывалась статистическая сумма длякритерия хи-квадрат. После принятия решения о распределении очередной записи контролирующий модуль вычислял текущую вероятность репрезентативности выборки на первом узле и запоминал её.
В конце тестарезультаты записывались в итоговый файл. Таким образом, ввиду детер-минированности нашего алгоритма, мы получаем степень репрезентативности для всех количеств данных от 0 до максимальной для теста. Чтобыпроверить алгоритм для разных условий, был проведен тест с другим порядком загрузки данных – начиная не с первого, а с другого файла. Однакона результат при больших N это не повлияло.Важный результат такого исследования – это возможность понять динамику репрезентативности выборки при добавлении данных в хранилище,а также её зависимость от выбранного минимального порога вероятности.Для наглядности приведем график зависимости вероятности репрезентативности выборки от порядкового номера поступающей записи (рис.13)для M = 120, N(max) = 50000, k = 2 и порога вероятности BO;/ = 0,9.1,110,90,80,70,6AlphaOK0,50,40,30,20,10110100100010000100000Рисунок 13.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
