Если вы никогда не задумывались об алгоритме предсказания номеров лотереи или лиги фэнтези-футбола, то это будет скучно. Но если вы фанат секретной науки о данных, то присоединяйтесь ко мне в эпической пятерке!
Мы только что завершили кодирование инструмента кластерного анализа данных: соревнование длилось 90 минут, мы закончили менее чем за час.
Проблемное пространство обычно составляет O (n³) и похоже на вашу классическую задачу коммивояжера.
У нашего клиента Слалом возникла проблема с данными и стоимостью.
Проблема с данными
Возьмите имя, адрес и другую личную информацию, чтобы объединить информацию из различных источников. Я пишу это в спешке, поэтому не буду раскрывать какие-либо специфические для клиента детали или фактическую реализацию, которая сейчас принадлежит клиенту, но аналогичное проблемное пространство может быть генеалогическим.
Затем дано: у вас есть записи о смерти, записи о браке, записи о рождении, записи переписи населения из разных источников в разное время и с разным написанием. Вы не хотите дублировать данные. Вы не хотите терять данные. Итак, вам нужно сформировать кластер. Кластер - это то, как вы определяете, что перепись 1890 года Джимми Джоосафата на 10-Бэнд-стрит совпадает с переписью 1880-го Джеймса Джохосафата на 10-Бонд-стрит.
Я уверен, вы можете придумать, как это сделать для одного человека, но как вы масштабируете эту проблему до миллионов, не убивая свой сервер?
Проблема стоимости
Стоимость была проблемой для клиента. Они тратили шестизначные суммы в год на лицензирование предприятий. Естественно, я предполагаю, что они потратят сэкономленные деньги на покупку фонтана, подключенного к бесконечному запасу энергетических напитков Monster.
Инструменты
Microsoft SQL Server 2012 и SSIS. Иногда приходится работать с тем, что у вас есть. ;)
Решение
Мы использовали функции подобия SQL Server Master Data Management (MDM) и SSIS, чтобы найти сходство между всеми записями.
У Люка есть отец.
У Люка есть сестра.
Сын Вейдера - Люк.
Отец Лии - Вейдер.
Брата Лии зовут Люк.
Чубакка - вуки
Мы сохранили эти сходства в таблице.
Затем мы запустили хранимую процедуру для консолидации всех ассоциативных и транзитивных ассоциаций до единственного родителя.
Кластер Люка Скайуокера: Люк, Лия, Вейдер
Кластер вуки: Чубакка
Мы сделали это. Пришли, увидели, надрали ему задницу!
Присоединяйтесь к команде решений для слалома
Команда управления данными (MDM)
Наши суперзвезды Vaibhav Sathe и Soumen Chakraborty - с точки зрения личности это были Уинстон (Эрни Хадсон) и Рэй (Дэн Эйкройд) - эти двое потратили несколько недель на построение правил и нечеткий анализ для сравнения данных и определения возможного кластера. отношения. Некоторое время я работал с Суменом, поэтому я набираю форму Эйкройда, но мы с Вайбхавом работали вместе с другим клиентом над аналогичной проблемой. Обычно он тихий и собранный, но я могу представить, как он кричит: Я люблю этот город! после победы над гигантским зефирным человечком.
Руководитель нашей практики управления данными Тедди Вэй - это сила, с которой нужно считаться. Его левое остроумие в равной степени сочетается с его преданностью команде и клиенту. Он заботится. По характеру он определенно Венкман (Билл Мюррей).
Также выручил на уровне MS SQL Server Гуру Кевин Фейт. Я сохраняю последний Охотник за привидениями для себя, так что мне придется дать Кевину неверное представление о Рике Моранисе… Извини, Кевин, я пишу статью. ;) Хотя интеллектуально он и является Эгоном, он знает сервер MSSQL и T-SQL, как Нео знает кунг-фу.
Команда разработки приложений (мы слишком хорошо разбираемся в аббревиатурах)
Под «мы» я подразумеваю себя. Я помогал в этом проекте чуть больше недели. Моя работа и та часть, которой я особенно горжусь, заключалась в написании хранимой процедуры для подключения всех связанных кластеров к единственному родительскому элементу с помощью операций на основе наборов.
Вы представляли себе курсор SQL Server? Нет, я сделал это с помощью операций на основе наборов . Гоша! ;)
В наших последних тестах моя операция на основе набора занимала 13% времени подхода на основе курсора. Я Эгон (Гарольд Рамис). К тому же мои волосы растут, как у Эгона, когда я слишком долго не остаюсь без стрижки.
Табло, гонка на скорость
Самая захватывающая часть этого проекта для меня вернулась в июне, когда Вайбхав (Уинстон) обратился ко мне. У них были проблемы с производительностью их последней хранимой процедуры кластеризации, которая просматривает все отношения между точками данных и создает по одному родительскому элементу для каждого кластера.
Они использовали один подход, на выполнение которого уходило шесть часов. Клиенту требовалось решение, которое было разработано менее чем за два часа. И это была лишь небольшая выборка тестовых данных. Если бы мы не смогли потратить два часа на непрерывный анализ, проект провалился бы.
Если шесть часов кажутся чрезмерными, вот в чем проблема.
У вас есть таблица с 40 000 связей.
Все ассоциативные отношения "многие ко многим".
(A == B, B == A, B == C)
Описан только один уровень отношений. Вы должны самостоятельно выяснить транзитивные отношения.
(если A == B и B == C, то A == C)
Поступая так сложным образом, вы должны сначала взглянуть на запись 1 и увидеть, кто связан с записью 1. Затем для тех записей, которые связаны с записью 1, вам нужно увидеть, связаны ли эти записи с какими-либо другими записями, и пометить их как связанные. до 1. Затем продолжайте, пока вы больше не сможете идти. Затем перейдите к записи 2.
Без помощи каких-либо индексов SQL Server должен будет выполнить 40 000! читает. Мне не удалось найти калькулятор для вычисления такого большого факториала.
Это рекурсивная проблема. Вот почему 40 000 отношений заняли шесть часов.
40 000! = навсегда
Затем алгоритм был оптимизирован, чтобы максимально использовать индексы. Что это дает вам сейчас? Теперь вы делаете факториалы на меньшем уровне. Если средняя глубина кластера составляет 6 узлов, превратите это значение в 6 !, что превратится в 6 * 5 * 4 * 3 * 2 * 1, что равно 720. Итак, если вы получите 1700 конечных кластеров, тогда вы получите это оптимальное количество.
6! * 1700 = 1224000 записей для чтения
Итак, ваш лучший сценарий состоит в том, что SQL Server не нужно будет просматривать более 1,2 миллиона строк для этого небольшого размера выборки.
Благодаря оптимизации индекса мы сократили время до 15 минут.
Однако размер этой выборки был на 3% меньше того, с чем столкнется производство. Решение все равно не выдержит масштабирования.
Я преобразовал алгоритм в операцию, основанную на наборах.
С помощью операций на основе наборов мы сократили время до 2 минут.
Это было потрясающе! Когда мы приступили к производству, эта хранимая процедура смогла проанализировать 1,19 миллиона отношений и вернуть уникальные идентифицированные кластеры для каждого дерева отношений менее чем за десять минут.
Конечный результат: для полумиллиона записей потребовалось 40 минут на определение всех взаимосвязей и 10 минут на консолидацию и идентификацию всех кластеров.
Это похоже на то, как если бы вы смотрели на всех студентов колледжа и выясняли, кто с кем спал, чтобы выяснить, у кого из студентов сейчас герпес. Ладно, может быть, это была немного чопорная метафора - но проблемное пространство того же типа. ;)
Пожелания и извлеченные уроки
Если бы у меня было больше времени, я бы с удовольствием переписал шаги нечеткого анализа. Посмотрим, смогу ли я изобрести способ индексирования записей в SQL для оценок Левенштейна и Яро-Винклера. Я приблизился к этому, используя ElasticSearch в другом проекте. В целом, я хотел бы попытаться как можно ближе подойти к O (n) log (n).
Я также повторно узнал, что когда вы начинаете работать с миллионами в SQL Server, планировщик выполнения запросов не заботится об индексах с составными столбцами. Он может подумать, что сканирование таблицы лучше, чем попытка точно выровнять два индекса, особенно если столбцы не уникальны. При работе с миллионами проиндексируйте один столбец и включите остальные.
Модульные тесты сэкономили много времени и избавили от головной боли в этой работе. Каждый раз, когда я обнаруживал новую ошибку в хранимой процедуре, которую я писал, я писал для нее новый модульный тест. Модульный тест не был сложным или чем-то подобным, это был всего лишь один файл T-SQL. Производственные записи будут выгружены во временную таблицу. Вставьте тестовые начальные данные в таблицу отношений. Затем запустите хранимую процедуру кластеризации и используйте операторы IF EXISTS (SELECT…) и RAISERROR, чтобы сообщить, если какие-либо ожидания не оправдались. В конце он удалял тестовые начальные данные и возвращал производственные записи в таблицу.
Работа архитектора никогда не заканчивается. Вот почему фараоны хоронили их вместе со своими делами. Чтобы заткнуть им рот.
Эта игра для Android (Osmos) вдохновила меня на решение этой проблемы.
Если вам понравилась эта статья, проявите немного любви и нажмите сердце слева, чтобы порекомендовать ее.
Подпишитесь на меня на Medium, чтобы получить материалы, наполненные энтузиазмом и бездушным убер-ботаником.
Я также в Твиттере и Инстаграм.
Хакерский полдень - это то, с чего хакеры начинают свои дни. Мы часть семьи @AMI. Сейчас мы принимаем заявки и рады обсуждать рекламные и спонсорские возможности.
Если вам понравился этот рассказ, мы рекомендуем прочитать наши Последние технические истории и Современные технические истории. До следующего раза не воспринимайте реалии мира как должное!
