|
того, следует запомнить и поддержку набора, которая пригодится при извлечении правил. Эти же действия применяются для нахождения (£+1 )-элементных наборов и т. д. 3.3.2. Разновидности алгоритма Apriori Алгоритм AprioriTid является разновидностью алгоритма Apriori. Отличительной чертой данного алгоритма является подсчет значения поддержки кандидатов не при сканировании множества D а с помощью множества Q, являющегося множеством кандидатов (^-элементных наборов) потенциально частых, в соответствие которым ставится идентификатор TID транзакций, в которых они содержатся. Каждый член множества С к является парой вида Множество С\ = D соответствует множеству транзакций, хотя каждый объект в транзакции соответствует одно-объектному набору в множестве С\, содержащем этот объект. Для к > I множество Q генерируется в соответствии с алгоритмом, описанным ниже. Член множества Q, соответствующий транзакции Т, является парой следующего вида: Подмножество наборов в Q с одинаковыми TID (т. е. содержатся в одной и той же транзакции) называется записью. Если транзакция не содержит ни одного ^-элементного кандидата, то Q не будет иметь записи для этой транзакции. То есть количество записей в С/, может быть меньше, чем в D особенно для больших значений к. Кроме того, для больших значений к каждая запись может быть меньше, чем соответствующая ей транзакция, т. к. в транзакции будет содержаться мало кандидатов. Однако для малых значений к каждая запись может быть больше, чем 94 |
Если ( 1−∉ kLs ) то Удалить c из kC Шаг 6. Для каждого кандидата из множества kC увеличить значение поддержки на единицу. Шаг 7. Выбрать только кандидатов kL из множества kC , у которых значение поддержки больше заданной пользователем minSupp . Вернуться к шагу 2. Результатом работы алгоритма является объединение всех множеств kL для всех k . Разновидности алгоритма Apriori. Алгоритм AprioriTid является разновидностью алгоритма Apriori. Отличительной чертой данного алгоритма является подсчет значения поддержки кандидатов не при сканировании множества D , а с помощью множества kC , являющегося множеством кандидатов (k-элементных наборов) потенциально частых, в соответствие которым ставятся идентификатор TID транзакций, в которых они содержатся. Каждый член множества kC является парой >< }{, kFTID , где ка-ждый kF является потенциально частым kэлементным набором, представленным в транзакции с идентификатором TID . Множество DC =1 соответствует множеству транзакций, хотя каждый объект в транзакции соответствует однообъектному набору в множестве 1C , содержащем этот объект. Для 1>k множество kC генерируется в соответствии с алгоритмом, описанным ниже. Член множества kC , соответствующий транзакции T , является парой следующего вида: >∈∈< }{,. TcCcTIDT k . Подмножество наборов в kC с одинаковыми TID (т.е. содержатся в одной и той же транзакции) называется записью. Если транзакция не содержит ни одного k-элементного кандидата, то kC не будет иметь записи для этой транзакции, т.е. количество записей в kC может быть меньше, чем в D , особенно для больших значений k . Кроме того, для больших значений k каждая запись может быть больше, чем соответствующая ей транзакция, так как в транзакции будет содержаться мало кандидатов. Однако для малых значений k каждая запись может быть больше, чем соответствующая транзакция, так как kC включает всех кандидатов k-элементных наборов, содержащихся в транзакции. Другой разновидностью алгоритма Apriori является алгоритм MSAP (Mining Sequential Alarm Patterns), специально разработанный для выполнения сиквенкциального анализа сбоев телекоммуникационной сети. Он использует следующее свойство поддержки последовательностей: для любой последовательности kL ее поддержка будет меньше, чем поддержка последовательностей из множества 1−kL . Алгоритм MSAP для поиска событий, следующих друг за другом, использует понятие «срочного окна». Это позволяет выявлять не просто одинаковые последовательности событий, а следующие друг за другом. В остальном данный алгоритм работает по тому же принципу, что и Apriori. 1.7. КЛАСТЕРИЗАЦИЯ Постановка задачи кластеризации. Первые публикации по кластерному анализу появились в конце 30-х прошлого столетия, но активное развитие этих методов и их широкое использование началось в конце 60-х – начале 70-х годов [11]. В дальнейшем это направление анализа интенсивно развивалось. Появились новые методы, модификации уже известных алгоритмов, существенно расширилась область применения кластерного анализа. Если первоначально эти методы использовались в психологии, археологии, биологии, то сейчас они стали активно применяться в социологии, экономике, статистике, в исторических исследованиях. Кластеризация отличается от классификации тем, что для проведения анализа не требуется иметь выделенную целевую переменную, с этой точки зрения она относится к классу задач с обучением без учителя. Эта задача решается на начальных этапах исследования, когда о данных мало что известно. Ее решение помогает лучше понять данные, и с этой точки зрения задача кластеризации является описательной задачей. Для этапа кластеризации характерно отсутствие каких-либо различий как между переменными, так и между записями. Напротив, ищутся группы наиболее близких, похожих записей. Методы автоматического разбиения на кластеры редко используются сами по себе, просто для получения групп схожих объектов. Анализ только начинается с разбиения на кластеры. После определения кластеров используются другие методы ИА для того, чтобы попытаться установить, а что означает такое разбиение на кластеры, чем оно вызвано. Большое достоинство кластерного анализа в том, что он позволяет производить разбиение объектов не по одному параметру, а по целому набору признаков. Кроме того, кластерный анализ, в отличие от большинства математико-статистических методов, не накладывает никаких ограничений на вид рассматриваемых объектов и позволяет рассматривать множество исходных данных практически произвольной природы. Это имеет большое значение, например, для прогнозирования конъюнктуры при наличии разнородных показателей, затрудняющих применение традиционных экономических подходов. Кластерный анализ позволяет рассматривать достаточно большой объем информации и резко сокращать, сжимать большие массивы информации, делать их компактными и наглядными. Задача кластеризации состоит в разделении исследуемого множества объектов на группы «похожих» объектов, называемых кластерами. Один из способов решения задачи кластеризации – построение набора характеристических функций классов, которые показывают, относится ли объект данных к данному классу или нет. Характеристическая функция класса может быть двух типов: |