Министерство образования и науки Российской Федерации
Министерство образования Саратовской области
Национальный исследовательский Саратовский государственный университет имени Н.Г. Чернышевского
Саратовский областной институт развития образования
Комитет по информатизации Саратовской области
Комитет по образованию администрации муниципального образования «Город Саратов»
Автономная некоммерческая организация «Информационные технологии в образовании»
Автономная некоммерческая организация «Научно-исследовательский центр «Образование. Качество. Отрасль»»
IX Всероссийская (с международным участием) научно-практическая конференция
«Информационные технологии в образовании»
«ИТО-Саратов-2017»
2-3 ноября 2017 года, г. Саратов

Изучение вопросов искусственного интеллекта на ступени СОО на примере итерационного алгоритма кластеризации k-means

ООО «Лаборатория знаний»
В статье приводится пример актуальной темы применения итеративного алгоритма кластерного анализа в рамках изучения вопросов искусственного интеллекта на ступени СОО. Также предложено использование специализированных сервисов для визуализации и применения алгоритмов искусственного интеллекта, не требующих глубоких знаний языков программирования обучающимися непрофильных классов.
Статья посвящена проблемам изучения вопросов искусственного интеллекта на ступени СОО на примере итерационного алгоритма кластерного анализа k-means и инструментам для практического изучения алгоритов машинного обучения обучающимся непрофильных классов.

Область искусственного интеллекта не является новой наукой, но её активное вхождение в жизнь общества началось после 2010 года в связи с развитием технологий, их удешевлением и развитием облачных сервисов. Современные технические средства позволяют производить сложные вычисления, требующие больших объёмов памяти, на серверах удалённо. Поскольку интеллектуальные алгоритмы используются во всех сферах человеческой жизни без исключения, обострилась необходимость изучения этой области в школе. Изучение вопросов искусственного интеллекта – одна из актуальных тем в рамках углублённого курса информатики на ступени среднего общего образования.

Сегодня мир производит колоссальные объёмы информацию: в 2016 году за одну секунду человечество производит примерно 11,75 эксабайт (1 эксабайт = 1018 байт) информации [3]. Для сравнения в 2003 году подобный объём генерировался за год. К сожалению, скорость создания новой информации намного превышает скорость создания новых ресурсов для хранения информации. В связи с этим, наряду с созданием новых технологий хранения информации, с каждым годом всё более актуальна проблема обработки больших данных для структурирования, получения новых данных и выявления взаимосвязей, а также уменьшения их объёма путём избавления от избыточной информации. Наиболее эффективным решением является применение алгоритмов интеллектуальной обработки данных, позволяющих структурировать информацию, избегая хранения избыточных данных при минимально затрачиваемых ресурсах.  Алгоритмы постоянно совершенствуются не только для повышения качества выявленных связей и иных результатов, но и для уменьшения их сложности, как следствие, затрат ресурсов (мощности компьютеров для вычислений и времени обработки).

Наиболее распространёнными являются алгоритмы кластеризации, применяемые в том числе в популярном сегодня направлении распознавания образов, речи, включая синхронный перевод. Кластерный анализ (Cluster Analysis) — это многомерная статистическая процедура, выполняющая сбор данных, содержащих информацию о выборке объектов, и упорядочивающая объекты в сравнительно однородные чаще непересекающиеся группы (кластеры). Объекты различных кластеров должны существенно отличаться. Алгоритм кластеризации каждому x∈X, где X – множество входящих данных, ставит в соответствие номер соответствующего кластера y∈Y, где Y– множество меток (имён) всех кластеров [5].

Кластерный анализ является частью интеллектуального (глубинного) анализа данных (DataMining) – совокупности методов и алгоритмов, а также сам процесс аналитического исследования больших массивов информации с целью выявления определённых закономерностей и систематических взаимосвязей, которые могут быть применены к новым совокупностям, чаще с целью получения практической пользы или экономической выгоды. Совокупность же всех методов обработки и хранения большого количество связанной информации, рынок компаний, занимающихся технологиями её обработки, представляет собой достаточно новое направление – науку о больших данных (BigData).

Наиболее популярный для изучения алгоритм кластерного анализа – это классический алгоритм k-means (метод k-средних; быстрый кластерный анализ), поскольку он достаточно прост в реализации, понимании и достаточно надёжен. Впервые полное описание этого алгоритма было опубликовано Хартиганом и Вонгом в 1979 году [1]. Он долгий период времени (2006-2017) занимает второе место по популярности среди всех применяемых алгоритмов Data Mining, уступая лишь регрессионному алгоритму C4.5.

