Организация распределенного хранилища, оптимизированного под статический анализ, страница 5

Зависимость вероятности репрезентативности от номерапоступающего элементаНа этом графике синяя линия (Alpha) – вероятность, а красная (OK) – функция от вероятности следующего вида:Ÿ(B) =1, B ≥ BO;/ ,0, B < BO;/ .Такая функция позволяет проследить ситуации, когда нарушается требуемый уровень репрезентативности выборки на первом узле.Если мы посмотрим на аналогичный результат для случая αO;/ = 0,99 , тоувидим, что моменты нарушения репрезентативности происходят«дольше» до достижения определенного количества данных в хранилище(рис. 14).1,110,90,80,70,6AlphaOK0,50,40,30,20,10110100100010000100000Рисунок 14. Зависимость вероятности репрезентативности выборкина первом узле от номера поступающей записиВвиду таких различий между результатами для разных пороговых вероятностей, рассмотрим отдельно случай BO;/ = 0,9; 0,95; 0,975; 0,99.• ¢£¤¥ = 0,9Приведем график зависимости вероятности репрезентативности выборки на первом узле для алгоритма случайного распределения инашего алгоритма (рис.

15).1,0510,950,90,850,80,750,7500049999,9999999999 499999,999999999 4999999,99999999 49999999,9999999Рисунок 15. Зависимость вероятности репрезентативности от количества данных для k = 2, M = 1001,0510,950,90,850,80,750,70,650,65000500005000005000000Рисунок 16. Зависимость вероятности репрезентативности для k = 4,M = 121,0510,950,90,850,80,750,70,650,6100000010000000100000000Рисунок 17.

Зависимость вероятности репрезентативности от количества данных при k = 10 M = 40Из результатов экспериментов видно, что наш алгоритм дает стабильнолучший результат, чем алгоритм случайного распределения на этих жеданных. Это выполняется как и для случая малого количества интерваловкритерия, так и для случая большого количества серверов.• ¢£¤¥ = 0,95При таком заданном пороге ситуация практически не меняется – нашалгоритм выдает стабильно хороший результат, а случайное распределение выходит на хороший результат только при очень большом количестве данных.1,110,90,80,70,60,50,410100100010000100000100000010000000 100000000Рисунок 18. Зависимость вероятности репрезентативности от количества данных при M = 20 k = 4• ¢£¤¥ = 0,9910,980,960,940,920,90,880,860,840,820,80,780,760,740,720,7100000010000000100000000Рисунок 19. Зависимость вероятности репрезентативности от количества данных в хранилище для k =10, M = 20Исходя из экспериментальных данных, мы можем утверждать, что в случаес небольшим количеством критериев (M < 30) и/или с большим количеством серверов (k > 8) алгоритм случайного распределения данных даетрезультат хуже и не стабильнее, чем наш алгоритм.Таким образом, мы можем утверждать, что разработка собственного алгоритма, обеспечивающего репрезентативность выборки на выбранном узледля выбранного измерения выполнена успешно.Однако протестирована лишь незначительная часть возможностей хранилища, оптимизированного под статистический анализ.

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

Это своего рода измерение «средней температуры по больнице», которое может быть выполнено средствами Hadoop над всеми данными. А такие интересные и сложные виды анализа, как факторный иликорреляционный, которые плохо реализуются средствами Hadoop иMapReduce, проводить на такой выборке мы не можем. Однако, наше решение легко масштабируется на случай поддержки репрезентативностинескольких измерений на одном узле.

Каким образом – будет рассказанов следующей главе.5. Расширение задачиКак было сказано выше, обеспечение репрезентативности только одногокритерия не дает нам столь широких возможностей анализа, как хотелосьбы. Действительно, мы можем выполнять на выборке по одному измерению лишь определительный анализ: узнать её математическое ожидание,дисперсию и другие параметры распределения, однако факторный, корреляционный и регрессионный виды анализа нам недоступны.Оказывается, наше решение с помощью критерия хи-квадрат хорошо масштабируется на случай поддержки репрезентативности сложной выборкидля двух и более измерений одновременно. Рассмотрим этот случай подробно.5.1.Репрезентативность по двум и более распределениям на одном узлеБудем рассматривать задачу анализа на данных, которые использовалисьв тестах.

Помимо среднесуточной температуры, каждая запись определяется датой замера и номером станции. Допустим, мы хотим не толькознать среднюю температуру вообще, а исследовать зависимость параметров температуры от номера станции. Рассмотрим, как это можно сделатьсредствами хи-квадрат.Так как критерий хи-квадрат не опирается на то, что нам известно распределение данных, а для его применения важно знать только частотные характеристики попадания данных под определенные интервалы и критерии, то мы можем «расширить» наши интервалы таким образом, чтобыдля каждого интересующего нас интервала температуры рассматривать ираспространенность её в выбранной нами станции.Например, у нас была следующая частотная таблица для нашей выборкина узле:№ интервала1232Количество данных, попавших винтервал4W5‚6¦7ŽˆТаблица 3.

Таблица частот для одного измеренияТеперь, рассматривая еще и номер станции, мы можем составить следующую таблицу частот:№ интервала12Станция №1Станция №2Станция №3Станция №4Станция №52W‚¦345672W‚¦Žˆ2WWW‚W¦WŽWˆW222‚2¦W2W‚W¦‚2‚‚‚¦¦2¦‚¦¦Ž2Ž‚Ž¦Таблица 4. Таблица количества данных для заданного интервала иномера станцииПри этом выполняется следующее: n! = ∑¦89;8ˆ2ˆ‚ˆ¦для всех i от 1 до 7.Статистическая сумма тогда подсчитывается не по количеству интерваловM, а по количеству интервалов, помноженному на количество станций(или, в общем случае, количество интервалов второго измерения).Если мы захотим проводить анализ не только в зависимости от номерастанции, но и в зависимости от года, когда снималась температура, нашатаблица «превратится» в параллелепипед, по третей стороне которого будет варьироваться год измерения. Тогда статистическая сумма будет высчитываться по количеству интервалов температуры, помноженной на количество станций и количество лет измерений.Очевидно, что вычисления на каждом шаге добавления данных возрастают с увеличением количества измерений, репрезентативность которыхмы хотим обеспечить на выбранном узле.

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

Предположим, на первом узле мы хотимиметь репрезентативную выборку по температуре, на втором – по станциям. Например, для чуть важнее распределение по температуре, нежеличем по станциям, поэтому мы присваиваем этим требованиям вес 0,6 и 0,4соответственно. Так же нас интересует равномерное распределение данных на хранилище, но только при выполнении первых двух требований.Допустим, мы посчитали статистическую сумму и квантиль хи-квадрат дляпервого и второго требования.

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

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