Кластер на тему автомобиль

Производство легковых автомобилей в России по кластерам

В России производством легковых автомобилей занимаются более 20 сборочных предприятий. Наиболее крупные кластеры сформировались в Поволжье, на Северо-Западе и в Центре страны.

Из 1,2 млн выпущенных в прошлом году легковых автомобилей менее половины(45,4%) пришлось на Приволжский кластер. На местных автозаводах, расположенных в Тольятти, Ижевске, Ульяновске, Набережных Челнах, Елабуге и Нижнем Новгороде, суммарно было произведено 550 тыс. легковых автомобилей.

Свыше четверти (26,6%) легкового автопрома сосредоточено в Северо-Западном кластере, куда входят автосборочные предприятия Санкт-Петербурга и Всеволожска, совокупные показатели которых в минувшем году составили 322 тыс. единиц.

Шестая часть (16,2%) от общего объема производства легковых автомобилей в стране принадлежит заводам, входящим в Центральный кластер (Москва и Калуга), которым в общей сложности удалось произвести 196 тыс. машин.

Также в России есть сборочные предприятия так называемой внекластерной сборки, к которым относятся автозаводы в Калининграде, Владивостоке, Черкесске и Аргуне. Их доля составляет около 12%, что эквивалентно 143 тыс. легковых автомобилей.

Отметим также, что в 2015 году автосборочные предприятия в нашей стране произвели 118 моделей легковых автомобилей, относящихся к 28 различным маркам. При этом самые большие объемы выпуска приходятся на три модели, являющиеся лидерами российского рынка: LADA Granta, Hyundai Solaris и KIA Rio. Показатель каждой из них превысил 100 тысяч произведенных экземпляров.

Источник

Урок окружающего мира «Зачем нужны автомобили?»

Онлайн-конференция

«Современная профориентация педагогов
и родителей, перспективы рынка труда
и особенности личности подростка»

Свидетельство и скидка на обучение каждому участнику

Ф.И.О. автора: Мурина Юлия Вячеславовна.

Место работы: МБОУ Школа № 155 г.о. Самара.

Должность автора: учитель начальных классов.

УМК «Школа России», 1класс

Тема: «Зачем нужны автомобили?» (открытый урок)

Технологическая карта урока

Цели деятельности учителя

1) уточнить и систематизировать представления учащихся об устройстве и назначении автомобилей ; 2) развивать навыки чтения, связную речь, мышление, память, внимание;

3) воспитывать культуру общения, чувство взаимопомощи, доброжелательные отношения при работе в парах.

Урок открытия новых знаний.

Планируемые образовательные результаты

научатся классифицировать автомобили и объяснять их назначение, узнают основные детали автомобиля.

понимают учебную задачу урока, стремятся её выполнить, оценивают свои достижения на уроке; работают в паре: извлекают информацию из рисунка-схемы, проводят взаимопроверку; выполняют задания на основании информации из учебника.

проявляют интерес к новому учебному материалу и способам решения новой частной задачи; целостно воспринимают окружающий мир.

Использованные технологии и формы обучения

Технология развития критического мышления; индивидуальная, фронтальная, работа в парах.

Плешаков А.А. Учебник «Окружающий мир» 2 часть; электронное приложение к учебнику; презентация по истории автомобилей; карточки к составлению кластера; рисунки различных автомобилей.

Прозвенел звонок и смолк,

Встанем мы, ребята, ровно,

— Здравствуйте, ребята! Чтобы у всех на уроке было хорошее настроение, давайте улыбнёмся друг другу, улыбнёмся нашим гостям, поздороваемся с ними и тихонько сядем за парту. У нас урок окружающего мира, а что нам для него нужно? (ответы детей). Я вижу, что все готовы, тогда начнём.

Мотивация познавательной деятельности.

А начать мне хотелось бы с загадок. Отгадай, что это?

Есть кузов и кабина.

По ленточкам дорог.

Я вам доставлю в срок. (Грузовик) Вывешивается изображение грузовика на доску.

Пассажиров мы катаем

По маршрутам тут и там,

А туристов доставляем

К историческим местам.

Едем к цели дружно все

По проспектам и шоссе. (Автобусы) Иллюстрация закрепляется на доске.

В городах глубокой ночью

Спят автобус и трамвай.

