На этом шаге мы рассмотрим пример использования этого алгоритма.
В каждом американском штате есть губернатор. В июне 2017 года возраст этих чиновников находился в диапазоне от 42 до 79 лет. Если рассмотреть Соединенные Штаты с востока на запад, перебирая все штаты по долготе, то, возможно, удастся сформировать группы штатов с близкой долготой и близким возрастом губернаторов. На рисунке 1 представлена диаграмма распределения всех 50 губернаторов. По оси X откладывается долгота штата, а по оси Y - возраст губернатора.
Рис.1. Губернаторы штатов расположены по долготе возглавляемых ими штатов и возрасту (по состоянию на июнь 2017 года) (изображение кликабельно)
Существуют ли на рисунке 1 какие-либо очевидные кластеры? Оси здесь не нормированы. Напротив, мы рассматриваем необработанные данные. Если бы кластеры всегда были очевидными, то не было бы необходимости в алгоритмах кластеризации.
Попробуем пропустить этот набор данных через алгоритм k-средних. Для этого в первую очередь понадобится способ представления отдельной единицы данных:
from __future__ import annotations from typing import List from data_point import DataPoint from pr74_1 import KMeans class Governor(DataPoint): def __init__(self, longitude: float, age: float, state: str) -> None: super().__init__([longitude, age]) self.longitude = longitude self.age = age self.state = state def __repr__(self) -> str: return f"{self.state}: (долгота: {self.longitude}, возраст: {self.age})"
У класса Governor есть два именованных и сохраненных измерения: longitude и age. Кроме того, Governor не вносит никаких других изменений в механизм своего суперкласса DataPoint, кроме переопределенного __repr__() для структурной печати.
if __name__ == "__main__": governors: List[Governor] = \ [Governor(-86.79113, 72, "Алабама"), Governor(-152.404419, 66, "Аляска"), Governor(-111.431221, 53, "Аризона"), Governor(-92.373123, 66, "Арканзас"), Governor(-119.681564, 79, "Калифорния"), Governor(-105.311104, 65, "Колорадо"), Governor(-72.755371, 61, "Коннектикут"), Governor(-75.507141, 61, "Делавер"), Governor(-81.686783, 64, "Флорида"), Governor(-83.643074, 74, "Джорджия"), Governor(-157.498337, 60, "Гавайи"), Governor(-114.478828, 75, "Айдахо"), Governor(-88.986137, 60, "Иллинойс"), Governor(-86.258278, 49, "Индиана"), Governor(-93.210526, 57, "Юта"), Governor(-96.726486, 60, "Канзас"), Governor(-84.670067, 50, "Кентукки"), Governor(-91.867805, 50, "Луизиана"), Governor(-69.381927, 68, "Мэн"), Governor(-76.802101, 61, "Мэриленд"), Governor(-71.530106, 60, "Массачусетс"), Governor(-84.536095, 58, "Мичиган"), Governor(-93.900192, 70, "Миннесота"), Governor(-89.678696, 62, "Миссисипи"), Governor(-92.288368, 43, "Миссури"), Governor(-110.454353, 51, "Монтана"), Governor(-98.268082, 52, "Небраска"), Governor(-117.055374, 53, "Невада"), Governor(-71.563896, 42, "Нью-Гэмпшир"), Governor(-74.521011, 54, "Нью-Джерси"), Governor(-106.248482, 57, "Нью-Мексико"), Governor(-74.948051, 59, "Нью-Йорк"), Governor(-79.806419, 60, "Северная Каролина"), Governor(-99.784012, 60, "Северная Дакота"), Governor(-82.764915, 65, "Огайо"), Governor(-96.928917, 62, "Оклахома"), Governor(-122.070938, 56, "Орегон"), Governor(-77.209755, 68, "Пенсильвания"), Governor(-71.51178, 46, "Род-Айленд"), Governor(-80.945007, 70, "Южная Каролина"), Governor(-99.438828, 64, "Южная Дакота"), Governor(-86.692345, 58, "Теннесси"), Governor(-97.563461, 59, "Техас"), Governor(-111.862434, 70, "Юта"), Governor(-72.710686, 58, "Вермонт"), Governor(-78.169968, 60, "Виргиния"), Governor(-121.490494, 66, "Вашингтон"), Governor(-80.954453, 66, "Западная Виргиния"), Governor(-89.616508, 49, "Висконсин"), Governor(-107.30249, 55, "Вайоминг")]
Запустим алгоритм k-средних с k, равным 2:
kmeans: KMeans[Governor] = KMeans(2, governors)
gov_clusters: List[KMeans.Cluster] = kmeans.run()
for index, cluster in enumerate(gov_clusters):
print(f"Кластер {index}: {cluster.points}\n")
Поскольку выполнение алгоритма начинается со случайно выбранных центроидов, то каждый запуск KMeans потенциально может возвращать разные кластеры. Чтобы увидеть, действительно ли это правильно выбранные кластеры, требуется анализ результатов человеком. Следующий результат получен после запуска, который дал действительно интересный кластер:
Сошлось после 4 итерации Кластер 0: [Аляска: (долгота: -152.404419, возраст: 66), Калифорния: (долгота: -119.681564, возраст: 79), Гавайи: (долгота: -157.498337, возраст: 60), Айдахо: (долгота: -114.478828, возраст: 75), Орегон: (долгота: -122.070938, возраст: 56), Юта: (долгота: -111.862434, возраст: 70), Вашингтон: (долгота: -121.490494, возраст: 66)] Кластер 1: [Алабама: (долгота: -86.79113, возраст: 72), Аризона: (долгота: -111.431221, возраст: 53), Арканзас: (долгота: -92.373123, возраст: 66), Колорадо: (долгота: -105.311104, возраст: 65), Коннектикут: (долгота: -72.755371, возраст: 61), Делавер: (долгота: -75.507141, возраст: 61), Флорида: (долгота: -81.686783, возраст: 64), Джорджия: (долгота: -83.643074, возраст: 74), Иллинойс: (долгота: -88.986137, возраст: 60), Индиана: (долгота: -86.258278, возраст: 49), Юта: (долгота: -93.210526, возраст: 57), Канзас: (долгота: -96.726486, возраст: 60), Кентукки: (долгота: -84.670067, возраст: 50), Луизиана: (долгота: -91.867805, возраст: 50), Мэн: (долгота: -69.381927, возраст: 68), Мэриленд: (долгота: -76.802101, возраст: 61), Массачусетс: (долгота: -71.530106, возраст: 60), Мичиган: (долгота: -84.536095, возраст: 58), Миннесота: (долгота: -93.900192, возраст: 70), Миссисипи: (долгота: -89.678696, возраст: 62), Миссури: (долгота: -92.288368, возраст: 43), Монтана: (долгота: -110.454353, возраст: 51), Небраска: (долгота: -98.268082, возраст: 52), Невада: (долгота: -117.055374, возраст: 53), Нью-Гэмпшир: (долгота: -71.563896, возраст: 42), Нью-Джерси: (долгота: -74.521011, возраст: 54), Нью-Мексико: (долгота: -106.248482, возраст: 57), Нью-Йорк: (долгота: -74.948051, возраст: 59), Северная Каролина: (долгота: -79.806419, возраст: 60), Северная Дакота: (долгота: -99.784012, возраст: 60), Огайо: (долгота: -82.764915, возраст: 65), Оклахома: (долгота: -96.928917, возраст: 62), Пенсильвания: (долгота: -77.209755, возраст: 68), Род-Айленд: (долгота: -71.51178, возраст: 46), Южная Каролина: (долгота: -80.945007, возраст: 70), Южная Дакота: (долгота: -99.438828, возраст: 64), Теннесси: (долгота: -86.692345, возраст: 58), Техас: (долгота: -97.563461, возраст: 59), Вермонт: (долгота: -72.710686, возраст: 58), Виргиния: (долгота: -78.169968, возраст: 60), Западная Виргиния: (долгота: -80.954453, возраст: 66), Висконсин: (долгота: -89.616508, возраст: 49), Вайоминг: (долгота: -107.30249, возраст: 55)]
Кластер 0 представляет штаты крайнего Запада, все они географически расположены рядом друг с другом (если считать Аляску и Гавайи штатами Тихоокеанского побережья). Во всех них относительно старые губернаторы, следовательно, эти штаты образуют интересную группу. Население Тихоокеанского побережья предпочитает губернаторов постарше? Мы не можем сделать на основании этих кластеров какие-либо определенные выводы за пределами этой корреляции. Результат показан на рисунке 2.
Рис.2. Единицы данных кластера 1 обозначены кружками, а единицы данных кластера 0 - квадратиками (изображение кликабельно)
Необходимо еще и еще раз подчеркнуть, что результаты, полученные методом k-средних со случайной инициализацией центроидов, всегда будут различаться. Обязательно запустите
алгоритм k-средних несколько раз, независимо от набора данных.
На следующем шаге мы рассмотрим еще один интересный пример.
