使用 F# 进行 K-means

Gaston Verelst

5.00/5 (10投票s)

2019年2月28日

CPOL

14分钟阅读

22041

如何使用 F# 实现 K-means 等算法。

引言

假设我们想对一些数据进行分组。每个数据元素都有一些（数值）属性。使用这些属性，我们想将数据分成不同的簇。对我们人类来说，这通常可以通过查看数据来完成。但对于计算机来说，这更难确定。

当然，只有当数据维度不多、数据集不大、簇的数量有限时，我们（人类）才能“看到”这一点。当数据变得更复杂时，我们就需要计算机了。

本文的代码可以在 https://github.com/GVerelst/ArtificialIntelligence 找到。

本文的前提条件

这篇帖子中的示例代码是用 F# 编写的，因此需要一些该语言的知识。网上有很多学习资源，我在结尾的参考部分列出了一些比较好的。对 |> 运算符有很好的理解将会有所帮助。

聚类的例子有哪些？

电子商务

我们可以有一个电子商务网站，其中包含每个人的销售历史。也许了解顾客是否是爱好者，这样我们就可以推荐一些电动工具。或者他们之前订购了很多 DVD，这样我们就可以向他们推荐特定的 DVD（或 DVD 播放器）。

对于 DVD，我们可能能够找出该顾客感兴趣的类型，并向该顾客推荐更有趣的商品。

图像压缩

位图由 RGB 值组成。这些值有时只是略有不同，人眼看不出来。但是，如果我们能将数百万种颜色聚类成大约 100 种不同的颜色，我们或许就能压缩位图的大小。或者我们也许能从中发现图像中的形状。

算法是如何工作的？

让我们从在一维线上聚类点开始。

算法的输入是

点的值
我们想要的簇的数量。这是 k-means 中的 k。此算法只会尝试创建 k 个簇，其中 k 由调用者确定。可以尝试使用不同的 k 值运行算法，然后找到最佳方法，但这超出了本文的范围。

进一步的输入可以是

我们将如何计算点之间的距离？
如果您希望结果可重复：随机数生成器的种子值。

使用函数式语言，这可以通过将正确的函数传递给算法轻松完成。

下面，我们看到一条线，点位于 { 1, 2, 3, 7, 8, 10, 11, 15, 16, 18 }

我们想将其分成 3 个簇（k = 3）。观察这条线，我们发现最终可能会得到簇 { 1, 2, 3}、{ 7, 8, 10, 11 } 和 { 15, 16, 18 }。

K-Means 聚类步骤

将所有点分配到随机簇，确保没有簇是空的。
循环
- 计算每个簇的质心
- 将点重新分配到最近的质心
直到没有变化为止

这是优化问题的典型流程。首先分配随机值，然后进行精炼，直到找到一个好的解决方案。

什么是“质心”？

质心通常是每个簇的“平均值”。当我们讨论单个值时，这意味着计算每个簇中值的平均值。当每个项有更多属性时，我们希望计算每个属性的平均值。例如，在一个簇 C 中，我们有点 {x, y}。质心将是具有以下值的点

x = 簇中所有 x 值的平均值
y = 簇中所有 y 值的平均值

“最近”是什么意思？

一个点到另一个点的最近点是距离该点最近的点。

对于每个点，我们将计算其到每个质心的距离，然后将该点分配给最近质心的簇。

有效的距离 d(x, y) 意味着

正值。 $d(x, y) \ge 0$。 $d(x,y) = 0$ 仅当 $x = y$
对称性。 $d(x,y) = d(y,x)$
三角不等式。 $d(x,y) + d(y,z) \ge d(x,z)$

计算两点之间的距离有几种不同的方法。我们将创建一个单独的函数来计算距离。

在我们的例子中，我们可以使用 $\left | x-y \right |$。或者，我们也可以使用 $\sqrt{\left ( x-y \right )^{2}}$，这总是可行的。这使我们更接近欧几里得距离。

当我们想计算两点之间的距离时，我们得到