Если транспорт нужен срочно –

Та приедет: «Я свободна!

Довезу куда угодно!» (Такси) Иллюстрация вывешивается на доску.

— Рассмотри иллюстрации на доске и дай общее название данной группе предметов. (Слово машина используется применительно к разным механизмам, поэтому правильнее будет использовать слово автомобиль).

(Выступление обучающегося с показом презентации)

Актуализация необходимых знаний

— Закройте глаза и представьте современный автомобиль. Какие слова, связанные с этим объектом, возникают у вас в воображении, какие факты, сведения известны вам об этом виде транспорта? Запишите их на листочке, лежащем перед вами. (Даю 2 минуты). А теперь обсудите ваши записи со своим соседом по парте, обменяйтесь мнениями по записанному материалу и не забудьте подать сигнал учителю об окончании работы. (3 минуты).

— Давайте сложим ваши автомобильные слова в нашу корзинку идей, только очень прошу не повторяться. (Заслушиваются ответы детей, которые фиксируются на доске учителем). Попробуем ваши слова объединить в группы. Какое название можно дать группе слов: руль, фары, колёса и т.д.? (устройство). Светофор, кресло безопасности и т.д.? (безопасность). Груз, люди и т.д.? (назначение). Такси, автобус и т. д.? (виды транспорта) На доске крепятся таблички: устройство, назначение, безопасность, виды автомобилей и одна пустая (может быть ещё что –то узнаем об автомобилях в ходе урока). Глядя на появившиеся записи, сформулируйте цели нашего урока.

Организация познавательной деятельности

— Давайте начнём нашу работу. У чьих родителей есть автомобиль? Какой он марки? Для чего используют его в вашей семье? Автомобили, служащие для перевозки людей называют пассажирскими. Какие ещё пассажирские автомобили вам известны? Найди пассажирские автомобили среди рисунков на доске.

— А для чего нужны грузовики? Как ты думаешь, как называются автомобили, служащие для перевозки грузов? Приведи пример грузовых автомобилей.

— Очень часто на улицах нашего города можно увидеть и такой автомобиль. (показываю иллюстрацию эвакуатора). Для чего служит эта машина? Группу автомобилей, служащую для оказания помощи людям, называют специальными автомобилями. А какие ещё автомобили можно отнести к этой группе? Почему автомобилям «скорой помощи», милиции, пожарным другие автомобили уступают дорогу?

— Итак, какие бывают автомобили по назначению?

— Все эти автомобили можно разделить на три большие группы: общественный транспорт, индивидуальный транспорт, автомобили специального назначения. Приведите примеры известных вам автомобилей каждой группы.

— Как же устроен наш «четырёхколёсный помощник»? Чтобы ответить на этот вопрос, давайте поработаем в парах. У вас на столах лежит инструкция для организации работы в парах, давайте с ней познакомимся.

Вместе со своим товарищем рассмотри схему устройства автомобиля на странице 60 нашего учебника;

Договорись, кто из вас будет сначала называть части автомобиля, а кто рассказывать о назначении каждой части, используя текст, лежащий у вас на парте;

Поменяйтесь ролями и проверьте работу друг друга;

Договорись, кто в вашей паре будет предоставлять результаты работы классу;

Подай сигнал окончания работы учителю.

— Кто не понял, как организовать работу в паре? Как это поменяться ролями? Тогда приступаем к работе. (Дети работают 5 минут.)

— Проверим работу наших пар. Внимание на доску! Покажите части автомобиля на доске и расскажите, для чего они служат. (Выполняют задание с электронного приложения).

— А для чего нужны ремни безопасности? Если вы с папой едете на автомобиле, то какие правила необходимо выполнять?

— Автомобили движутся благодаря той энергии, которая получается от сгорания бензина. В двигателе автомобиля возникают маленькие взрывы. Они «раскручивают» двигатель. Двигатель крутит колеса автомашины. Она едет. Но от этих маленьких взрывов в двигателе в воздух выделяется большое количество дыма и других вредных веществ. Иногда можно наблюдать, как пыхтит и дымит выхлопная труба у некоторых автобусов и автомобилей. Как ты думаешь: каким будет автомобиль будущего?

— Учёные тоже пытаются решить эту проблему, усовершенствуют машины. Об одном из таких усовершенствований прочитайте в учебнике на странице 61.

