02-预备知识

选择背景色：黄橙洋红淡粉水蓝草绿白色选择字体：宋体黑体微软雅黑楷体选择字体大小：小中大特恢复默认

6.1　预备知识

聚类算法需要用到一些统计学原语（均值、标准差等）。自Python 3.4版开始，Python的标准库在 statistics 模块中提供了几种有用的基本统计操作函数。请注意，虽然本书沿用的是标准库，但是有更多高性能的第三方库可用于数值操作，如NumPy，因此在看重性能的应用程序中，应该充分利用这些第三方库，特别是那些处理大数据的应用程序。

为简单起见，本章中要处理的数据集都用 float 类型表示，因此会有很多对 float 列表和元组的操作。基本统计操作 sum() 、 mean() 和 pstdev() 在标准库中定义，对它们的定义直接来自统计学课本中的公式。另外，我们要用到一个计算z分数（z-score）的函数。具体代码如代码清单6-1所示。

代码清单6-1　kmeans.py

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 all zeros if there is no variation
        return [0] * len(original)
    return [(x - avg) / std for x in original]

提示 pstdev() 会求出整个种群的标准差，而这里未用到的 stdev() 会求出某个样本的标准差。

zscores() 会把一系列浮点数转换为列表，列表元素为每个浮点数相对于原序列中所有数值的z分数。关于z分数，本章后面会有更多介绍。

注意　对基础统计学知识的介绍已超出本书范围，不过对本章剩余部分而言，只要基本了解均值和标准差就足够了。如果你已有一段时间未接触而需要复习，或者以前从未学过这些术语，那么你可能需要花时间快速阅读一篇对这两个基本概念进行解释的统计学资料。

所有聚类算法都是对数据点进行处理的，k均值算法的实现也不例外。我们这里将定义一个名为 DataPoint 的通用接口。为整洁起见，我们将在 DataPoint 自己的文件中定义它。具体代码如代码清单6-2所示。

代码清单6-2　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均值算法最常用的方式就是欧氏距离（Euclidean distance）。这是几何课程中最为熟悉的距离公式，可由毕达哥拉斯定理推导出来。其实我们在第2章中讨论过该公式了，并推导出了该公式的二维空间版本，用于求出迷宫中任意两点间的距离。 DataPoint 所用的欧氏距离需要更复杂一些，因为一个 DataPoint 可能包含任意数量的维度。

这一版的 distance() 特别紧凑，适用于维度数量任意的 DataPoint 类型。这里调用 zip() 创建元组并组合成一个序列，元组里成对存放着两点的维度。列表推导式将求出每个点在各维度上的差并求出差的平方。 sum() 将这些值求和， distance() 返回的最终值是和的平方根。

Previous 上一篇本节目录 Next 下一篇

02-预备知识

6.1 预备知识

6.1　预备知识