Подсчет критерия хи-квадрата

[martell]

Здравствуйте. Неуверен верный ли раздел. Пытаюсь разобраться с критерием Кхи-квадрата.

Есть практическая задача: известно, что в некоторой выборке данных часть набора была сгенерирована при помощи генератора псевдослучайных чисел, а часть введена вручную. Требуется разделить сгенерированные данные от введенных вручную

Для теста пробую сделать на строках. В 2-м томе кнута искусство программирования есть вот такая формула
$V = \frac{1}{n}\sum\limits_{s=1}^{k}(\frac{Y^2_{s}}{P_{s}}) - n$
$k$ - количество выборочных значений, $n$ - количество байт в выборке, $P$ - вероятность, $Y$ - сколько раз в данных встречается $s$-й байт

Основная проблема для меня тут в вероятности $p$. Если я верно понимаю, то результат работы ГСПЧ является равномерным распределением (uniform distribution, поправьте если русский вариант термина неверный), значит вероятность появления символа должна быть
$P_{s} = \frac{1}{N}$
где $N$ - мощность алфавита

Но тогда не подходит по условию, что сумма всех вероятностей должна быть равна 1, т.к суммирование проводится по количеству выборочных значений (observations, как оно на русском?), по числу $k$ из формулы выше.

Собственно вопрос, как верно посчитать вероятность появления символа?

Вот примерный код что я накидал, но он очевидно работает неверно, в частности из-за неверного подсчета вероятности. Возможно есть еще какие-то проблемы неизвестные мне.

def pearson(s):
    alphabet_power = 27 * 2 + 10 # digits, uppercase with lowercase latin alphabet
    probability_uniform = 1.0 / alphabet_power # probability of appearence of a single byte in discrete uniform distribution
              
    observations = {}
    for i in s:
        if i in list(observations.keys()):
            observations[i] += 1.0
        else:
            observations[i] = 1.0
    
    chi_square = 0
    for i in list(observations.keys()):
        A = (observations[i] ** 2) / probability_uniform
        chi_square += A
        
    chi_square /= len(s)
    chi_square -= len(s)
    return (chi_square, len(observations.keys())) 

Вот вывод кода, примеры строк и $(V, k)$

qRJ4c - (251.0, 5)
1r3LjbA2 - (248.0, 8)
leonell - (541.5714285714286, 4)
leo mariocelli - (461.42857142857144, 9)
aaaaaaaaaaaaaaaaaaaa - (5100.0, 1)
aaaaaaa - (1785.0, 1)
hello world chi-square - (420.1818181818182, 15)
AaaA - (508.0, 2)
Programmer - (450.8, 7)
Computer - (248.0, 8)
user - (252.0, 4)
F7df7wtf7fg73rgrrg - (664.6666666666666, 9)

Первые два являются машинно сгенерированными, остальные введены руками.

Уважаемые математики, что я делаю неверно? И каким образом потом интерпретировать данные?
Спасибо.

P.S. У вас тут какой-то особенный стиль латеха что ли? Из моего редактора формулы некорректно парсятся тут без $ символа.

[martell]

Еще вопрос возник. А если у меня множество не скаляров, а векторов, или даже матриц, в общем случае тензоров $n$-го ранга. Каким образом считать? Раскладывать на компоненты? Или как? Этот вопрос тоже интересен. Или данные критерии только для скаляров?

И может есть какие-то специальные критерии (не общие наподобии кхи-квадрата) для чисто равномерного распределения?

Заранее извиняюсь, теорию вероятностей я знаю на довольно слабом уровне.

[martell]

Добрые люди подсказали, что за вероятность следует брать $P_{s} = \frac{1}{n}$ где $n$ является длиной последовательности.
UPD: Добрые люди ошиблись. Если взять строку

aaaa

, то $k = 1$, $n = 4$, в таком случае $P = \sum\limits_{s=1}^{k}P_{s} = 0.25$, а должно $P = 1$. Так что вопрос открыт. Надеюсь на помощь профессиональных математиков. А то ощущаю себя как пингвина, который мечтает летать, но он не математик.

Остался также открытым вопрос с множеством тензоров. Эта формула является общего вида, или это вывод только для скаляров? Можно ли считать, что, например, для тензора ранга $(0, 1)$ (вектора) взять просто квадрат длины (т.е скалярное произведение вектора самого на себя, следуя из формулы приведенной в головном посте) и поделить на вероятность появления такого вектора? В таком случае верно ли, что два вектора в последовательности $\boldsymbol{A_{1}} = (A;B), \boldsymbol{A_{2}} = (B;A)$ являются идентичными для критерия кхи-квадрата, что мягко говоря не соответствует действительности?

UPD2: идея появилась. Опять же на примере вектора. Что если брать сначала кхи квадрат у всех векторов сначала по компоненте $x_{1}$, потом по $x_{2}$ и тд до $x_{i}$? Если координаты вектора также подчиняются некоторому распределению, то верно ли, что можно не рассматривать сами векторы, а лишь их компоненты?

[Евгений Машеров]

