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

    Алгоритм кластеризации потребует некоторых статистических примитивов (среднее значение, стандартное отклонение и т. д.). Начиная с Python версии 3.4, в стандартную библиотеку языка входит несколько полезных статистических примитивов в модуле statistics. Следует отметить: хотя в книге мы и придерживаемся стандартной библиотеки, существуют более эффективные сторонние библиотеки для операций с числами, такие как NumPy, - их и следует использовать в приложениях, для которых важна производительность, особенно для работы с большими объемами данных.

    Для простоты все наборы данных, с которыми мы будем работать далее в этих шагах, можно выразить с помощью типа float, поэтому здесь будет много операций со списками и кортежами данных типа float. Статистические примитивы sum(), mean() и pstdev() определены в стандартной библиотеке. Их определения вытекают из формул, которые вы найдете в любом учебнике по статистике. Кроме того, нам понадобится функция для вычисления z-оценок:

from __future__ import annotations
from typing import TypeVar, Generic, List, Sequence
from copy import deepcopy
from functools import partial
from random import uniform
from statistics import mean, pstdev
from dataclasses import dataclass
from data_point import DataPoint


def zscores(original: Sequence[float]) -> List[float]:
    avg: float = mean(original)
    std: float = pstdev(original)
    if std == 0: # если нет изменений, то вернуть все нули
        return [0] * len(original)
    return [(x - avg) / std for x in original]

Функция pstdev() находит стандартное отклонение множества, a stdev(), которую мы не используем, - стандартное отклонение выборки.

    Функция zscores() преобразует последовательность чисел в список чисел с соответствующими z-оценками исходных чисел относительно всех чисел в исходной последовательности. Подробнее о z-оценках будет рассказано позже.

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

    Все алгоритмы кластеризации работают с единицами данных, и наша реализация метода k-средних (k-means) не станет исключением. Мы определим общий интерфейс под названием DataPoint. Из соображений ясности кода определим его в отдельном файле data_point.py.

from __future__ import annotations
from typing import Iterator, Tuple, List, Iterable
from math import sqrt


class DataPoint:
    def __init__(self, initial: Iterable[float]) -> None:
        self._originals: Tuple[float, ...] = tuple(initial)
        self.dimensions: Tuple[float, ...] = tuple(initial)

    @property
    def num_dimensions(self) -> int:
        return len(self.dimensions)

    def distance(self, other: DataPoint) -> float:
        combined: Iterator[Tuple[float, float]] = zip(self.dimensions,
                                                      other.dimensions)
        differences: List[float] = [(x - y) ** 2 for x, y in combined]
        return sqrt(sum(differences))

    def __eq__(self, other: object) -> bool:
        if not isinstance(other, DataPoint):
            return NotImplemented
        return self.dimensions == other.dimensions

    def __repr__(self) -> str:
        return self._originals.__repr__()

    Должна существовать возможность проверять каждую единицу данных на равенство другим единицам данных того же типа (__eq__()), а также выполнять удобочитаемый вывод единицы данных при отладке (__repr__()). Каждый тип единиц данных имеет определенное количество измерений (num_dimensions). В кортеже dimensions хранятся фактические значения для каждого из этих измерений в виде чисел типа float. Метод __init__() принимает итерируемый объект, содержащий значения нужных измерений. Впоследствии эти измерения могут быть заменены с помощью k-средних на z-оценки, поэтому мы также сохраняем в _originals копию исходных данных для последующего вывода.

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

    Эта версия distance() очень компактна и будет работать с типами DataPoint, имеющими любое количество измерений. Вызов zip() создает кортежи, заполненные для каждого измерения парами из двух точек, объединенных в последовательность. Генератор списков (list comprehension) находит разность между точками, составляющими пару, для каждого измерения и вычисляет квадрат этого значения. Функция sum() складывает все эти значения, итог, возвращаемый функцией distance(), является квадратным корнем из данной суммы.

    На следующем шаге мы рассмотрим агоритм кластеризации k-средних.

Предыдущий шаг Содержание Следующий шаг