На просторах великой страны нас встречает могильный покой


Previous Entry Поделиться Next Entry
ИТ: Про закон Бенфорда и Big Data
seerozha
    Тут уж буфетчик возмутился.                              
   -  Это  никому  не известно и никого не касается,  - ответил он.
   -  Ну да, неизвестно, - послышался все тот же дрянной голос
из  кабинета, - подумаешь, бином Ньютона!
Умрет он через девять месяцев, в феврале будущего года,
от рака печени в клинике пер
вого МГУ, в четвертой палате.


Михаил Булгаков, "Мастер и Маргарита"


"
В 1881 году американский математик Саймон Ньюком заметил нечто очень странное: по какой-то причине первые страницы в книгах с логарифмическими таблицами всегда истрепаны сильнее, чем последние. И дело не в том, что их никто не дочитывает до конца. Логарифмические таблицы — не обычная книга, которую положено читать по порядку. Это инструмент, значительно ускоряющий умножение и деление больших чисел. В логарифмические таблицы сводят заранее подсчитанные логарифмы множества чисел. Чтобы перемножить два числа, достаточно отыскать в таблице соответствующие им логарифмы, сложить их, а затем определить по той же таблице, какому результату соответствует сумма. Это гораздо проще и быстрее, чем умножение столбиком, которому учат в школе.

В начале логарифмической таблицы перечислены логарифмы чисел с единицей в старшем разряде, затем идут логарифмы чисел, начинающихся с двойки, и так далее до девяти. Если в начале книга истрепана сильнее, чем в конце, значит, множители, которые начинаются с единицы, нужны людям чаще, чем числа, начинающиеся с цифры два, не говоря уж о девяти. Ньюком предположил, что чем меньше значение старшего разряда числа, тем чаще оно встречается. Согласно формуле, которую вывел ученый, вероятность столкнуться с числом с единицей в начале составляет около 30%. Вероятность снижается с каждой цифрой, пока не достигает 4,6% — это значение соответствует девятке.

Здравый смысл протестует против этой идеи, но с фактами не поспоришь. В 1938 году физик Фрэнк Бенфорд, независимо наткнувшийся на ту же закономерность, протестировал справедливость своих выводов на десятках тысяч измерений. Он подсчитал вероятность, с которой разные цифры встречаются в старшем разряде десятков физических констант. Результаты совпали с предсказаниями формулы. Площади бассейнов рек? Молекулярный вес сотен химических веществ? Численность населения случайно отобранных населенных пунктов? Курсы акций на бирже? Бенфорд проверял один набор данных за другим, но не мог найти ошибки. Распределение цифр в старшем разряде подчинялось закону, который сегодня носит его имя, — закону Бенфорда.

В начале семидесятых экономист Хэл Вэриан предложил использовать закон Бенфорда для того, чтобы отличать фальсифицированные данные от подлинных. Значения, взятые с потолка, могут выглядеть очень правдоподобно, но они не выдерживают проверки законом Бенфорда. К концу двадцатого века этот метод взяла на вооружение судебная бухгалтерия. Там проверяют, укладываются ли цифры в финансовой отчетности в нужное распределение. Если закон Бенфорда не соблюден, значит, финансовые показатели кто-то подправил.

Закон Бенфорда с легкостью отыскивает следы человеческого вмешательства в естественный порядок. Нужно ли объяснять, насколько это ценное качество для поиска аномалий в данных? Алгоритм, построенный таким образом, прост и эффективен. Правда, он не годится для анализа данных, которые заведомо неестественны. Это ограничение, но у кого их нет?

Красивый пример использования закона Бенфорда для выявления обмана дает недавняя работа Дженнифер Голбек, известной специалистки в области анализа социальных сетей. Она показала, что с его помощью можно выводить на чистую воду ботов — поддельные учетные записи в Facebook или Twitter. Голбек начала с изучения наборов данных о подмножествах пользователей пяти крупных социальных сетей: Facebook, Twitter, Google+, Pinterest и LiveJournal. В большинстве случаев данные о пользователях извлекались при помощи программного интерфейса соответствующей соцсети. Исключение составляли Google+ и LiveJournal. Информация об их пользователях была позаимствована в Stanford Network Analysis Project.

Для начала исследовательница проверила количество связей между аккаунтами в каждой соцсети. Как и ожидалось, эти значения совпали с показателями, которые предсказаны законом Бенфорда. Исключение составляет Pinterest: при создании аккаунта сервис добавляет пять связей автоматически, и это портит всю статистику.

Затем Голбек занялась анализом отдельных учетных записей. Она отобрала те из них, которые насчитывают по меньшей мере сто социальных связей. Оказалось, что распределение первых значащих цифр количества «друзей» у аккаунтов, к которым ведут эти связи, почти всегда укладывается в закон Бенфорда. Например, в наборе данных Twitter существенное отклонение наблюдалось лишь в 1% случаев.

И что же это за процент? Голбек проверила 170 аккаунтов Twitter, не подчиняющихся закону Бенфорда, и обнаружила, что лишь два из них не вызывают подозрений. Подавляющее большинство остальных оказались русскими ботами. Эти аккаунты очень похожи друг на друга: фотография пользователя явно позаимствована из фотобанка, сами твиты — бессмысленные обрывки книжных цитат, друзья — другие боты. Они маскируются под обычных людей, но закон Бенфорда легко выявляет их искусственность.
"

Отсюда

  • 1

ИТ: Про закон Бенфорда и Big Data

Пользователь ansari75 сослался на вашу запись в своей записи «ИТ: Про закон Бенфорда и Big Data» в контексте: [...] Оригинал взят у в ИТ: Про закон Бенфорда и Big Data [...]

  • 1
?

Log in

No account? Create an account