Каков наилучший способ анализа большого набора данных с похожими записями?

Question

В настоящее время я ищу способ разработать алгоритм, который должен анализировать большой набор данных (около 600 миллионов записей).Записи имеют параметры «вызывающая сторона», «вызываемая сторона», «длительность звонка», и я хотел бы создать график взвешенных соединений между пользователями телефонов.

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

1. создать массив чисел, чтобы указать, какие записи (номер строки) уже были отсканированы.
2. начать сканирование св первой строке и для комбинации первой строки «вызывающая сторона», «вызываемая сторона» проверяют одинаковые комбинации в базе данных на сумму длительностей вызовов и делят результат на сумму всех длительностей вызовов, добавляя номера суммированных строк в созданный массивв начале
3. проверьте массив, если следующий номер записи уже суммирован, если он уже суммирован, затем пропустите запись, иначе выполните шаг 2

Буду признателен, если кто-нибудьиз вас предложили какое-либо улучшение логики, описанной выше.

ps края направлены, поэтому (вызывающая сторона, вызываемая сторона) не равна (вызываемая сторона, вызывающая сторона)

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

Answer 1

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

Ваш первый шаг должен состоять в анализе распределения (й)данных в вашем наборе данных.

В отсутствие какой-либо дополнительной информации о ваших данных я склонен предложить вам создать хеш-таблицу.Прочитайте каждую запись в вашем 600M наборе данных и вычислите хеш-адрес из объединения вызовов и вызываемых номеров.В таблицу по этому адресу напишите номера вызывающего и вызываемого абонентов (они понадобятся вам позже и имейте в виду, что хеш, вероятно, необратим), добавьте 1 к числу вызовов и добавьте продолжительность к общей продолжительности.Повторите 600M раз.

Теперь у вас есть хеш-таблица, содержащая необходимые данные.

Answer 2

Просто сортируйте записи по "вызывающей стороне", а затем по "вызываемой стороне".Таким образом, каждая уникальная пара будет иметь все вхождения в последовательных позициях.Следовательно, вы можете рассчитать вес каждой пары (вызывающая сторона, вызываемая сторона) за один проход с небольшим количеством дополнительной памяти.

Для сортировки вы можете сортировать небольшие порции по отдельности, а затем выполнять N-way-слияние,Это эффективно для памяти и может быть легко распараллелено.

Answer 3

1. Как часто вам нужно будет выполнять этот анализ? Если это большой, уникальный набор данных и, следовательно, только один или два раза - не слишком беспокоитесь о производительности, просто получите егосделано, например, как говорит Амриндер Арора, используя простые, существующие инструменты, которые вы знаете.
2. Вы действительно хотите получить больше информации о распределении , как говорит High Performance Mark.Для начала было бы полезно узнать количество уникальных телефонных номеров, количество уникальных пар телефонных номеров, а также среднее значение, отклонение и максимальное количество вызываемых / вызываемых телефонных номеров на уникальный номер телефона.
3. Вам действительно нужна дополнительная информация об анализе, который вы хотите выполнить для результата. Например, вас больше интересует целостная статистика или идентификация отдельных кластеров?Вы больше заботитесь о том, чтобы переходить по ссылкам вперед (определяя, кому Х часто звонили) или переходить по ссылкам назад (определяя, кому Х часто звонили)?Вы хотите проецировать обзоры этого графа в низкоразмерные пространства, т.е. 2d?Должно быть легко идентифицировать косвенные ссылки - например, X находится рядом с {A, B, C}, все из которых находятся рядом с Y, поэтому X является рядом с Y?

Если вы хотите быстрые и часто адаптируемые результаты,затем имейте в виду, что плотное представление с хорошей памятью и временной локализацией может легко сделать огромную разницу в производительности.В частности, это может легко перевесить фактор ln N в обозначениях big-O;Вы можете извлечь выгоду из плотного, отсортированного представления по хеш-таблице.А базы данных?Это действительно медленно.Не прикасайтесь к ним, если вообще можете этого избежать;они могут быть в 10000 раз медленнее - или больше, чем сложнее запросы, которые вы хотите выполнить для результата.

Answer 4

Поскольку существует 600 М записей, он кажется достаточно большим, чтобы использовать базу данных (и не слишком большим, чтобы требовать распределенную базу данных).Таким образом, вы можете просто загрузить это в БД (MySQL, SQLServer, Oracle и т. Д.) И выполнить следующие запросы:

выбрать call_party, named_party, sum (call_duration), avg (call_duration), min (call_duration), max (call_duration), count (*) из группы call_log по call_party, порядок Call_party на 7 дес

Это было бы начало.

Далее, вы хотели бы запустить некоторый анализ ассоциации (возможно, используя Weka), или, возможно, вы захотите проанализировать эту информацию как кубы (возможно, используя Mondrian / OLAP).Если вы расскажете нам больше, мы поможем вам больше.

С точки зрения алгоритма, то, что БД делает внутренне, похоже на то, что вы делали бы сами программно:

1. Сканирование каждой записи
2. Найдите запись для каждой комбинации (Call_party, Call_party) и обновите ее статистику.

Хорошим способом хранения и поиска записей для (Call_party, Call_party) будет использование хэш-функциии найти соответствующую запись из корзины.

Хотя может быть заманчиво создать двумерный массив для (call_party, named_party), который будет очень разреженным массивом (очень расточительным)).