Алгоритм Тойвонена в аналитике данных
В этой статье мы собираемся обсудить алгоритм Тойвонена в аналитике данных.
Алгоритм Тойвонена:
Он использует непостоянство иначе, чем простой алгоритм выборки. Этот алгоритм при наличии достаточного объема оперативной памяти будет использовать один проход для небольшой выборки и один полный проход для данных. Он не даст ни ложноотрицательных, ни положительных результатов, но есть небольшая, но конечная перспектива, что он вообще не вызовет никакого ответа. В этом случае его необходимо воспроизвести, пока он не даст ответ. В этом алгоритме до того, как он произведет среднее количество необходимых проходов, и только частые наборы элементов являются небольшой константой.
- Алгоритм Тойвонена начинается с выбора небольшой выборки входного набора данных и нахождения из нее наиболее часто встречающихся наборов элементов.
- Процедура рассматриваемого алгоритма точно такая же, как и в простом рандомизированном алгоритме, за исключением того, что в этом алгоритме важно установить порог на значение, меньшее, чем пропорциональное значение.
- То есть, если порог поддержки для полного набора данных равен s, а величина выборки - дробная часть p, то при поиске часто встречающихся наборов элементов в выборке используйте порог 0,9 пс или 0,8 пс.
- Чем меньше мы делаем порог, тем больше оперативной памяти требуется для вычисления всех наборов элементов, которые часто встречаются в выборке, но тем больше вероятность того, что мы сможем обойти ситуацию, когда алгоритм ломается, чтобы предоставить ответ.
- Собрав коллекцию частых наборов элементов для образца, мы затем настраиваем отрицательную границу. Это набор наборов элементов, которые не часто встречаются в выборке, но все их мгновенные подмножества (подмножества, созданные путем удаления ровно одного элемента) часто встречаются в выборке.
В заключение алгоритма Тойвонена мы проходим через весь набор данных, считая все наборы элементов, которые часто встречаются в выборке или находятся под отрицательной границей.
Есть два возможных последствия:
- В полном наборе данных отрицательная граница не встречается часто. В этом случае точный набор частых наборов элементов такой же, как и те наборы элементов из выборки, которые были отмечены как частые в общем.
- Часто встречаются несколько членов в полном наборе данных отрицательной границы. В этом случае мы не можем быть уверены, что не существует еще более крупных наборов, ни в отрицательной границе, ни в наборе частых наборов элементов для выборки, которые также часто встречаются в целом. Таким образом, мы не можем дать ответы в это время и должны повторить алгоритм с вновь обнаруженной случайной выборкой.
Почему работает алгоритм Тойвонена:
Очевидно, что алгоритм Тойвонена никогда не создает ложных срабатываний, поскольку он описывает как частые только те наборы элементов, которые были подсчитаны и часто встречаются в общей сумме. Чтобы утверждать, что он никогда не приводит к ложноотрицательному результату, мы должны показать, что, когда в целом не часто встречается морган отрицательной границы, тогда не может быть набора элементов, который выглядит следующим образом.
- В конце концов, он часто встречается в полном наборе предметов.
- Но ни в отрицательной границе, ни в сборе частых наборов элементов для данной выборки.
Вниманию читателя! Не переставай учиться сейчас. Ознакомьтесь со всеми важными концепциями теории CS для собеседований по SDE с помощью курса теории CS по доступной для студентов цене и будьте готовы к работе в отрасли.