$d \left( \left( x_{1},y_{1} \right ),\left ( x_{2},y_{2} \right ) \right )=\sqrt{\left ( x_{1}-x_{2} \right )^{2}+\left ( y_{1}-y_{2} \right )^{2}}$

这可以推广到更多属性。

对于聚类算法，我们不关心确切的距离，我们只关心哪个质心离一个点更近。因此，没有必要计算（昂贵的）平方根。

在维基百科上，有详细的解释： https://en.wikipedia.org/wiki/Distance

对于我们的算法，我们不需要计算平方根，因为我们不关心两点之间的确切距离。我们只关心哪个质心离一个点最近。

让我们用我们到目前为止学到的知识来详细分析这个例子

迭代 0（初始化）

这是与之前相同的数据集，随机分为三个簇：橙色、黄色和绿色。现在我们为每个簇计算质心

我在下面的图表中添加了质心。它们位于最上面的线上。

迭代 1

接下来要做的是找出每个点离哪个质心最近。对于每个点，我们现在计算它到所有质心的距离，然后将该点分配给最近质心的簇。这就得到了下面的图

我们可以看到情况有所改善，质心也在移动。橙色簇目前只有一个元素，但这会改变。

迭代 2

迭代 3

这是最终解决方案。算法计算了新值，但它们与之前的值相等。因此，这是最佳解决方案。

要理解代码，您需要了解 F# 的哪些知识

管道运算符 |>

当我们在代码中看到

let centroids = values |> calcCentroids

这与以下内容相同

let centroids = calcCentroids values

我们可以这样理解：values 集合被传递给 calcCentroids 函数。

当管道中只有一个函数时，这不是很实用（主要是个人偏好和代码一致性的问题），但看看我们如何调用算法，这开始变得有意义了

getValues |> assignRandomClusters k |> algo calcIntDistance |> showClustered

我们将 getValues 的输出作为第二个（隐藏）参数传递给 assignRandomClusters 函数。然后，该函数的输出被传递给 algo 函数（隐藏参数），最后，algo 的输出被传递给 showClustered（隐藏参数）。

以这种方式组织代码可以立即清晰地展示所有步骤。它比以下方式更具可读性

showClustered (algo calcIntDistance (assignRandomClusters k getValues))

列表

通常，函数式语言使用不可变列表。有很多函数可以用来处理列表中的元素，通常是同时处理整个列表。这就解释了为什么我们不需要循环。

其中一些函数是

List.iter

示例

values |> List.iter (printfn "%A")

对于每个列表项，将调用过程 (printfn "%A")。

List.map

xs |> List.map (fun y -> {x = y; cluster = random.Next(k)} )

对于每个列表项，将调用函数。将返回一个包含函数结果的新列表。

List.groupBy

rows |> List.groupBy(fun r -> r.cluster)

这将返回一个列表的列表，每个列表对应于 r.cluster 的不同值。

我使用了一些额外的函数，但它们都是不言自明的。

创建项目

我使用 Visual Studio 2017 创建了这个项目

文件 > 新建 > 项目…
选择 **其他语言** > **Visual F#** > **.NET Core** > **控制台应用程序 (.NET Core)**
给项目起一个好名字和位置，然后单击 **确定**。将创建一个新的 F# 项目。

展示代码！

此示例的代码只有 55 行 F#。如果您要从 Github 下载代码，您会发现实际上有 68 行。这是因为我还提供了一个简化的 algo 函数版本。您可以在此处找到算法的实现。

数据结构

[<StructuredFormatDisplay("[x:{x}, c:{cluster}]")>]
type Row =
    {
        x: float;
        cluster: int;
    }

这是数据行。在这种情况下，它只包含一个 float x 作为数据项，如前所述，它所属的簇。StructuredFormatDisplay 属性使 printfn 函数以美观的方式输出 Row。

为了使代码简单，我创建了一个包含 1 个数据点（x）的 Row。为了使其更通用，我们可以将其更改为 float list。这将允许每行有多个值。

我做的第二个设计选择是保留簇与数据。另一种可能性是为每个簇创建一个新列表。