— Как называется один из автомобилей будущего? В чём разница между современными автомобилями и электромобилем? Что вы посоветуете своим родителям, имеющим автомобили с бензиновым двигателем? Предположите, что будет, если все автомобилисты будут ездить на электромобилях?

— Проверим работу на доске. Если вы согласны с расположением карточек, то поднимите вверх зелёный квадрат, если нет – красный.

— О чём мы сегодня говорили на уроке? Опишите этот предмет, какой он? двумя словами. Придумайте 3 слова, которые показывают, что предмет умеет делать. Составь предложение из 4-х слов выражающее ваше отношение к предмету. Вспомните всё о чём мы говорили сегодня на уроке и назовите слово, близкое по смыслу к слову автомобиль, которое указывает на смысл его существования. Прочитаем, что у нас получилось.

Источник

Раздел Научно-методический раздел, библиотеки

Статьи

Кластер: автомобилестроение

Автомобильный кластер можно назвать одним из самых динамично развивающихся, но неоднозначных проектов инновационного развития Петербурга. Достаточно неуверенные позиции отечественных автозаводов вкупе с конкуренцией со стороны зарубежных производителей вызывают сомнения в перспективах такого сотрудничества.

Тем не менее, о создании такого объединения было объявлено еще в 2010 году. О том, как этот проект реализуется сейчас в Санкт-Петербурге — в информации журнала «ГлавСправ».

Главный принцип кластера — географическая локализация взаимосвязанных производственных компаний, поставщиков оборудования, комплектующих и специализированных услуг. В кластер входят также: научно-исследовательские институты, вузы, технопарки, бизнес-инкубаторы и объекты инфраструктуры.

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

На территории РФ автомобильная промышленность представлена в четырех типах предприятий: традиционные автозаводы («АвтоВАЗ», «ГАЗ», «КамАЗ», «ЗИЛ» и др.), сборочные предприятия («Иж-Авто», «Тагаз», «Соллерс» и др.), иностранные автопроизводители и прямые импортеры.

Создание автомобильного кластера на территории Санкт-Петербурга обусловлено многолетней деятельностью предприятий мировых автопроизводителей на территории города и области. Первые заводы по выпуску автомобилей начали работу в 2007 году (Тойота). Сейчас в городе функционирует уже пять производств, в перспективе — еще один.

География кластера распространяется на промзоны города: Шушары, Каменка и Марьино.

Для поддержки предприятий автокластера правительством Российской Федерации был введен новый режим промышленной сборки автомобилей: таможенные ставки для ввоза комплектующих будут снижены у тех иностранных компаний, чья локализация производства в течение шести лет с момента заключения соглашения достигнет 60%.

План развития автомобильной промышленности прописан в соответствующей стратегии на период до 2020 года. При этом поставлена задача обеспечить транспортные потребности страны за счет производства высокотехнологичных комплектующих на внутреннем рынке, с максимальной локализацией.

В перспективе, собственные разработки российского автокластера смогут конкурировать с зарубежными на мировом рынке. Важным является и аспект состоятельности национальной оборонной промышленности: сильное внутреннее производство укрепит позиции российской военной техники.

Отдельно в стратегии прописаны пункты о разработке новых образовательных программ и программ повышения квалификации для обеспечения автомобильной промышленности рабочими кадрами. Государственная поддержка будет распространяться на подготовку научно-исследовательских, инженерных, производственных и управленческих кадров, в том числе, в зарубежных инжиниринговых и производственных центрах.

Образовательные и научные организации

В Петербурге идет работа по созданию центров по подготовке инженерных кадров для промышленных предприятий, входящих в автомобильный кластер. Первый такой центр уже создается в Санкт-Петербургском государственном политехническом университете при поддержке автомобильных заводов GM, Toyota, Hyundai и Nissan.

Результатом многолетней работы по укреплению внутреннего автомобильного рынка и сотрудничества с мировыми производителями станет повышение к 2020 году доли добавленной стоимости с текущего уровня 21% до 48% (2200 млрд. руб.), а также повышение доли автомобильной промышленности ВВП страны с 1% до 2,38%.

Ведущие предприятия автомобильного кластера

Ford Sollers (Focus, Mondeo)