Метод k-средних является итеративным алгоритмом разбиения множества объектов на k классов. Значительным минусом алгоритма k-средних является необходимость объявления заведомо известного количества кластеров, поэтому зачастую его используют в связке с другими алгоритмами, а не самостоятельно. Внутри каждого кластера находится центр масс – внутрикластерное среднее по каждому признаку cj, вычисляемому как: где  – это множество всех центров масс кластеров, а –рассматриваемые объекты из X. Целевая функция алгоритма представляет собой нахождение расстояния между объектами из выборки и найденными центроидами их классов:
, где – расстояние от центра j-того кластера до i-того объекта.

Алгоритм назначает k случайных точек в качестве начальных центроидов, затем каждый объект выборки получает метку кластера ближайшего центроида (см. рис. 1). Существуют также способы выбора начальных центроидов как первых k встреченных наблюдений или как k максимально удалённых друг от друга точек.  Затем производится обновление центроидов путём вычисления центра масс получившихся кластеров (полученные центры не обязаны совпадать с каким-либо объектом внутри кластера). Итерации продолжаются до тех пор, пока кластеры изменяются.

Рисунок 1 Работа алгоритма k-means при k=3

К сожалению, результат работы алгоритма во многом зависит от критерия выбора начальных центроидов и метрики для подсчёта расстояния, k-meansмедленно справляется с большими выборками, не справляется, когда объекты в равной степени принадлежат двум и более классам. Алгоритм k-means крайне чувствителен к вбросам. Они в значительной степени влияют на подсчёт центра масс кластеров как среднего. Для устранения этого недостатка применяют алгоритм k-medians (k-медиан).Подсчёт медианы позволяет минимизировать ошибки по всем кластерам в метрике с 1-нормой. В случае прибавления условия, что найденный кластероид должен совпадать с каким-либо представителем кластера, получают алгоритм k-medoids (k-метоидов). Проблема же принадлежности к нескольким кластерам решается с помощью c-means, определяющего вероятность вхождения объектов во все кластеры. Существует целое семейство модификаций алгоритма, помогающее разрешить некоторые его проблемы. К сожалению, все из этих алгоритмов могут быть неэффективными для выборок, обладающих определёнными (для каждой модификации разными) характеристиками, что отображает теорему “No Free Lunch” («бесплатных завтраков не бывает»). Универсальных методов обработки больших данных, не только методами кластеризации, не существует.

Оценка качества и визуализации работы k-means может быть произведена, например, с помощью функции силуэта Sh(C), демонстрирующей распределение величины, равной отношению разности среднего расстояния до членов ближайшего кластера и среднего расстояния до членов своего кластера, делённого на максимум из этих двух средних. Значение силуэта , где 1 достигается при максимальном расстоянии между кластерами [6].  

Алгоритм k-means для изучения в школе представлен, например, в элективном курсе «Искусственный интеллект» Л.Н. Ясницкого [7]. Проблема изучения любых интеллектуальных алгоритмов в школьном курсе информатики заключается в том, что они представлены, в основном, с теоретической точки зрения, в то время как практическая часть сегодня наиболее актуальна, но отражена в учебных изданиях слишком сложно. Для их освоения требуются хорошее знание языков программирования. Информатизация общества и увеличение уровня его инженерной культуры делает необходимым понимание основ искусственного интеллекта и принципов работы алгоритмов представителями различных профессий, включая традиционно гуманитарные направления (социологию, филологию, менеджмент и др.), а также представителями прикладных областей, имеющим только среднее-специальное образование. Примерами являются анализ потребительских корзин, создание индивидуальных меню, анализ поведения людей в социальных сетях, прогнозирование поведения групп и возможных беспорядков правоохранительными органами и многое другое. Алгоритмы также требуются для обработки больших данных исследователями.