演示函数

showData

让我们从 showData 函数开始，它是微不足道的

let showData values =
    values |> List.iter (fun r -> printfn "%A" r)

它遍历集合并在新行上打印每个元素。

如果您想更简洁地编写它，那么您可以使用柯里化

let showData values =
    values |> List.iter (printfn "%A")

这将以相同的方式输出集合。请注意 showData 的数据类型未指定。这使得函数成为多态的。这就是 StructuredFormatDisplay 的用武之地。

showClustered

showClustered 函数输出相同的列表值，但按簇分组。

let showClustered values =
    values |> List.groupBy(fun r -> r.cluster)
           |> List.iter(fun (c, r) -> 
                printfn "Cluster %d" c 
                r |> showData)

初始化随机数生成器

let random = new Random(5);

我使用的是种子值为 5 的 Random。这将始终生成相同的随机数序列，因此程序的输出将是相同的。在实际应用中，这不是必需的，您可以实例化一个不带参数的 Random。

let getValues = [ 1.0; 2.0; 3.0; 7.0; 8.0; 10.0; 11.0; 15.0; 16.0; 18.0; ]

此函数返回数据。对于演示程序，数据是一个硬编码列表。数据也可以从文件中读取，这更现实。

辅助函数

现在基础工作已经完成，我们可以开始实际实现。

calcIntDistance

let calcIntDistance t u = Math.Abs(t.x - u.x)

此函数用于计算质心与数据点之间的距离。我选择了一个非常简单的实现，如您所见。此函数将作为参数传递给算法，以便可以轻松替换。当行有更多属性需要考虑时，这将是必要的。

assignRandomClusters

此函数将原始数据集分成 k 个随机簇。使用 F# 可以使此函数成为一行代码。它所做的只是将每个元素 (x) 映射到一个新的 Row，以及一个介于 0 和 k-1 之间的随机数。如果您想使其更可靠，可以验证没有簇是空的。我已经实现了这个测试在 KmeansGeneric 模块中。

let assignRandomClusters k xs =
    xs |> List.map (fun y ->= y; cluster = random.Next(k)} )

k 作为参数传递。这是我们唯一需要知道簇数量的地方。

calcCentroids

let calcCentroids rows =
    rows |> List.groupBy(fun r -> r.cluster)
         |> List.map(fun (c, r) -> 
                    { 
                        x = r |> List.averageBy (fun x -> x.x);
                        cluster = c
                    })

您猜对了，此函数将计算每个簇的质心。步骤是

rows |> List.groupBy 将按簇分割行集合。结果是列表的列表。
List.map 将计算每个簇的质心。这意味着取簇行中的平均值并加上簇号。

F# 再次以其简洁性闪耀！

实际算法

现在所有辅助函数都已就位，实际计算簇所剩无几。

let rec algo calcDistance values =
    printfn "\nLoop"
    values |> showClustered
    printfn "Centroids"

    let centroids = values |> calcCentroids
    centroids |> showData

    let values' = values |> List.map (fun v -> 
            let shortest = centroids |> List.minBy(fun c -> calcDistance c v)
            { v with cluster = shortest.cluster }
        )

    if values = values' then values'
    else algo calcDistance values'

因为这是一个演示程序，其中包含一些在生产程序中会省略的输出。algo 函数中的步骤是

使用 calcCentroids 函数计算质心
对于 values 中的每一行。找到最近的质心并将其分配给该行。更准确地说，我们实例化一个带有新簇值的新行。实际计算是一个管道，其中我们
- 计算所有值的质心（实际上是带有当前分配簇的数据）
- 对于每个质心，我们计算到当前点 v 的距离
- 然后我们找到这些值中的最小值。这就是 v 现在将所属的簇。
测试新计算的值与原始值之间是否存在变化。如果没有变化，我们就完成了，否则我们将 values 重新发送回算法。

对于更简洁的版本，更多地利用 |> 运算符