General Motors (Chevrolet Cruze, Chevrolet Captiva, Opel Astra, Opel Antara)

Nissan (Teana, X-trail, Murano)

Toyota (Toyota Camry)

Scania (грузовые автомобили)

Холдинг «Яровит» и группа «Онэксим» (проект Ё-мобиль)

В феврале 2012 года были приняты первые шаги к появлению в Петербурге еще одного крупного автоконцерна — Fiat-Chrysler. Уже подписано соглашение, согласно которому строительство предприятия планируется начать в 2013 году в городе-спутнике «Южный» вблизи Санкт-Петербурга. Запуск производства мощностью 120 тысяч автомобилей намечен на конец 2014 года. Петербургский завод Fiat будет выпускать внедорожники Jeep Grand Сherokee и Compass.

Источник

Самарские автопроизводители решили перезапустить автомобильный кластер

ТОЛЬЯТТИ, 17 окт — РИА Новости, Нина Белая. Автопроизводители, входящие в состав Поволжского автомобильного кластера, на форуме «Автопром. Автокомпоненты» в Тольятти в среду приняли решение перезапустить работу этого объединения, заявил руководитель направления инновационного развития и кластерных инициатив Самарской области Владимир Сундквист.

Поволжский автомобильный кластер представлен такими крупными предприятиями, как ВАЗ, ГАЗ, АвтоВАЗ, Соллерс, КАМАЗ и другими. Он был создан компаниями-поставщиками «АвтоВАЗа» в 2010 году, чтобы удержаться на российском рынке, улучшая качество и конкурентоспособность своей продукции через интенсивную совместную работу автопроизводителей и поставщиков автокомпонентов. На открытом заседании кластера, которое прошло в среду в Тольятти в рамках форума представителей автоиндустрии, было принято решение перезапустить проект.

«Я считаю, что мы должны работать с тем, что у нас есть. Сегодня мы принимаем решение о перезапуске автокластера», — сказал Сундквист.

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

«Нам не удалось выстроить полноценную кластерную инициативу, при которой люди, обладающие определенными интеллектуальными возможностями, сели и сформулировали, куда и зачем идем», — сказал гендиректор Поволжского отделения российской инженерной академии Юрий Михеев.

Члены автокластера решили создать рабочую группу, которая в течение трех недель сформирует и представит новую программу и стратегию автомобильного автокластера. Результат работы созданной группы, по словам Михеева, будет опубликован на официальных сайтах Минэкономразвития и Минпромторга.

Источник

Как машины анализируют большие данные: введение в алгоритмы кластеризации

Взгляните на картинку ниже. Это коллекция насекомых (улитки не насекомые, но не будем придираться) разных форм и размеров. А теперь разделите их на несколько групп по степени похожести. Никакого подвоха. Начните с группирования пауков.

Закончили? Хотя здесь нет какого-то «правильного» решения, наверняка вы разделили этих существ на четыре кластера. В одном кластере пауки, во втором — пара улиток, в третьем — бабочки, и в четвёртом — трио из пчелы и ос.

Хорошо справились, не так ли? Вероятно, вы смогли бы сделать то же самое, будь насекомых на картинке вдвое больше. А если бы у вас было вдоволь времени — или тяга к энтомологии — то вы, вероятно, сгруппировали бы сотни насекомых.

Однако для машины группирование десяти объектов в осмысленные кластеры — задача непростая. Благодаря такому сложному разделу математики, как комбинаторика, мы знаем, что 10 насекомых группируются 115 975 способами. А если насекомых будет 20, то количество вариантов кластеризации превысит 50 триллионов.

С сотней насекомых количество возможных решений будет больше, чем количество элементарных частиц в известной Вселенной. Насколько больше? По моим подсчётам, примерно в пятьсот миллионов миллиардов миллиардов раз больше. Получается более четырёх миллионов миллиардов гуглов решений (что такое гугл?). И это лишь для сотни объектов.

Почти все эти комбинации будут бессмысленными. Несмотря на невообразимое количество решений, вы сами очень быстро нашли один из немногих полезных способов кластеризации.

Мы, люди, принимаем как должное своё прекрасное умение каталогизировать и понимать большие объёмы данных. Не важно, будет ли это текст, или картинки на экране, или последовательность объектов — люди, в целом, эффективно понимают данные, поступающие из окружающего мира.

