2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Подсчет критерия хи-квадрата
Сообщение04.11.2019, 07:56 


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

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

Для теста пробую сделать на строках. В 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. У вас тут какой-то особенный стиль латеха что ли? Из моего редактора формулы некорректно парсятся тут без $ символа.

 Профиль  
                  
 
 Re: Подсчет критерия кхи-квадрата
Сообщение04.11.2019, 21:10 


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

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

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

 Профиль  
                  
 
 Re: Подсчет критерия кхи-квадрата
Сообщение04.11.2019, 23:15 


04/11/19
6
Добрые люди подсказали, что за вероятность следует брать $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}$? Если координаты вектора также подчиняются некоторому распределению, то верно ли, что можно не рассматривать сами векторы, а лишь их компоненты?

 Профиль  
                  
 
 Re: Подсчет критерия кхи-квадрата
Сообщение05.11.2019, 12:55 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Подсчет критерия кхи-квадрата
Сообщение07.11.2019, 01:25 


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

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

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


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

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

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

Спасибо.

 Профиль  
                  
 
 Posted automatically
Сообщение07.11.2019, 01:35 


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

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

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


Возвращено.

 Профиль  
                  
 
 Re: Подсчет критерия хи-квадрата
Сообщение08.11.2019, 18:47 


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

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

 Профиль  
                  
 
 Re: Подсчет критерия хи-квадрата
Сообщение08.11.2019, 20:36 


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

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

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

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

 Профиль  
                  
 
 Re: Подсчет критерия хи-квадрата
Сообщение08.11.2019, 20:48 
Заслуженный участник
Аватара пользователя


11/03/08
9489
Москва

(Оффтоп)

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group