let rec algo calcDistance values =
    let values' = values |> List.map (fun v -> 
            let shortest = values |> calcCentroids 
                                  |> List.minBy(fun c -> calcDistance c v)
            { v with cluster = shortest.cluster }
        )

    if values = values' then values'
    else algo calcDistance values'

使用算法

调用 algo 函数

getValues |> assignRandomClusters k |> algo calcIntDistance |> showClustered

在此管道中，我们

获取要聚类的值
将它们分配到随机簇，k 是簇的数量
调用递归聚类算法，其中 calcIntDistance 是计算两点之间距离的函数。这允许在需要时插入不同的函数。
最后，输出聚类数据。

实际的 k-means 算法是：assignRandomClusters k |> algo calcIntDistance

注意事项

算法并非完美，原因有几点。

一个簇可能会变空。这将意味着我们最终得到 n-1 个簇，这可能不是期望的结果。发生这种情况时，我们必须重新开始，使用新的随机值。
在极少数情况下，算法可能不会终止。为避免这种情况，我们必须传递一个参数来限制算法的迭代次数。对于 n 个元素的集合，此参数通常设置为 n²。
算法不是确定性的。根据初始簇值，可以找到其他簇组合。多次运行相同的程序可能会产生不同的结果。K-means 是一种优化解决方案，可能存在一个以上的（局部）最优解决方案。
因此，我们不确定是否找到了“最佳”解决方案。一种解决方案是衡量结果的聚类效果如何，然后多次运行算法。然后我们取所有解决方案中的最佳。这超出了本文的范围。
数据未标准化。由于行中只有一个值，这不成问题。当一行包含多个值（例如 x 和 y），其中 x 的值在 0 到 1 之间，而 y 的值在 40000 到 50000 之间时。计算两行之间的距离几乎会忽略 x 值。这可以通过对 x 和 y 进行标准化，使它们落在相同的数据范围内来解决。

扩展此示例

我们做了一个简单的例子，其中行只有一个属性 x。要将其扩展到平面中的聚类，您可以添加一个属性 y。除了 Row 类型和 getValues 函数之外，只有两个地方需要修改代码

您需要一个新的 calcDistance 函数，使用 x 和 y 来计算距离。
在 calcCentroids 函数中，您还需要分配 y 值。

通过使 Row 类型更通用，这两个问题都可以解决，但为了简单起见，我将其保留原样。

结论

聚类是一个优化问题。通常，这些问题是通过首先生成一个随机解决方案，然后将其精炼成一个可接受的解决方案来解决的。从不能保证解决方案是完美的。

F# 是一种实现此类算法的绝佳语言，因为它简洁、类型推断和不变性。

我实现了一个算法的更通用版本，它使用数据行中的浮点数列表，而不是只有一个 x。这意味着代码会进行一些更改。

calcListDistance 实现为平方和
calcCentroids 变得更复杂，但本质上做的是同样的事情
一些细节上的调整。

我提供了代码，但由于只是一些细节变化，我将不再进一步讨论。请参阅 https://github.com/GVerelst/ArtificialIntelligence/blob/master/ArtificalIntelligence/KmeansGeneric.fs。

参考文献

左键单击 gadget 并拖动以移动它。左键单击 gadget 的右下角并拖动以调整其大小。右键单击 gadget 以访问其属性。

https://en.wikipedia.org/wiki/Distance
https://quoteinvestigator.com/2010/12/07/foul-computer/ - 关于本文开头引言的作者

K-Means 算法

https://www.syncfusion.com/ebooks/machine - 关于机器学习的免费电子书
K-means & Image Segmentation - Computerphile
StatQuest: K-means clustering
12. Clustering

F#

https://fsharpforfunandprofit.com/ 这是 F# 的参考！
- https://fsharpforfunandprofit.com/posts/function-composition/ 在代码中，我大量使用了 F# 管道 (|>)。您可以在此处了解更多关于它的信息。
- https://fsharpforfunandprofit.com/posts/designing-with-types-single-case-dus/ 对用于描述 Row 类型的联合类型进行了说明。

历史

2019年2月28日：初始版本