algorithm - 使用 Haskell 进行最近邻和模式识别

Question

这是我拥有的 3 个数据集的简化版本:

Set A = [1, 1, 2, 2, 1, 2, 2, 1]
Set B = [2, 2, 1, 2, 2, 1, 1, 3]
Set C = [8, 4, 4, 4, 4, 9, 8, 4]

Haskell 是否具有用于查找数据集之间未指定模式的任何内置功能？我想在 2 个或更多数据集上运行我的程序，并让它报告哪些是相似的，在这种情况下，将是集合 A 和 B。

Answer 1

如果您不是在谈论寻找结果交集。

对于每 2 个列表，我们可以使用 Data.List 中的 intersect 函数，它取它们的交集。

因此，想法是计算所有列表的交集并对其进行排序。

> snd . last . sort $ [ (length $ intersect x y, (x,y)) | let list = [[1,1,2,2,1,2,2,1],[2,2,1,2,2,1,1,3],[8,4,4,4,4,9,8,4]], x <- list, y <- list, x /= y ]
([1,1,2,2,1,2,2,1],[2,2,1,2,2,1,1,3])

如果您有兴趣建立后续交集，您可以使用类似的东西:

import Data.List (sort, subsequences)

intersectCons :: (Ord a) => [a] -> [a] -> [a]
intersectCons x y = snd . last . sort $
  [ (length x1, x1) | x1 <- subsequences x
                    , x2 <- subsequences y
                    , x1 == x2 ]

例如:

> intersectCons [1, 1, 2, 2, 1, 2, 2, 1] [2, 2, 1, 2, 2, 1, 1, 3]
[2,2,1,2,2,1]

我们也可以用它来寻找最相似的列表对:

> snd . last . sort $ [ (length $ intersectCons x y, (x,y)) | let list = [[1,1,2,2,1,2,2,1],[2,2,1,2,2,1,1,3],[8,4,4,4,4,9,8,4]], x <- list, y <- list, x /= y ]
([2,2,1,2,2,1,1,3],[1,1,2,2,1,2,2,1])

实际上，如果您不仅要获得一对列表，而且要获得所有“相似”的对，您可以删除 snd 。最后的 。对 $ 进行排序并获取所有这些。