В последние пять лет на рынке информационных решений появились новые продукты, нацеленные на применение интеллектуальных алгоритмов и когнитивных сервисов профессионалами, не вовлечёнными ранее в ИТ-сферу. Одним из таких продуктов является облачная платформа Azure Machine Learning, позволяющая составить модель работы с большими данными с подключением собственной выборки. Модель составляется из соединяемых блоков по принципу графических языков программирования. Для демонстрации можно использовать Лабораторию с подключённым к проекту модулем K-Means Clustering [2]. В его параметрах задаются количество кластероидов, метрика (по умолчанию – Евклидова, также используется Хэмминга и Минковского), метод инициализации кластероидов (по умолчанию – k-means++) и количество итераций. Если представленных характеристик недостаточно, возможно подключение блока с алгоритмом, написанном на языке R (в Лаборатории доступны все его популярные модули) или Python (также подключено большое количество различных пакетов). Выборка для анализа может быть загружена из csv-файла, экспортированного, например, из статистики группы VK с большим количеством участников. Результаты также возможно сохранять в формате cvs-таблицы. Стоит отметить, что Azure предоставляет бесплатное пользование для участников программы Microsoft Imagine [4] для школьников и студентов без обязательств и без временных ограничений, включая использование достаточных для учебных проектов квот обращений в Microsoft Azure Cognitive Services – API когнитивных сервисов, включая, например, распознавание речи и лиц. Для других проектов могут понадобиться The Microsoft Cognitive Toolkit, находящийся в свободном доступе.

Технологический прогресс и развитие общества требуют постоянного усложнения, дополнения школьного курса информатики, а также переосмысления некоторых его составляющих, включая изучение искусственного интеллекта не только в рамках углублённого уровня. Более практико-ориентированная методика преподавания вопросов искусственного интеллекта – ключ к эффективному усвоению материала обучающимися.  

Список использованных источников
  1. J. A. Hartigan and M. A. Wong. Algorithm AS 136: A K-Means Clustering Algorithm / A. Hartigan, M.A.Wong // Journal of the Royal Statistical Society. Series C (Applied Statistics). – 1979. – Vol. 28, No. 1. – С. 100-108.
  2. K-Means Clustering (Microsoft Azure) [Электронный ресурс]. – Режим доступа : https://msdn.microsoft.com/en-us/library/azure/dn905944.aspx, свободный. – Загл. с экрана.
  3. Мир в терабайтах: "Большие данные - это поток опыта" [Электронный ресурс]. – Режим доступа : https://rg.ru/2017/10/03/mir-v-terabajtah-bolshie-dannye-eto-potok-opyta.html, свободный. – Загл. с экрана.
  4. Программа Microsoft Imagine [Электронный ресурс]. – Режим доступа : https://imagine.microsoft.com/ru-ru, свободный. – Загл. с экрана.
  5. Ресурс MachineLearning.ru при поддержке РФФИ [Электронный ресурс]. – Режим доступа : http://www.machinelearning.ru/wiki/index.php?title=, свободный. – Загл. с экрана.
  6. Сирота А.А. Методы и алгоритмы анализа данных и их моделирование в MATLAB: учеб. пособие. – СПб.: БХВ-Петербург, 2016 – 384 с. : ил. – (Учебное пособие)
  7. Ясницкий Л.Н. Искусственный интеллект. Элективный курс : учебное пособие / Л.Н. Ясницкий – М.: БИНОМ. Лаборатория знаний, 2011 – 197 с.
Вид представления доклада  Устное выступление и публикация
Ключевые слова  искусственный интеллект, Big Data, Data Mining, Cluster Analysis, k-means, итерационные алгоритмы кластерного анализа, СОО, информатика, практико-ориентированное обучение

В статусе «Черновик» Вы можете производить с тезисами любые действия.

В статусе «Отправлено в Оргкомитет» тезисы проходят проверку в Оргкомитете. Статус «Черновик» может быть возвращен тезисам либо если есть замечания рецензента, либо тезисы превышают требуемый объем, либо по запросу участника.

В статусе «Рекомендован к публикации» тезис публикуется на сайте. Статус «Черновик» может быть возвращен либо по запросу участника, либо при неоплате публикации, если она предусмотрена, либо если тезисы превышают требуемый объем.

Статус «Опубликован» означает, что издана бумажная версия тезиса и тезис изменить нельзя. В некоторых крайне редких ситуацих участник может договориться с Оргкомитетом о переводе тезисов в статус «Черновик».

Статус «Отклонен» означает, что по ряду причин, которые указаны в комментариях к тезису, Оргкомитет не может принять тезисы к публикации. Из отклоненных тезис в «Черновики» может вернуть только Председатель программного или председатель оргкомитета.