Учитывая, что ключевой аспект разработки ИИ и машинного обучения заключается в том, чтобы машины быстро могли разбираться в больших объёмах входных данных, как повысить эффективность работы? В этой статье рассмотрим три алгоритма кластеризации, с помощью которых машины могут быстро осмыслить большие объёмы данных. Этот список далеко не полон — есть и другие алгоритмы, — но с него уже вполне можно начинать.

По каждому алгоритму я опишу, когда его можно использовать, как он работает, а также приведу пример с пошаговым разбором. Считаю, что для настоящего понимания алгоритма нужно самостоятельно повторить его работу. Если вы действительно заинтересованы, то поймёте, что лучше всего выполнять алгоритмы на бумаге. Действуйте, вас никто не осудит!

Три подозрительно опрятных кластера при k = 3

Кластеризация методом k-средних

Используется:

Когда вы понимаете, сколько групп может получиться для нахождения заранее заданного (a priori).

Как работает:

Алгоритм случайным образом присваивает каждое наблюдение к одной из k категорий, а затем вычисляет среднее по каждой категории. Затем он переприсваивает каждое наблюдение к категории с ближайшим средним, и снова вычисляет средние. Процесс повторяется до тех пор, пока переприсвоения становятся не нужны.

Рабочий пример:

Возьмём группу из 12 футболистов и количество забитых каждым из них голов в текущем сезоне (например, в диапазоне от 3 до 30). Разделим игроков, скажем, на три кластера.

Шаг 1: нужно случайным образом разделить игроков на три группы и вычислить среднее по каждой из них.

Шаг 2: переприсвоим каждого игрока к группе с ближайшим средним. Например, игрок А (5 голов) отправляется в группу 2 (среднее = 9). Затем снова вычисляем средние по группам.

Повторяем шаг 2 снова и снова, пока игроки перестанут менять группы. В данном искусственном примере это произойдёт уже на следующей итерации. Стоп! Вы сформировали из датасета три кластера!

Кластеры должны соответствовать позиции игроков на поле — защитники, центральные защитники и нападающие. K-средние работают в этом примере потому, что есть основания предполагать, что данные поделятся именно на эти три категории.

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

Существует несколько вариантов описанного алгоритма. Первоначальное формирование кластеров можно выполнять разными способами. Мы рассмотрели случайное классифицирование игроков по группам с последующим вычислением средних значений. В результате исходные средние значения групп близки друг к другу, что увеличивает повторяемость.

Альтернативный подход — формировать кластеры, состоящие всего из одного игрока, а затем группировать игроков в ближайшие кластеры. Получаемые кластеры больше зависят от начального этапа формирования, а повторяемость в датасетах с высокой вариабельностью снижается. Но при таком подходе для завершения алгоритма может потребоваться меньше итераций, потому что на разделение групп будет тратиться меньше времени.

Очевидный недостаток кластеризации методом k-средних заключается в том, что вам нужно заранее предположить, сколько кластеров у вас будет. Существуют методы оценки соответствия определённого набора кластеров. Например, внутрикластерная сумма квадратов (Within-Cluster Sum-of-Squares) — это мера вариабельности внутри каждого кластера. Чем «лучше» кластеры, тем ниже общая внутрикластерная сумма квадратов.

Иерархическая кластеризация

Используется:

Как работает:

Вычисляется матрица расстояний (distance matrix), в которой значение ячейки (i, j) является метрикой расстояния между значениями i и j. Затем берётся пара самых близких значений и вычисляется среднее. Создаётся новая матрица расстояний, парные значения объединяются в один объект. Затем из этой новой матрицы берётся пара самых близких значений и вычисляется новое среднее значение. Цикл повторяется, пока все значения не будут сгруппированы.

Рабочий пример:

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

Шаг 1: вычисляется матрица расстояний между всеми видами. Мы будем использовать евклидову метрику, описывающую, насколько далеко наши данные находятся друг от друга, словно населённые пункты на карте. Получить разницу в длине тел у каждой пары можно считав значение на пересечении соответствующей колонки и строки.

Шаг 2: Берётся пара двух ближайших друг к другу видов. В данном случае это афалина и серый дельфин, у которых средняя длина тела равна 3,3 м.

