machine-learning - 提取手写数字的属性以加强最近邻算法

Question

我有三个手写数字的 1024 位长二进制表示:0、1、8。 基本上，在一个数字的 32x32 位图中，行被连接起来形成一个二进制向量。

每个数字有 50 个二进制向量。 当我们对每个数字应用最近邻时，我们可以使用汉明距离度量或其他一些，然后应用算法来区分向量。 现在我想使用另一种技术，而不是查看向量的每一位，我想在比较向量时分析较少的位数。

例如，我知道当比较数字“8”和“0”的位图(大小:1024 位)时，我们必须在数字“8”的向量中间有 1，因为数字 8 在视觉上显示为放置在列中的两个零的组合。 所以我们的算法会寻找两个零的交集(这将是数字的中间。

这就是我想要的工作方式。我想将低级表示(查看 1024 位图矢量)转换为高级表示(由从位图中提取的两个属性组成)。

有什么建议吗？我希望听众对这个问题有所了解。

Answer 1

思路一:洪水填充

这个想法不使用每个数字的 50 个模式:它基于这样的想法，即通常“1”的所有 0 位都连接在“1”形状周围，而“0”将 0-它内部的位与外部的位，“8”有两个这样的封闭区域。因此，计算 0 位的连接区域将确定它是三个中的哪一个。

所以你可以使用 flood fill algorithm ，从向量中的任何 0 位开始，并将所有连接的 0 位设置为 1。在一维数组中，您需要注意正确识别连接的位(水平:相隔 1 个位置，但不跨越 32 边界，或垂直......相隔32个位置)。当然，这种泛滥会破坏图像 - 所以一定要使用副本。如果在一个这样的泛洪填充之后仍然有 0 位(因此它们没有连接到你变成 1 的那些)，那么选择其中一个并在那里开始第二次泛洪填充。如有必要，请重复。

当所有位都以这种方式设置为 1 时，使用您必须执行的泛洪填充次数，如下所示:

1. 一个洪水填充？它是一个“1”，因为所有的 0 位都是相连的。
2. 两次填充？这是一个“0”，因为零的形状分隔了两个区域(内部/外部)
3. 三个洪水填充？这是一个“8”，因为这种形状将三个相连的 0 位区域分开。

当然，此过程假设这些手写数字格式正确。例如，如果一个 8 字形有一个小间隙，如下所示:

..那么它不会被识别为“8”，而是“0”。这个特殊问题可以通过识别 1 位的“松散端”(停止的“线”)来解决。当你有两个距离很近时，然后将你从 flood-fill 计数中得到的数字增加 1(就好像这两个末端是相连的)。

类似地，如果一个“0”不小心有一个小的第二个循环，就像这里:

...它将被识别为“8”而不是“0”。您可以通过要求每个泛洪填充找到最少数量的 0 位(例如至少 10 个 0 位)来算作一个来防止这个特殊问题。

思路2:概率向量

对于每个数字，将您拥有的 50 个示例向量相加，这样对于每个位置，您都有一个介于 0 到 50 之间的计数。每个数字都有一个这样的“概率”向量，即 prob0、prob1 和 prob8。如果 prob8[501] = 45，这意味着“8”向量极有可能 (45/50) 在索引 501 处有一个 1 位。

现在按如下方式转换这 3 个概率向量:不是存储每个位置的计数，而是按计数(概率)递减的顺序存储位置。因此，如果 prob8[513] 具有最高值(如 49)，那么新数组的开头应该类似于 [513, ...]。我们称这些新向量为 A0、A8 和 A1(对应数字)。

最后，当您需要匹配给定的输入向量时，同时遍历 A0、A1 和 A8(始终查看三个向量中的相同索引)并保留 3 个分数。当输入向量在A0[i]中指定的位置有一个1时，则将score0加1。如果它在 A1[i] 中指定的位置也有一个 1(相同的i)，则将 1 加 1 到 score1。 score8 也一样。增加 i，然后重复。一旦你有明显的赢家，即当 score0、score1 和 score8 中的最高分与其中第二高分超过阈值差异时，立即停止此迭代。那时你知道代表的是哪个数字。