По-моему, в расчёте критерия всё правильно (ну разве что chi принято кириллицей писать "хи"). Расчётная формула выглядит несколько отличной от общепринятой $\Sigma \frac {(Y_i-np_i)^2}{np_i}$, но несложными выкладками легко убедиться, что они равны. Кнутовская - позволяет суммировать только по ненулевым значениям.
Проверяется гипотеза, что байты текста выбираются случайно из набора строчных и прописных букв и цифр с равной вероятностью. Критическое значение $\chi^2$ для 63 степеней свободы (число ячеек минус единица, поскольку есть ограничение - общее количество известно, это отнимает одну степень свободы) и 5% уровне 82.53, 1% уровне 92.01.
То есть у Вас гипотеза, что все последовательности сгенерированы с равной вероятностью, отвергается во всех случаях. Однако для "компьютера" полученное значение критерия ниже.
Впрочем, у Вас слишком короткие строки, для данного числа ячеек стоило бы рассматривать строки длиной 320 байт и более (исходя из часто предлагаемого эмпирического правила - "ожидаемое число наблюдений в ячейке не менее 5 "), и использование критерия $\chi^2$ необосновано. Попробуйте сгенерировать более длинные (и куски "человеческого текста" тоже подлиннее)

[martell]

Евгений Машеров, спасибо Вам за ответ, теперь стало окончательно все понятно. В частности, то что для решения моей задачи не подходит критерий Хи-квадрата.

Если кратко, то у меня довольно практическая задача. Есть ПО для учета сотрудников. Ранее тунеядство мы ловили через обнаружение неактивности компьютера, кто-то сделал генерацию движения мышки, требуется обнаружить такое. Пример со строками был тестовый.

То есть, я хотел решить задачу так, имеем монитор $(n,m)$, где $n$ - количество пикселей по оси $X$, $m$ - по оси $Y$. Возьмем, например, монитор с разрешением $(1920,1080)$, для примера возьмем ось $X$ с 1920 пикселями.

Цитата:

исходя из часто предлагаемого эмпирического правила - "ожидаемое число наблюдений в ячейке не менее 5 "

Тогда исходя из этого правила требуется не менее $1920 \cdot 5 = 9600$ наблюдений. Частота генерации новой координаты мышки лежит обычно в промежутке между $[100, 2000]$ миллисекунд, тогда в лучшем случае при 100 мс нам потребуется 16 минут, в худшем - 5.3 часа, если промежуток генерации новых координат генерируется также случайным образом, то получим значение где-то по середине, что является совершенно недопустимым для 9-ти часового рабочего дня.

Каким образом можно было бы решить данную задачу, чтобы обнаружить случайное распределение координат при движении мышки? Буду благодарен за идеи.
Если построить, например, пространство с координатами мышки за несколько минут, то на глаз совершенно точно заметно равномерное распределение. У реальных пользователей быстро образуются кластеры, вокруг которых сосредоточена мышка, тогда как у случайной генерации координаты занимают в равном порядке практически весь экран.

Каким образом такое можно обнаружить? Не переводить же задачу в класс машинного обучения и кластерного анализа. Или проще решений нет?

Спасибо.

[Lia]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

Возвращено.

[stiv1995]

Можно разбить экран на несколько мета-пикселей (размером, скажем, 100x100) и тестировать на них. Так собственно и делают, когда применяют этот критерий к непрерывным распределениям (а в вашем случае вы фактически тестируете непрерывное равномерное). Еще можно поискать более специальные отличия людей от алгоритма --- длина скачка, направление скачка и тд. Тестирование равномерности выглядит слишком общим подходом.

Вообще если вы что-то видите глазами, то тестирование этого как правило не доставляет сложности, нужно лишь сформулировать разницу и тестировать на нее.

[stiv1995]

А еще нужно подумать, нужно ли вам вообще тестирование как таковое.

В вашей постановке, нулевая гипотеза состоит в том, что движение равномерно. Альтернатива, что нет. То есть по умолчанию вы считаете, что сотрудник нарушает правила. Так как в классической парадигме тестирования основное внимание уделяется контролю ошибки первого рода, то ваш тест будет считать, что сотрудник нарушает правила, пока не будет точно уверен в обратном (хотя, конечно, должно быть наоборот). Как минимум, нужно подумать о правильной формулировке, а уж потом о тесте.

Еще не забудьте про поправку на множественное тестирование (Бонферрони, Фишер, Бенджамини-Хофберг) -- это в вашем случае очень важно.

А вообще, я бы посоветовал не сводить задачу к именно тестированию. Просто определите разумную эвристику и ранжируйте сотрудников согласно ей. После этого анализируйте топ рейтинга глазами (в любом случае, выписывать штрафы должен человек, а не алгоритм :) )

[Евгений Машеров]

(Оффтоп)

Безотносительно математической постановки задачи - если работа сотрудников оценивается не по резултьтатам работы, а по формальному критерию, то скоро работать не будет никто. Научатся обманывать систему. А кто будет работать действительно, тот и окажется наказан - не может работник так имитировать работу, как идейный бездельник. Как только поймут, что начальство ничего не понимает в их работе (на самом деле может и понимает, но из подобных "проверок" явственно следует, что не понимает, а только проверяет, чтобы "шевелились", изображая Бурную Деятельность) так и перестанут работать.