Повторяем шаг 1, снова вычисляя матрицу расстояний, но в этот раз мы объединяем афалину и серого дельфина в один объект с длиной тела 3,3 м.

Теперь повторим шаг 2, но уже с новой матрицей расстояний. На этот раз ближе всего окажутся гринда и косатка, так что соберём их в пару и вычислим среднее — 7 м.

Далее повторим шаг 1: снова вычислим матрицу расстояний, но уже с гриндой и косаткой в виде единого объекта с длиной тела в 7 м.

Повторим шаг 2 с этой матрицей. Наименьшее расстояние (3,7 м) будет между двумя объединёнными объектами, так что мы объединим их в ещё более крупный объект и вычислим среднее значение — 5,2 м.

Затем повторим шаг 1 и вычислим новую матрицу, объединив афалину/серого дельфина с гриндой/косаткой.

Повторим шаг 2. Наименьшее расстояние (5 м) будет между горбачом и финвалом, так что объединим их и вычислим среднее — 17,5 м.

Снова шаг 1: вычислим матрицу.

Наконец, повторим шаг 2 — осталось лишь одно расстояние (12,3 м), так что объединим всех в один объект и останавливаемся. Вот что получилось:

Объект имеет иерархическую структуру (вспоминаем JSON), так что его можно отобразить в виде древовидного графа, или дендрограммы. Результат похож на фамильное древо. Чем ближе на дереве два значения, тем более они схожи или тем теснее связаны.

Простенькая дендрограмма, сгенерированная с помощью R-Fiddle.org

Структура дендрограммы позволяет понять структуру самого датасета. В нашем примере получились две основные ветви — одна с горбачом и финвалом, другая с афалиной/серым дельфином и гриндой/косаткой.

В эволюционной биологии для выявления таксономических связей используются гораздо более крупные датасеты со множеством видов и обилием признаков. Вне биологии иерархическая кластеризация применяется в сферах Data Mining и машинного обучения.

Этот подход не требует прогнозировать искомое количество кластеров. Вы можете разбивать полученную дендрограмму на кластеры, «обрезая» дерево на нужной высоте. Выбрать высоту можно разными способами, в зависимости от желаемого разрешения кластеризации данных.
К примеру, если вышеприведённую дендрограмму обрезать на высоте 10, то мы пересечём две основные ветви, тем самым разделив дендрограмму на два графа. Если же обрезать на высоте 2, то разделим дендрограмму на три кластера.

Другие алгоритмы иерархической кластеризации могут отличаться в трёх аспектах от описанного в этой статье.

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

Также существует несколько методов вычисления матриц расстояний. Евклидовой метрики достаточно для большинства задач, но в каких-то ситуациях лучше подходят другие метрики.

Наконец, может варьироваться и критерий объединения (linkage criterion). Связь между кластерами зависит от их близости друг к другу, но определение «близости» бывает разным. В нашем примере мы измеряли расстояние между средними значениями (или «центроидами») каждой группы и объединяли ближайшие группы в пары. Но вы можете использовать и другое определение.

Допустим, каждый кластер состоит из нескольких дискретных значений. Расстояние между двумя кластерами можно определить как минимальное (или максимальное) расстояние между любыми их значениями, как показано ниже. Для разных контекстов удобно использовать разные определения критерия объединения.

Красный/синий: центроидное объединение; красный/зелёный: объединение на основе минимумов; зелёный/синий: объединение на основе максимумов.

Определение сообществ в графах (Graph Community Detection)

Используется:

Когда ваши данные можно представить в виде сети, или «графа».

Как работает:

Сообщество в графе (graph community) очень грубо можно определить как подмножество вершин, которые больше связаны друг с другом, чем с остальной сетью. Есть разные алгоритмы определения сообществ, основанные на более специфичных определениях, например, Edge Betweenness, Modularity-Maximsation, Walktrap, Clique Percolation, Leading Eigenvector…

Рабочий пример:

Теория графов — очень интересный раздел математики, позволяющий нам моделировать сложные системы в виде абстрактных наборов «точек» (вершин, узлов), соединённых «линиями» (рёбрами).

Пожалуй, первое применение графов, которое приходит в голову, это исследование социальных сетей. В этом случае вершины представляют людей, которые рёбрами соединены с друзьями/подписчиками. Но представить в виде сети можно любую систему, если вы сможете обосновать метод осмысленного соединения компонентов. К новаторским применениям кластеризации с помощью теории графов относятся извлечение свойств из визуальных данных и анализ генетических регуляторных сетей.

