введение
Эта статья начинается с рассказа о «пиве и подгузниках» и представляет общую проблему машинного обучения — предысторию применения частого поиска предметов; во-вторых, кратко представляет два наиболее часто используемых алгоритма для поиска часто встречающихся предметов — априорный алгоритм и FP-алгоритм. алгоритм роста; Затем выдвигаются некоторые предложения по взрывному увеличению числа частых элементов в высоких измерениях. Наконец, автор кратко представляет применение интеллектуального анализа частых элементов в реальной сцене Tencent Cloud, взяв многомерную хост-машину индекс в качестве примера.
1. Предпосылки
История пива и подгузников:В супермаркете люди обнаружили особенно интересное явление: два вида подгузников и пиво.НесовместимостьТовары фактически размещены вместе. Но этот странный шаг привел к значительному увеличению продаж подгузников и пива. Это не шутка, а явление, о котором всегда говорили бизнесмены.АмерикаРеальный случай сети супермаркетов Walmart. оригинальный,Америкаженщин обычно занимаются своими детьми дома, поэтому они часто просят своих мужей купить детям подгузники по дороге домой с работы, а муж вместе с подгузниками покупает свое любимое пиво. Это открытие принесло купцам большую прибыль.
Как обнаружить связь между продажами пива и подгузников в море беспорядочных данных? Чему это нас учит? Это интеллектуальный анализ данных, который анализирует правила ассоциации между данными для получения желаемых результатов.
2. Алгоритм добычи частых предметов
Алгоритм извлечения часто встречающихся наборов элементов используется для извлечения наборов элементов, которые часто появляются вместе (называемых часто встречающимися наборами элементов). рекомендуемые.
Проще говоря, учитывая список набора транзакций = {A,B,C,...}, каждая запись набора данных D является подмножеством списка, чтобы выяснить, что частое совпадение в наборе данных превышает порог t, то есть Все комбинации поддержки. Поддержка относится к количеству вхождений частого набора элементов во всем наборе данных. Как показано в таблице 1, предполагается, что набор данных содержит 100 записей, в том числе 50 записей {'перчаток'}, а его поддержка составляет 50. Конечно иногда выражается и в процентном примере, суть та же).
Таблица 1. Примеры часто встречающихся элементов
Априорный алгоритм
Существует два распространенных алгоритма добычи частых наборов элементов: один из них — алгоритм априори, а другой — алгоритм роста FP.
Алгоритм априори – это классический алгоритм поиска часто встречающихся наборов элементов. Его основная идея состоит в том, чтобы анализировать часто встречающиеся наборы элементов в два этапа: генерация набора кандидатов и обнаружение замыкания графика вниз. Априори извлекает часто встречающиеся наборы элементов, непрерывно создавая наборы-кандидаты и отбирая наборы-кандидаты, что требует повторного сканирования исходных данных. Когда исходная база данных велика, эффективность повторного чтения относительно низка, и Априори может генерировать большое количество наборов-кандидатов. что априориалгоритмдва основных недостатка.
Общий ход алгоритма:
1. Просканировать базу данных D за один проход, вычислить поддержку каждого набора из 1 элемента и получить набор частых наборов из 1 элемента.
2. Начните цикл с 2 наборов элементов и сгенерируйте частые и частые k наборов элементов из частых k-1 наборов элементов.
2.1 Этап соединения: для того, чтобы сгенерировать, предварительно сгенерировать, он получается путем выполнения операции слияния (k-2) на двух наборах частот, которые отличаются только одним элементом.
2.2 Шаг обрезки: Поскольку это надмножество, некоторые элементы могут быть нечастыми. Отбрасывать наборы элементов, подмножества которых не являются частыми наборами элементов, то есть наборы элементов, которые не входят в частые наборы элементов k-1.
2.3 Сканировать базу данных, вычислить поддержку k наборов элементов, отфильтрованных на шаге 2.3, отбросить наборы элементов, поддержка которых меньше порогового значения, и сгенерировать частые k наборов элементов.
3. Когда в текущем частом наборе k элементов есть только один набор элементов, цикл завершается.
Рисунок 1. Схематическая диаграмма алгоритма Apriori
Алгоритм роста FP
FP-рост, то есть частый рост шаблона, сжимает исходные данные через структуру данных FP-дерева, которая более эффективна. Алгоритм FPGrowth в основном делится на два этапа: построение FP-дерева и рекурсивный анализ FP-дерева. Проще говоря, априори сначала генерирует набор наборов элементов-кандидатов, а затем фильтрует нечастые наборы элементов через исходный набор данных: сначала найдите A, B, C, проверьте, проходят ли они, затем найдите AB, AC, AB и проверьте. опять.., а потом в ABC... Это подход в ширину. И fp-рост заключается в том, чтобы сначала найти частый элемент из набора данных, а затем найти другие частые элементы из набора подданных, содержащего этот частый элемент.Соединение двух должно быть частым: сначала искать A, а затем искать A содержащий A В подбазе данных, если найдено B, часто встречается AB, а затем в подбазе данных, содержащей AB, если C найдено, ABC часто.
фигура 2. Схематическая диаграмма алгоритма роста FP
nПреимущества:
1.Поскольку алгоритм роста FP должен пройти набор данных только дважды, он быстрее, чем априори..
2. Дерево FP сортирует набор в порядке убывания поддержки.Если разные пути используют одно и то же пространство хранения с одним и тем же префиксным путем, данные сжимаются.
3. Нет необходимости генерировать набор кандидатов.
nНедостатки:
1. Второй обход FP-Tree будет хранить много значений в промежуточном процессе, который будет занимать много памяти.
2. Построение FP-дерева стоит дорого.
3. Проблема размерного взрыва
Независимо от того, используется ли алгоритм роста Apriori или FP, у последних часто добытых предметов может возникнуть проблема резкого увеличения количества.Особенно, когда размерность очень велика, то есть когда количество признаков/атрибутов велико, количество частых элементов увеличивается экспоненциально, а программа также требует много времени и занимает большой объем памяти.В ответ на резкое увеличение числа частых элементов в больших измерениях автор выдвигает следующие предложения:
1. Одномерный анализ
Во время предварительного анализа порог минимального частого элемента может быть установлен выше для просмотра наиболее часто встречающихся признаков.
Если признак в определенном измерении является доминирующим, например, среди 100 событий покупок 99 событий покупок в определенном измерении относятся к одному и тому же типу, то введение этого признака в любой частый предмет не изменит характер частого предмета, то есть частый элемент по-прежнему является частым элементом. Таким образом, это измерение является необязательным для всех часто встречающихся элементов, и количество часто встречающихся элементов может быть удвоено. Таким же образом проанализируйте другие одномерные ситуации,Для определенного измерения, если подавляющее большинство относится к определенному типу, трудно проанализировать, является ли это причиной неисправности, поэтому нет необходимости вводить частую добычу предметов в этом измерении.
Примечание. Сколько раз он появляется в общем наборе транзакций как «доминирующий», что зависит от настройки минимального порога поддержки. Если добывается 500 событий, а минимальная поддержка установлена на 5, то есть равные или даже более 495 событий по определенному измерению являются определенным характерным признаком, то это измерение, очевидно, можно считать «доминирующим».
2. Корреляционный анализ
Выполните числовое преобразование показателей всех размерностей, преобразуйте их в числовые 1234 и найдите корреляцию между двумя парами показателей. Чем больше абсолютное значение коэффициента корреляции, тем сильнее кажущаяся корреляция: чем ближе коэффициент корреляции к 1 или -1,относительностьЧем сильнее корреляция, тем ближе коэффициент корреляции к 0 и тем слабее корреляция. Обычно считается, что коэффициент корреляции Пирсона выше 0,8 можно рассматривать как высококоррелированный. Для пар индексов с высокой степенью корреляции выберите один, чтобы ввести частый анализ элементов. Примечание. Пороговое значение 0,8 может различаться в зависимости от потребностей бизнеса.
Конечно, в дополнение к коэффициенту корреляции Пирсона другие показатели для измерения корреляции/сходства между атрибутами включают коэффициент Спирмена, Евклидово расстояние, манхэттенское расстояние, расстояние Минковского, сходство Жаккара и т. д.
3. Различные алгоритмы
Классический алгоритм для частого майнинга предметов — Apriori, а наиболее широко используемый — FP-growth. Алгоритм роста FP более эффективен и быстрее, чем Apriori. Кроме того, хорошим выбором является алгоритм Relim (алгоритм рекурсивного исключения Кристиана Боргельта), который также является рекурсивным поиском. При анализе наборов данных с высокой минимальной поддержкой или несколькими частыми правилами алгоритм Relim часто работает быстрее, чем алгоритм роста FP.
Алгоритм Relim — это новый алгоритм анализа частых наборов элементов, который не требует набора элементов-кандидатов на основе алгоритма роста FP. Он имеет очевидные преимущества, такие как простая структура алгоритма, высокий коэффициент использования пространства и простота реализации. Но отличие от FP-роста в том, что алгоритму Relim не нужно создавать дерево частых паттернов во время выполнения, а он находит все частые наборы элементов, устанавливая группу списка транзакций (списки транзакций).
Практика автора доказала, что алгоритм действительно быстрее алгоритма FP-роста.
4. Сопоставление строк
Сопоставление длинных строк занимает больше времени, чем сопоставление коротких строк. Следовательно, можно рассмотреть возможность замены исходных индикаторов картой формы, аналогичной A1, A2, A3, B1, B2, C1, перед извлечением частых элементов, а затем инвертировать отображение конкретных индикаторов и имен категорий при выводе результатов.
Недостатком является то, что при отладке промежуточного процесса нелегко анализировать результаты, а повышение эффективности неочевидно, поэтому, если строка не является особенно длинной, она обычно используется реже.
5. Декомпозиция данных
Один из них — кластеризация шаблонов, при котором сначала определяется хорошая мера сходства, шаблоны группируются в соответствии с этим показателем, а затем выбирается и выводится только один репрезентативный шаблон для каждого кластера. Это больше зависит от опыта экспертов и целевых требований.
Одним из них является декомпозиция базы данных, анализ часто встречающихся элементов в пакетах. Классифицировать индикаторы альтернативных измерений в соответствии с важностью и приоритетом, расставлять приоритеты по важным или приоритетным измерениям, постоянно вводить новые измерения или одновременно удалять измерения, которые больше не нужны.
6. Кэш данных
Анализ производительности программы и цели оптимизации:К концу оптимизации производительности большинство оставшихся узких мест производительности вызвано кодом, связанным с вводом-выводом.
Наиболее распространенный способ оптимизации фрагмента кода (функции) — кэширование возвращаемого функцией значения. Для некоторых данных, которые могут быть повторно использованы и имеют большой объем, может быть установлена библиотека кэша для сохранения промежуточных результатов обработки. При последующем использовании данных предпочтительно используется кеш, что может сократить затраты времени и ресурсов, вызванные промежуточными операциями обработки.
Вообще говоря, чем больше библиотека кэша данных, тем выше скорость, особенно в больших размерах, а когда много часто встречающихся элементов, улучшение скорости более очевидно. Однако чем больше библиотека кеша, тем больше памяти она занимает.Как сбалансировать эти два параметра — вопрос компромисса, зависящий от ситуации.
7. Определите потребности
При выборе параметра характеристики обратите внимание на просмотр и подумайте над вопросом: если в частом элементе фигурирует 50 параметров, как эксперты могут проанализировать все комбинации индикаторов? Человеческий глаз и мышление могут различать и анализировать измерения в одно время ограничены. Преследование многомерных частых предметов не обязательно имеет практический смысл для бизнеса.
С точки зрения спроса, одновременная добыча многомерных индикаторов может скорректировать порог минимального частого элемента, но если необходимо проанализировать взаимосвязь между индикаторами, основанную на опыте экспертов, и проанализировать возможное увеличение каждого индикатора на частоте отказов, Размер не соответствует соответствующему параметру.
В конце концов, частая добыча предметов нужна для бизнеса.Четкие цели и четкие потребности часто важнее, чем изучение того, как быстро добывать часто используемые предметы.
4. Анализ случая
Облачный бизнес Tencent:Надежность базовой IASS — важная мера качества облачных услуг. Как наиболее важная часть базовой IASS, основная машина будет напрямую влиять на вспомогательную машину клиента, когда она выйдет из строя, что приведет к значительным экономическим потерям для бизнеса клиента. Поэтому большое значение имеет анализ причин выхода из строя основной машины и снижение частоты отказов основной машины. Как выявить общие индикаторы неисправных машин с помощью часто встречающихся элементов, чтобы устранить неполадки со скрытыми машинами? Как найти скрытое бурное подводное течение под спокойной поверхностью нормального индикатора материнской машины?Немедленно локализуйте проблему и найдите проблему, в чем смысл добычи частых предметов.
1.Цель
Для накопленных заказов на работу с неисправностями главной машины реализуйте
1) Благодаря автоматическому агрегированному анализу многомерных показателей обнаруживаются общие скрытые опасности партий,
2) Путем обнаружения общих конфигураций неисправной основной машины можно точно определить основную причину высокой частоты отказов;
3) Путем обнаружения потенциальных причин частых отказов основной машины, а затем обеспечения поддержки принятия решений операторами с точки зрения приобретения, эксплуатации и отзыва оборудования, программного обеспечения и конфигурации, связанной с окружающей средой.
2. Основные шаги
Рисунок 3. Основные этапы
3. Результаты
В этом случае используется неисправность основной машины в определенном месяце определенного года, чтобы продемонстрировать частую добычу предметов.Этот случай предназначен только для справки, и используемые данные являются демонстрационными, а не реальными бизнес-данными.
1) Предварительная обработка данных: после соответствующей обработки осталось 500 рабочих заданий;
2) Частый анализ элементов: выберите «server_type», «model», «server_version», «cpu_model», «nic_model», «bios_type», «mem_pn» и другие индикаторы измерения. Минимальный порог поддержки установлен на 5, а алгоритм роста FP выбран для частой добычи предметов.
3) Анализ результатов: в результатах есть * частые элементы, и некоторые результаты показаны в таблице 2. Из первой комбинации индексов видно, что когда server_type равен s1, а модель — m1, имеется * * Отказ основной машины, согласно все той же пропорции от общего количества сконфигурированных машин, используется для расчета частоты отказов, чтобы операторы могли проводить дальнейший поиск и устранение неисправностей на основе этой комбинации показателей.
Таблица 2. Отображаются некоторые часто используемые элементы
4) Оптимизация производительности: для оптимизации производительности программы используются кэширование данных и алгоритм relim.Результаты сравнения следующие. При текущем объеме данных использование кэша данных может значительно сократить время работы программы;Использование алгоритма Relim вместо алгоритма роста FP для добычи частых предметов не кажется очевидной оптимизацией, но это преимущество будет более очевидным, когда размерность выше.После оптимизации затраты времени программы в основном связаны с чтением данных, а общее время работы конечной программы увеличилось на 21%, а использование памяти увеличилось только на 0,12 ГБ.
таблица 3. Сравнение оптимизации производительности
5) Если мы рассмотрим дальнейшее введение 30 показателей измерения в будущем. Из-за высокой размерности сначала можно выполнить одномерный анализ и корреляционный анализ. Результаты одномерного анализа показаны в таблице 4. Было обнаружено, что существует 495 рабочих заданий с номером_процессора, равным n1, который преобладает, когда минимальная поддержка равна 5, поэтому параметр номер_процессора можно исключить. Точно так же, если минимальная поддержка установлена на 500-480 = 20, размерность платформы также может считаться преобладающей над p1, а затем исключена.
Таблица 4. Одномерный анализ
Для всех показателей была проведена численная замена, и получена корреляция между двумя показателями.Показатели со статистическим коэффициентом корреляции Пирсона выше 0,8 (что можно считать высококоррелированными) представлены в таблице 5. Из таблицы видно, что коэффициенты корреляции двух пар индексов с порядковыми номерами 1 и 2 чрезвычайно высоки.Можно считать, что появление одного признака может отражать закон появления другого признака, а один из них можно зарезервировать. Коэффициенты корреляции порядковых номеров 3, 4, 5 и 6 относительно высоки, а зарезервированный индекс оказывает незначительное влияние на один из показателей. При необходимости один из показателей может быть сохранен, а распределение другого показателя может быть дополнительно проанализировано при необходимости.
Таблица 5. Корреляционный анализ
следовать за
На основе частых наборов элементов мы можем доработать правила ассоциации. С точки зрения непрофессионала, если происходит А, то, скорее всего, произойдет и Б. В сочетании с уверенностью мы можем исследовать вероятность того, что возникновение события А приведет к возникновению события В. С помощью ассоциативных правил можно обнаружить множество интересных правил, которым автор будет следовать в дальнейшем.
Вышеизложенное основано на резюме личной работы. Благодаря помощи небольших партнеров в команде эксплуатации и разработки, а также старшему @simbazhou, наставнику @lelandwu и старшей сестре @mengnizhang за их руководство и помощь.
Автор не талантлив. Если есть какая-то ошибка, добро пожаловать, чтобы исправить ее!
Ссылка на ссылку
1.blog.CSDN.net/Просто расширьте…
2.Зимние каникулы. В это время. Иллинойс. Quota/PDF/Rice 04_… (Data Mining and Knowledge Discovery)
3.blog.CSDN.net/Предоставь это своему мужу/Арити…
4.Woohoo. IBM.com/developer Я…
6.Woohoo. IBM.com/developer Я…
7. «Простота: поиск часто встречающихся наборов предметов с помощью рекурсивного исключения»
8.машинное обучение на высоком уровне. прочитайте документ s.io/this/stable/1…