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

Допустим,нас интересует статистический анализ температуры: поэтому мы формируем репрезентативную выборку для этого измерения.Возникает вопрос, как измерять качество репрезентативности выборки.Для этого воспользуемся критериями однородности, известными из математической статистики.2.2.Критерии однородностиПуть у нас есть две выборки μ и η размеромисоответственно дляслучайных величин, распределение которых нам неизвестно. Чтобы определить, имеют ли обе выборки одно и тоже определение или нет, служаткритерии однородности. Один из этих критериев - критерий однородностихи-квадрат – позволяет утверждать с некоторой вероятностью, принадлежат ли выборки одному распределению.

Приведем его описание для общего случае нескольких выборок.Сразу отметим, что доказательство корректности и состоятельности критерия хи-квадрат излагается в [17][18]. Критерий хи-квадрат применяют канализу данных, имеющих дискретную структуру, конкретнее, когда в опытах наблюдается некоторый переменных признак, принимающий конеч-ное число K ≥ 2 различных значений. Но к такой схеме можно свести любую модель, применяя предварительно метод группировки данных [17],поэтому метод хи-квадрат применим на самом деле к анализу данных любой природы, т.е.

является в этом смысле универсальным. Кроме того, спомощью этого метода можно анализировать любое конечное число выборок. Итак, пусть осуществленосерий независимых наблюдений, состо-ящих из n , … , n наблюдений соответственно, и пусть ϑ! = (ϑ! , … , ϑ!# ) –частоты исходов $-ой серии, а p! = (p! , … , p!# ) − их вероятности ($ = 1, … ,). Тогда гипотеза однородности означает утверждение, что вероятностиисходов не менялись от серии к серии, т.е.H' : p = ⋯ = p = p = (p , … , p# ),где * – некоторый (неизвестный) вектор вероятностей. При этом p + ⋯ +p# = 1 .

Критерий проверки этой гипотезы состоит в том, что все данныеобъединяются в одну выборку объема n = n + ⋯ + n с частотами ис-ходов ϑ∗- , … , ϑ∗# . В итоге в [17] получена тестовая статистика критерия однородности хи-квадрат./20…/1:7n! ϑ∗1= n 334ϑ!- −6n! ϑ∗-2;9 89с помощью которой и строится критическая область критерия:<.=/20 …/1 > >? @.Для нахождения критической границы >? при заданном уровне значимости [18] B используется следующий предельный результат [19]:при n! → ∞ (i = 1, … , k):LG.=/20…/1 HH' I → χ2 G(k − 1)(N − 1)I.В силу этого результата при большихχ2K ?,(:K)(7K ) ,;можно полагать >? =где статистика .=/20…/1 вычисляется по формуле, приведен-ной выше.

Вероятность ошибочно отклонить при этом истинную гипотезуприблизительно равна B, еслидостаточно велико.Чтобы применить данный критерий к нашему случаю, рассмотрим его действие на примере со среднесуточной температурой.Есть общая выборка из N записей, а есть её подмножество – выборка изL записей. Каждая запись имеет характеристику – среднесуточную температуру на выбранной станции и в выбранную дату. Нам известно, что M ∈MO;/ , MOPQ . Разобьем этот отрезок на D равных отрезков и будем гово-рить, что температура имеет значение $, если её величина попадает на $ −й интервал.

Таким образом мы превратили непрерывную величину в дискретную. Для каждой записи мы знаем номер интервала, к которому принадлежит температура. Подсчитаем для каждого температурного отрезкаколичество записей для общей выборки и для выборки на первом узле иприведем их в таблице:Интервал1Общая выборкаВыборка на первомузлеBY2B2Y23BW..YW.D-2D-1BXK2 BXKYXK2 YXKDBXYXТаблица 1. Частотная таблица для среднесуточной температурыКритерий однородности Хи-квадрат позволяет определить, репрезентативна ли выборка на первом узле по отношению к общей выборке данных.Посчитаем статистику для нашего случая: k = 2, N = D, если общая выборкаразмера',а– размер выборки на первом узле:.=/2Z,/0 = () ∑X89 \/'+Z (?]`B8 +^_ )]/0 (?] ^ _] ) 2/Z ^/0/Z (?] ^ _] ) 2a b ./Z ^/0a +/0 (?] ^_] )`Y8 +Выполнив необходимые вычисления, мы получим значение статистикидля нашего случае.

Далее нам необходимо обратиться к таблице квантилей распределения хи-квадрат. Напомним, что квантиль – это число, прикотором функция распределения хи-квадрат равна заданной вероятностиα. Пример таблицы:0,10,20,30,40,50,60,70,80,910,020,060,150,280,450,711,071,642,7120,210,450,711,021,391,832,413,224,6130,581,011,421,872,372,953,664,646,2541,061,652,192,753,364,044,885,997,7851,612,3433,664,355,136,067,299,2462,23,073,834,575,356,217,238,5610,6472,833,824,675,496,357,288,389,812,0283,494,595,536,427,348,359,5211,0313,3694,175,386,397,368,349,4110,6612,2414,68104,876,187,278,39,3410,4711,7813,4415,99Таблица 2.

Таблица квантилей хи-квадрат.В нашем случае число степеней свободы есть (2 − 1)(c − 1) = c − 1. Значит, для строки с индексом, равным D-1, мы ищем ближайшее по значе-нию значение квантиля и определяем α. Полученное значение α и будетобозначать вероятность того, что выборка на первом узле репрезентативно представляет общую выборку данных, то есть имеет то же распределение.На основе формализованной формулировки задачи можно создавать самумодель хранилища, уделяя пристальное внимание модулю распределенияданных и контролю качества выборки.

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

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

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

Длякаждой записи, поступающей в хранилище, модуль записывает значениееё главного измерения и узел, на который эта запись была распределена.При запросе модуль вычисляет вероятность репрезентативности выборкина заданном узле по сравнению со всем массивом данных: вычисляетсястатистика и по квантилям определяется полученный уровень вероятности.Про подсчет квантилей распределения хи-квадрат будет рассказано впункте о вычислении функции распределения хи-квадрат.3.4.Алгоритм случайного распределения данныхСмысл алгоритма случайного распределения данных прост – мы пробуемсформировать репрезентативную выборку по определению – случайнымобразом выбирая данные из общей выборки.

Для большого количестваданных ожидается хороший показатель репрезентативности, однако принебольшом количестве данных или при большом количестве узлов ожидается непредсказуемый результат.При инициализации модуль получает количество узлов в хранилище. Припоступлении одной записи с помощью стандартных функций рандомизации языка Python случайно выбирается номер узла, на который следуетположить эту запись. Результаты тестирования этого алгоритма приведеныв следующей главе, а пока изложим принцип организации собственногоалгоритма распределения.3.5.Собственный алгоритм распределения данныхЧтобы поддерживать репрезентативность выборки на первом узле, будемиспользовать критерий хи-квадрат (описан в предыдущей главе) как числовой критерий для принятия решений и контроля репрезентативности.Отметим, что в отличие от случайного распределения для этого алгоритмауровень минимальной вероятности репрезентативности α должен быть задан заранее, до распределения данных на хранилище.

На каждом шаге заполнения хранилища, получая каждую запись отдельно, необходимо сделать следующий выбор: положить ли данные на первый узел или наостальные. В случае второго решения данные распределяются случайнымобразом среди оставшихся узлов для обеспечения равномерностинагрузки на узлы. Предлагается подсчитывать статистическую сумму дляпервого и второго случаев, и на основе этих данных принять необходимоерешение. Допустим, мы получили значение статистической суммы дляпервого узла Σ , для всех данных Σ и значение функции распределения хи-квадрат для данного количества интервалов измерения и вероятности ре2презентативности B − Χ/,K? .Так же нам известно количество данных,уже хранящихся на всех узлах L , . .

, L/ и общее количество данных на хранилище L' = L + ⋯ + L/ .Принятие решение о номере узла проходит в несколько этапов:• Определяем, сохраняется ли репрезентативность выборки при добавлении записи на первый узел.• Если сохраняется, проверяем, сохранится ли выборка, если данныене класть на первый узел. Если сохраняется, распределяем данныесогласно вопросу равномерной загруженности хранилища, иначе выбираем первый узел.• Если не сохраняется, проверяем сохранение репрезентативности вслучае выбора не первого узла.

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

Как именно изменится алгоритм, будет описано ниже.3.6. Вычисление функции распределения хи-квадратВажным вопросом в организации нашего хранилища является вычислениефункции распределения хи-квадрат и подсчет квантилей этого распределения. Функция распределения хи-квадрат выражается следующим образом:ij` , a2 2 ,fgh (:) (i) =k` a2где Г(m) и j(n, m) гамма-функция и неполная гамма функция соответственно. Они равны следующему:k(m) = o' > pK q Kr s>, m ∈ ℂ: uq(m) > 0,wj(n, m) = o' q Kr > PK s>.pОчевидно, что даже численное приблизительное вычисление для каждогошага анализа данных затруднительно. Поэтому в нашей модели мы воспользовались аппроксимациями для квантилей распределения хи-квадрат.Для получения приближенных значений квантилей распределения хи2квадрат x?,/существуют аппроксимации:• Аппроксимация Корниша-Фишера [20]:2x?,/=где:+ y√ + { +|√y = s√2+2 2(s − 1)3s2 − 7|=s∗9√2{=c+}√,s= †6s ‚ + 14s2 − 32c=4059s‚ + 256s 2 − 433}=s∗4860√22.0637 ∗ `‡−2.0637 ∗ `‡K??',‚2ˆ‚− 0.16a• Аппроксимация Голдштейна [21]2x?,/=Ž∗ ‹3;9'',‚2ˆ‚− 0.16a;K2, 0.5 ≤ B ≤ 0.999, 0.001 ≤ B < 0.5∗ s ; ∗ \n; +Œ;+•;2b•Wгде d определяется аналогично, а коэффициенты a, b, c приведены втаблице:i1a1.0000886b-0.2237368C-0.0151390420.47139410.02607083-0.00898600730.00013480280.011281860.022776794-0.008553069-0.01153761-0.0132329350.003125580.005169654-0.0069503566-0.00084268120.002530010.0010604380.00009780499-0.0014501170.0015653267Таблица 3.