В качестве простенького примера давайте рассмотрим нижеприведённый граф. Здесь показано восемь сайтов, которые я посещаю чаще всего. Связи между ними построены на основе ссылок в статьях на Википедии. Такие данные можно собрать и вручную, но для больших проектов куда быстрее написать скрипт на Python. Например, такой: https://raw.githubusercontent.com/pg0408/Medium-articles/master/graph_maker.py.

Граф построен с помощью пакета igraph для R 3.3.3

Цвет вершин зависит от участия в сообществах, а размер зависит от центральности (centrality). Обратите внимание, что самыми центральными являются Google и Twitter.

Также получившиеся кластеры весьма точно отражают реальные задачи (это всегда важный индикатор производительности). Жёлтыми выделены вершины, представляющие ссылочные/поисковые сайты; синим выделены сайты для онлайн-публикаций (статей, твитов или кода); красным выделены PayPal и YouTube, основанный бывшими сотрудниками PayPal. Неплохая дедукция для компьютера!

Помимо визуализации больших систем, настоящая сила сетей заключена в математическом анализе. Начнём с преобразования картинки сети в математический формат. Ниже приведена матрица смежности (adjacency matrix) сети.

Значения на пересечениях столбцов и строк указывают, есть ли ребро между этой парой вершин. Например, между Medium и Twitter оно есть, поэтому на пересечении этой строки и колонки стоит 1. А между Medium и PayPal ребра нет, так что в соответствующей ячейке стоит 0.

Если представить все свойства сети в виде матрицы смежности, это позволит нам сделать всевозможные полезные выводы. К примеру, сумма значений в любой колонке или строке характеризует степень (degree) каждой вершины — то есть количество объектов, соединённых с этой вершиной. Обычно обозначается буквой k.

Если просуммировать степени всех вершин и разделить на два, то получим L — количество рёбер в сети. А количество рядов и колонок равно N — количеству вершин в сети.

Зная лишь k, L, N и значения во всех ячейках матрицы смежности А, мы можем вычислить модулярность любой кластеризации.

Допустим, мы кластеризовали сеть на какое-то количество сообществ. Тогда можно использовать значение модулярности для прогнозирования «качества» кластеризации. Более высокая модулярность говорит о том, что мы разделили сеть на «точные» сообщества, а более низкая модулярность предполагает, что кластеры образованы скорее случайно, чем обоснованно. Чтобы было понятнее:

Модулярность служит мерой «качества» групп.

Модулярность можно вычислить по такой формуле:

Давайте разберём эту довольно устрашающе выглядящую формулу.

М, как вы понимаете, это и есть модулярность.

Коэффициент 1/2L означает, что всё остальное «тело» формулы мы делим на 2L, то есть на двойное количество рёбер в сети. На Python можно было бы написать:

Значения k_i и k_j — степени каждой вершины. Их можно найти, просуммировав значения в ряде i и колонке j соответственно. Если умножить их и разделить на 2L, то получим ожидаемое количество рёбер между вершинами i и j, если бы сеть была перемешана случайным образом.

Содержимое скобок отражает разницу между реальной структурой сети и ожидаемой в том случае, если бы сеть была пересобрана случайным образом. Если поиграться со значениями, то наивысшая модулярность будет при A_ij = 1 и низком ( k_i k_j ) / 2L. То есть модулярность повышается в том случае, если между вершинами i и j есть «неожиданное» ребро.

Наконец, умножаем содержимое скобок на то, что в формуле обозначено как δc_i, c_j. Это символ Кронекера (Kronecker-delta function). Вот его реализация на Python:

Да, настолько просто. Функция берёт два аргумента, и если они идентичны, то возвращает 1, а если нет, то 0.

Иными словами, если вершины i и j попадут в один кластер, то δc_i, c_j = 1. А если они будут в разных кластерах, функция вернёт 0.

Поскольку мы умножаем содержимое скобок на символ Кронекера, то результат вложенной суммы Σ будет наивысшим, когда вершины внутри одного кластера соединяются большим количеством «неожиданных» рёбер. Таким образом, модулярность — показатель того, насколько хорошо граф кластеризован на отдельные сообщества.

