Диссертация. Основам искусственного интеллекта и анализа данных в курсе информатики на уровне среднего общего образования Научная
 Скачать 4.76 Mb.
|
|
k-Nearest Neighbors или же k-NN). Он является довольно простым для освоения и всё же распространённым [188]. Как метод классификации, этот алгоритм обладает всеми описанными выше свойствами. Его суть сводится к сравнению с метками классов объектов, находящихся рядом, — проверяется k соседей (с наименьшим расстоянием по сравнению с остальными объектами обучающей выборки, затем объекту присваивается самая часто встречающаяся среди известных объектов метка [20]. Рассмотрим схематичный пример (см. Рис. 17). Допустим, у насесть два класса (красные и синие) и новый объекта число рассматриваемых соседей k = 6. Рис. 17. Метод k ближайших соседей Из шести ближайших соседей пять оказались с синей меткой, поэтому новый объект тоже получает синюю метку. Метод k ближайших соседей принимает решение на основе только известных меток. Здесь никак не возникнет фиолетовая метка, ведьмы условились, что тождественные 120 объекты будут тождественны полностью, те. и цвет метки для них будет одинаковым – либо только синим, либо только красным в зависимости от количества ближайших соседей определённого цвета. В более сложном варианте дальность до каждого из k соседей учитывается в виде веса – специального коэффициента близости [158]. Затем следует в качестве закрепляющего этапа предложить выписать характеристики изученного алгоритма в соответствии с известной классификацией. Итак, k-NN: • алгоритм обучения с учителем • при работе сохраняет исходные данные неизменными • неитеративный, так как за один проход присваивает метки классов объектам контрольной выборки • немасштабируемый, что следует из предыдущих двух пунктов. Также рассмотрим область применения классификации методом ближайших соседей Например, она применяется для продвижения товара при таргетировании: по возрасту, полу, уровню дохода и другим признакам, выделением которых как значащих занимается специалист, понимающий специфику изучаемой области. Этот метод используется также в банковских системах и при поиске групп платёжеспособных клиентов. Классификация встречается ив добыче (mining) знаний. Когда работа сводится к оперированию лишь типичными случаями и взаимодействию с представителями множеств, говорят о рассуждении по аналогии. Поскольку рассуждение по аналогии характерно для кластеризации, которая также иначе называется автоматической классификацией, отсюда вытекает выбор следующей подтемы. Тема КЛАСТЕРИЗАЦИЯ. МЕТОД ДИНАМИЧЕСКИХ ЯДЕР Мы переходим к следующей большой категории задач, предусматривающих обучение без учителя (Unsupervised learning) [18]. Если раньше мы на вход классификаторов подавали обучающую выборку 121 вместе с ответами, то здесь от нас требуется дать модели только сами данные без описанных ответов и зависимостей. В некоторых, более сложных, случаях мы не будем даже упоминать количественные характеристики. Кластеризация (сегментация) – это задача автоматической бесконтрольной) классификации [154]. Её название происходит от англ. cluster – скопление или гроздь, в данном случае – группа объектов. Обычно количество кластеров указывается в параметрах, но может быть выбрано автоматически на основе статистических критериев оценки качества работы алгоритма в итеративном формате. На вход подаётся только контрольная выборка, состоящая из описанных объектов — векторов с d значениями- свойствами. Классификатор кластеризации сам выявляет характеристики конкретных классов, к которым затем относит объекты. Объекты из разных кластеров отличаются, внутри одного кластера — максимально похожи. Это основное правило кластеризации. Обобщая сказанное, кластеризация — это автоматическая классификация без предоставления образца распределения, те. без известных свойств классов (кластеров. Для обозначения решения задач кластеризации также используют термины кластерный анализ (Cluster Analysis) или Data Clustering [51]. Впервые термин кластерный анализ в 1939 году ввёл и описал Роберт Трион. Большой обзор исследований различной направленности, проводимых с помощью кластерного анализа, в 1975 году дал Джон Хартиган. Сегодня к данной области Data Mining относят более ста методов. Существует сложность в подсчёте точного числа алгоритмов, поскольку в разных сферах одни и те же алгоритмы известны под разными названиями. Кластеризацию изначально применяли в основном в социологии, затем область применения была расширена. Большое значение кластерный 122 анализ имеет для изучения совокупностей временных рядов, характеризующих экономическое развитие. Изучение поведения кластеров, к которым принадлежат исследуемые объекты, позволяет выявить закономерности. Также динамическое изменение состояния кластеров даёт возможность выделять периоды схожести некоторых показателей и интересные эффекты и реакции. Именно поэтому кластеризация широко применяется в исследовании поведения групп людей, объединённых рядом каких-либо признаков (и для выявления этих признаков в том числе, в науках, ориентированных на изучение человека и его культуры. Сразу же рассмотрим несколько понятий, которыми мы будем оперировать. Кластер – это непересекающееся непустое подмножество максимально похожих объектов, отличных от объектов других групп [48]. Существуют алгоритмы, где рассматриваются пересекающиеся кластеры, но тогда отношение принадлежности объекта к кластеру выражается как вероятность (в процентах. Кластер обладает следующими характеристиками [20]: • центр кластера состояние кластера) – среднее геометрическое место точек (объектов) кластера в пространстве переменных. Если при работе алгоритма создаётся новый временный объект, то он называется центроид. Если же рассматривается объект, наиболее приближенный к найденному математически центру кластера, то используется название кластероид; • радиус кластера – это максимальное расстояние объектов данного кластера от его центра • среднеквадратическое отклонение объектов кластера. Среднеквадратическое отклонение позволяет определить качество разбиения на кластеры и наиболее оптимальное количество кластеров в будущем. Рассматривается на стадии проверки качества 123 • размер кластера, определяемый по радиусу кластера или его среднеквадратическому отклонению. Размер кластера равен мощности множества объектов, входящих в кластер, – количеству элементов в рассматриваемой группе • плотность кластера – свойство, показывающее, насколько кластер заполнен или напротив — достаточно разрежен. Наиболее распространённый способ решения задачи кластеризации – исследование дисперсии расстояния от центра кластера до отдельных точек в нм. Чем меньше дисперсия расстояния, тем выше плотность кластера. Вы можете представить группы людей на экскурсии. Чем ближе люди к экскурсоводу (своему центру, тем плотнее их группа выглядит со стороны. Групп может быть несколько. Допустим, людей попросили самостоятельно разбиться на подгруппы. Как вы определите, кто к какой группе относится Вы посмотрите, к какому экскурсоводу (центру кластера, выбранному из его объектов, — кластероиду) человек (объект кластера) стоит ближе минимальное расстояние. При кластеризации объектов обычно роль экскурсовода не прикреплена к определённому объекту – кластероид переопределяется на каждой итерации алгоритма, пока не устоится. Если мы смотрели бы не на экскурсовода, а в геометрический центр группы, то точка, куда упал наш взгляд, была бы центроидом — мнимым объектом, не принадлежащим группе. Если объект оказывается принадлежащим сразу нескольким кластерам, то его называют спорным. Для разрешения данной ситуации требуется вмешательство специалиста, и вхождение объекта в какой-либо кластер определяется уже по смыслу. Формальная запись задачи кластеризации выглядит следующим образом [158]. Пусть 124 X – множество всех объектов, причём на X задана функция расстояния – множество всех кластеров – множество меток (номеров) кластеров — конечная выборка. Требуется разбить данную выборку X на непересекающиеся подмножества, принадлежащие кластеру C те, таким образом, чтобы каждый кластер состоял из объектов, близких по метрике d (чтобы между ними было минимальное расстояние, а объекты разных кластеров существенно отличались (находились на большем расстоянии, большем чем расстояние до объектов того же кластера. Каждому объекту ставится в соответствие метка кластера Запишем последнее утверждение на формальном языке. Отображение (функция) , , называется алгоритмом кластеризации. Количество меток обычно задаётся исследователем как число k, однако не всегда можно интуитивно определить, является ли такое разбиение оптимальным. Отсюда возникает задача поиска оптимального числа k относительно одного из критериев качества кластеризации (например, с помощью метода локтя (elbow method) или проверки индекса силуэта (Silhouette Index)) [133]. Кластеризацию применяют с целью • выявления кластерной структуры для понимания данных, это необходимо для формулирования критериев (диапазонов значений свойств) описания классов (из полученных кластеров и их типичных представителей – центроидов или кластероидов) и разворачивания на основе множества 125 классов таксономии, те. описания правил классификации всех объектов и их отношений • обнаружения новизны (novelty detection) – выявления нетипичных объектов, не принадлежащих ни одному кластеру • сжатия данных путём сокращения выборки и сохранения от каждого кластера только кластероида. Данные могут сжиматься не только ради сокращения места, но и для удобства оперирования ими или создания образа типичного представителя. Работа с типичным представителем, а не совсем множеством, входит в методы рассуждения по аналогии (Case Based Reasoning, CBR). Считается, что правила, действующие на этого представителя, будут с некоторой вероятностью распространяться на остальных представителей кластера. Методы CBR позволяют добиться повышения этого коэффициента вероятности. Отметим, что разбиение данных на группы также позволяет более эффективно обрабатывать данные внутри групп, применяя разные методы анализа внутри каждого полученного кластера (согласно стратегии разделяй и властвуй. Большая гроздь объектов делится на маленькие грозди, внутри который продолжается поиск. Например, мы можем итеративно оставлять только кластероиды и наследующем этапе искать дополнительную информацию уже в выборке, состоящей только из них. Здесь, однако, возникает проблема искажения значащих свойств. Часто кластеризация применяется для задач распознавания образов на растровых изображениях (включая кадры видеосъёмки) путём объединения в объекты смежных пикселей, например, близких цветов. Итоги • методы кластеризации относятся к описательным • число кластеров обычно устанавливается субъективно экспертом (человеком 126 • методы кластеризации относятся к классу задач обучения без учителя. Мы рассмотрим самый распространённый алгоритм кластеризации – метод динамических ядер, который часто называют методом средних (k-means). Данный метод был изобретён в х годах, но стал популярным лишь в 1967 году после публикации обзора некоторых алгоритмов классификации и кластеризации многомерных данных. Как ив случае со многими инженерными изобретениям, идея алгоритма независимо пришла к нескольким ученым, но оказалась оценена по достоинству только после того, как была продемонстрирована её практическая польза. • Классическая версия метода предусматривает, что [48]: • разбиение на первом шаге – случайное • число кластеров k задаётся экспертом • любой объект может принадлежать только одному кластеру, расстояние до центра которого от объекта минимально. • Задача алгоритма заключается в минимизации сумм квадратов расстояний от каждой точки кластера до его центра (см. Рис. 18). Кроме того, на кластеры накладываются следующие условия 1) кластеры являются непересекающимися множествами 2) каждый элемент выборки обязательно принадлежит одному (и только одному) кластеру. Рис. 18. Работа алгоритма динамических ядер 127 На вход алгоритм получает n векторов размерности d (n объектов с описанными d свойствами в нормализованном формате) и мощность множества . То есть количество всех кластеров равно k. Алгоритм состоит из четырёх шагов. Шаги 2–3 составляют вычислительное ядро алгоритма. 1. Инициализация кластеров. Пусть – произвольное множество различных объектов (точек, рассматриваемых как начальные центры кластеров 𝐶 ∗ = {𝑐 1 ∗ , … , 𝑐 𝑘 ∗ }. Существует несколько стратегий выбора начальных точек. Их может выбрать и сам исследователь, например, как k случайных объектов из всей выборки. 2. Распределение имеющихся объектов по кластерам в момент времени (на итерации) t: Эта формула означает, что объекту присваивается метка того кластера, квадрат расстояния до центра которого оказался наименьшим. 3. Пересчёт центров кластеров в момент времени итерации) t: Новый центр находится как центральная точка для кластера, те. точка, расстояние до которой от остальных представителей кластера минимально. Такие центры надо найти у всех кластеров. 128 4. Проверка условия останова если , то продолжать, иначе – остановить выполнение, те. остановить, когда центры перестанут меняться. Этот шаг отображает сходимость алгоритма, достигаемую за конечное число итераций. Подведём итоги. Метод k-means: • относится к алгоритмам, использующим вероятностный подход данный подход строится на предположении, что каждый объект выборки относится строго к одному из k классов • неиерархический метод, поскольку не рассматривает случаи кластеров, вложенных друг в друга • при работе сохраняет исходные данные неизменными • итеративный, так как выполняет итерации, пока центры кластеров не устоятся • немасштабируемый, поскольку на каждой итерации проверяет все объекты. Конечно, у алгоритмов кластеризации, как и у других интеллектуальных алгоритмов, существуют свои особенности и проблемы. Например, на результат влияет правильность выбора начальных центров, числа кластеров и даже функции расстояния (выбор метрики. Тема АССОЦИАЦИИ. АНАЛИЗ ПОТРЕБИТЕЛЬСКИХ КОРЗИН. Если у насесть большая база данных событий – например, покупок, нам может быть интересно выявить ассоциации – то есть связанные события. Например – выяснить, какие товары покупают вместе Или какие страницы просматривает пользователь, попадающий к нам на сайт Чаще всего поиск ассоциаций встречается в розничной торговле, маркетинге, исследовании пользовательского поведения, в рекомендательных сервисах и т. дно иногда встречается ив робототехнике. 129 Пример с покупками приводится неслучайно. Раздел поиска ассоциативных правил (association rule mining) начался с вопроса, а как же поступают клиенты магазинов и есть ли среди их действий шаблоны поведения, которые продавцы могут использовать для составления акций, расположения товаров ив конечном счете, увеличения своих продаж. Исследователям предстояло заглянуть в продуктовые корзины – заняться их анализом (market basket analysis). Очевидно, что массивы данных для такого анализа большие (это, например, все чеки торговой сети за год, и выполнить его вручную – невозможно. Благодаря такой формулировке, первые термины, применяемые в этой области, закрепились и при применении алгоритмов в совершенно других сферах. Итак, для работы с ассоциативными правилами вам потребуется следующий словарь [45]: • множество товаров, корзина (item set) – все различные наименования, которые могут встретиться при анализе, например, ассортимент магазина или перечень исследуемых полезных значимых) свойств (features); • товар (item) – конкретный вид товара, наименование или исследуемое свойство имеет свой личный код в базе данных (ID); • рыночная корзина (market basket) – корзина покупок конкретного покупателя, которую он оплачивает в рамках отдельной транзакции • транзакция (transaction) – чек покупателя множество одновременно произошедших событий в технической документации под транзакцией также понимают входную запись, явно или неявно требующую обработки транзакция всегда обладает уникальным идентификатором (TID); 130 • множество транзакций (transaction set) – данные обо всех купленных товарах в магазине и их количестве, сводные данные всех чеков иначе называется операционной базой данных • поддержка (support) – встречаемость конкретного наименования или сочетания нескольких наименований среди всех транзакций обычно выражается в процентах • минимальная поддержка (min. support) – минимальный порог встречаемости, задаваемый исследователем • ассоциативное правило (association rule) − правило отношения к чему-либо, используемое для группировки данных, которые проще всего записать конструкцией если, то …» («if-then»), аналогично правилу, используемому в экспертной системе • надёжность, достоверность (confidence) – вероятность соблюдения конкретного ассоциативного правила, не должна достигать пороговых значений (0% и 100%) Также практически во всех алгоритмах встречаются следующие понятия [189]: • кандидат (candidate) – товар или сочетания из k товаров, которые необходимо проверить на встречаемость во множестве транзакций • множество кандидатов (candidate set) – это все кандидаты, имеющиеся на данном шаге • часто встречаемый элемент (frequency) – кандидат, поддержка которого выше минимальной • набор часто встречаемых элементов (frequency set) – множество всех часто встречаемых элементов, которые удалось найти. Самым первым алгоритмом поиска ассоциативных правил был AIS, названный по первым буквам его создателей Agrawal, Imielinski и Swami, представителями научно-исследовательского центра Almaden Research Center в 1993 году. Примерно сразу же появляется и алгоритм |