Деление на 2L ограничивает единицей верхнее значение модулярности. Если модулярность близка к 0 или отрицательная, это означает, что текущая кластеризация сети не имеет смысла. Увеличивая модулярность, мы можем найти лучший способ кластеризации сети.

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

Комбинаторика подсказывает, что для сети с 8 вершинами существует 4140 способов кластеризации. Для сети с 16 вершинами будет уже больше 10 млрд способов, для сети с 32 вершинами — 128 септильонов, а для сети с 80 вершинами количество способов кластеризации превысит количество атомов в наблюдаемой Вселенной.

Поэтому вместо перебора воспользуемся эвристическим методом, который поможет относительно легко вычислить кластеры с максимальной модулярностью. Это алгоритм под названием Fast-Greedy Modularity-Maximization, своеобразный аналог описанному выше алгоритму агломеративной иерархической кластеризации. Вместо объединения по признаку близости, Mod-Max объединяет сообщества в зависимости от изменений модулярности. Как это работает:

Сначала каждая вершина присваивается к собственному сообществу и вычисляется модулярность всей сети — М.

Шаг 1: для каждой пары сообществ, связанных хотя бы одним ребром, алгоритм вычисляет результирующее изменение модулярности ΔM в случае объединения этих пар сообществ.

Шаг 2: затем берётся пара, при объединении которой ΔM будет максимальной, и объединяется. Для этой кластеризации вычисляется новая модулярность и сохраняется.

Шаги 1 и 2 повторяются: каждый раз объединяется пара сообществ, которая даёт наибольшее ΔM, сохраняется новая схема кластеризации и её М.

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

Это было вычислительно сложно, как минимум для людей. Теория графов — богатый источник трудных вычислительных задач и НП-трудных (NP-hard) проблем. С помощью графов мы можем делать множество полезных выводов о сложных системах и датасетах. Спросите Ларри Пейджа, чей алгоритм PageRank — помогший Google превратиться из стартапа в мирового доминанта меньше, чем за жизнь одного поколения, — целиком основан на теории графов.

В исследованиях, посвящённых теории графов, основное внимание сегодня уделяется именно определению сообществ. Существует много альтернатив алгоритму Modularity-Maximization, который хоть и полезен, но не лишён недостатков.

Во-первых, при агломеративном подходе маленькие, хорошо выделенные сообщества часто объединяются в более крупные. Это называется пределом разрешения (resolution limit) — алгоритм не выделяет сообщества меньше определённого размера. Другой недостаток в том, что вместо одного выраженного, легко достижимого глобального пика алгоритм Mod-Max стремится сгенерировать широкое «плато» из многих близких значений модулярности. В результате получается трудно выделить победителя.

В других алгоритмах используются иные способы определения сообществ. Например, Edge-Betweenness — дивизивный (разделительный) алгоритм, который начинает с группирования всех вершин в один огромный кластер. Затем итеративно убираются наименее «важные» рёбра, пока все вершины не окажутся изолированными. Получается иерархическая структура, в которой вершины тем ближе друг к другу, чем больше они схожи.

Алгоритм, Clique Percolation, учитывает возможные пересечения между сообществами. Есть группа алгоритмов, основанных на случайном блуждании по графу, и есть методы спектральной кластеризации, который занимаются спектральным разложением (eigendecomposition) матрицы смежности и других, производных из неё матриц. Все эти идеи используются для выделения признаков, например, в машинном зрении.

Подробно разбирать рабочие примеры для каждого алгоритма мы не будем. Достаточно сказать, что сегодня в этом направлении ведутся активные исследования и создаются мощные методики анализа данных, просчитывать которые ещё лет 20 назад было крайне трудно.

Заключение

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

Как было сказано в начале, машинное обучение — чрезвычайно амбициозная сфера исследований, в которой очень сложные задачи требует разработки максимально точных и эффективных подходов. То, что людям свойственно от природы, при переносе в компьютер требует инновационных решений.

Работы ещё непочатый край, и тот, кто предложит следующую прорывную идею, вне всяких сомнений, будет щедро вознаграждён. Возможно, кто-то из вас, читатели, создаст новый мощный алгоритм? Все великие идеи с чего-то начинаются!

Источник