用于整数精确拟合的数据挖掘

Question

用于整数精确拟合的数据挖掘

algorithmdata-mining

4

我经常处理RFID卡。不同的读卡器有不同的输出和相同类型的卡片编码方式也不同。我经常被要求找出（如果可能的话）如何将一个输出转换为另一个，这意味着我必须盯着这些数字并找出它们的转换方法。

最常见的转换方法是：

添加常数
反转二进制序列
去掉一些位
旋转
以上方法的组合

我通常成功率约为30％，但当几个小时后我仍然无法找到翻译时，我会感到沮丧。这可能非常简单，但我就是想不出来。这就是为什么我正在寻找一种算法/库/软件，它可以自动检查两组数字上的这些规则，并尝试找出最小的Kolmogorov复杂度。

由于我对数据挖掘一窍不通，所以我会感激任何指导。

- Luka Rahne

你有没有一种方法可以为给定的目标生成相对较大的数据集？例如，逐步增加单个字段的值？同一类型的所有RFID卡是否编码相同的字段，还是有些是可选/专有的？ - datageist

最大二进制长度为52位，但大多数情况下为32位或更少。客户使用旧系统，他们有一个包含2k+用户的数据库，而我所得到的只是这个数据库、几张卡片以及这些卡片在他们的数据库中是如何存储的。在所有情况下，客户都可以手动输入这么多的卡片，但他们想要自动化这个过程，而我需要找到这个转换的方法。我需要一些能够自动运行并且能够找到简单翻译或返回无法找到任何逻辑的东西。 - Luka Rahne

3个回答

1

我不知道这些数字的长度，但假设它们是64位。那么不同非平凡原子变换的数量如下：

Added constant      2**64 - 1
Reversal            1
Remove bits         63
Rotation            63

如果您也有组合，那么您有4 + 12 + 24 + 24 = 64种不考虑变换参数的子集排列方式。因此，我会这样做：

有一个外循环，迭代64种组合变换的方式
然后有一个内循环，迭代最大63 * 63个“删除位”和旋转的参数值；现在总迭代次数为~~ 64 ³ == (2 ⁶) ³ = 2 ¹⁸，这还可以接受。
应用假设的变换（2 ¹⁸中的一种），然后计算第一个数据集与第二个数据集之间的差异；如果差异是常数，则找到了“添加常数”变换的加法常数，并完成了。

这应该在现代PC上非常快，即您应该能够在几秒钟内找到解决方案。如果数据集很大（> 100），您可以先使用样本，然后仅在子集正确时才对整个数据集进行验证结果。

- Antti Huima

0

我写了一个小的概念验证。这是我所做的。

我生成了十个随机的二进制字符串，每个有64位数，作为参考读卡器产生的卡内容示例。

0010110111011011100000010001100011111001010100111101110111000100
0000000110001111101110001011110100000100111101100100110010100000
1111000010100111011000111000100111111001000010100101011100011001
0010011011100011001000010111100010110001001000010101001110000000
1111000100101100010011101011010011100111000000001111110010101110
0101011101000101110111000010100110000111001010000010000001110111
0101110010011010011110011110111100111001110010100111101001111101
0101110100100101110000101000001000011100010100010010110000010001
0111101011011010111001011011110101011100111011010111100110100101
0000101001000110111101000100111011110000000011010110001110101011

然后我生成了一个随机映射表，模拟另一个读卡器对同样的十张卡片的不同输出。它的格式为i -> j，表示参考内容中的位i在另一个读卡器上出现为位j。

 4 ->  0   4 ->  1  49 ->  2  32 ->  3  51 ->  4  52 ->  5  10 ->  6  47 ->  7
16 ->  8  32 ->  9  14 -> 10  24 -> 11  13 -> 12   1 -> 13   8 -> 14  47 -> 15
12 -> 16  56 -> 17  55 -> 18  22 -> 19   6 -> 20  33 -> 21  22 -> 22  45 -> 23
37 -> 24  39 -> 25  46 -> 26  47 -> 27  25 -> 28  15 -> 29  43 -> 30  13 -> 31
33 -> 32  31 -> 33  16 -> 34  49 -> 35   0 -> 36  30 -> 37  28 -> 38  31 -> 39
45 -> 40  28 -> 41  17 -> 42  18 -> 43  40 -> 44  18 -> 45  23 -> 46  54 -> 47
11 -> 48  54 -> 49  41 -> 50  39 -> 51  28 -> 52  31 -> 53   1 -> 54  34 -> 55
45 -> 56   4 -> 57  59 -> 58  11 -> 59   6 -> 60  26 -> 61  21 -> 62   0 -> 63
52 -> 64   1 -> 65  55 -> 66  46 -> 67  49 -> 68  23 -> 69  47 -> 70  45 -> 71
28 -> 72  23 -> 73  41 -> 74  41 -> 75  16 -> 76   4 -> 77   4 -> 78  18 -> 79

例如，其他读卡器输出的第一位和第二位等于参考读卡器输出的第四位。模拟输出宽度为80位，有一些位重复，可能还有一些位缺失。

11111101111000111110010001110110101100100100001010111001010100001011111011111110
00100100101110101100000110100111011100111101110000101100100001001001100110111001
00111010011111100011011001100101110110110111011101011111001000010111110011000001
00111011011000110110100001011100000100100101011101011001000011000010111011000001
00111110010111001101011011000001100110000010000000010011000001111100100000000000
00010000110011000000100011000101011000110110000000011110001011100100000010001000
11101100001101101000000001101000010101110111111111111111011101001101110011110111
11000111100111010001001010010111001001000010000000100010011000001100001000111110
11101101101101111110110110010000111100111111111010101110110111101110111111111111
11110001111010010110110100011001101101101111010101001001110010100010101110001111

现在我们想要找到两个数据集之间的映射关系。为此，我们只需查看位之间的相关性。这意味着对于由参考读取器产生的位索引 i（0 到 63）和由其他读取器产生的位索引 j（0 到 79）的每个组合，我们只需计算有多少个示例在这些位置上具有匹配的位。

             111111111122222222223333333333444444444455555555566666
   0123456789012345678901234567890123456789012345678901234567890123

 0 3545.65456386363765535465634568436588433683666585575745656555647
 1 3545.65456386363765535465634568436588433683666585575745656555647
 2 4474534385457494458444376567873567875326554355654.48656783626534
 3 64743565476336564544465525456333.7853368114353456646256765446574
 4 669655438567727425624459656765356787734855435365684.656765446734
 5 4656752763479454654464558367475525457744794735656666.72365644734
 6 8676354543.33636254244956545235365655566334533456446476543266354
 7 33638674585643657453154636365462565864334656463.5555545874333445
 8 2434756747255656.54646334345655545255742576757474462652565642556
 9 64743565476336564544465525456333.7853368114353456646256765446574
10 33636452963663.5549533285656964656786215665466763937547874535425
11 685853256165765447646475.365475725457744774555634666874343666536
12 6636334723613.36674666716343455565433764334555434462474343666376
13 6.5.554543655634494466758363455745457766554373434486654325686758
14 44745543.5477296438442396567853745677326776555854828656765444514
15 33638674585643657453154636365462565864334656463.5555545874333445
16 556564367438.363545575467478584636546655885646747757963476735843
17 42725365674574746364463545696733676535445565374768466547.3604552
18 5383647278564385547315483636744478786235445466585737347.74335445
19 9767443632944725363355.47434146456546675443644547355585434377465
20 445455.349453454656648352765655565453564538377274464216765644576
21 758562545656656356533766543656447.766455443466567757565874537665
22 9767443632944725363355.47434146456546675443644547355585434377465
23 534362745636656374775744565658663634465186766.565553545674735465
24 5747445834546725763577627276364634124.73667646345373761254753665
25 667637456565545625446457456563358585536.334351636648456547466754
26 6454552583477476436662576545655745657346774755.36626676547466534
27 33638674585643657453154636365462565864334656463.5555545874333445
28 5343667256564363347755463.54568454764255645466565555329656557465
29 445437476563365.634442554345613563455546356733654424474545262334
30 5343663854566547723553645436346434346653685.26767333783456353443
31 6636334723613.36674666716343455565433764334555434462474343666376
32 758562545656656356533766543656447.766455443466567757565874537665
33 5747445474366565567775467474764.34346655867486723555545436775647
34 2434756747255656.54646334345655545255742576757474462652565642556
35 4474534385457494458444376567873567875326554355654.48656783626534
36 .676334543855634254466956545255567635586534555638446476545468574
37 552586543456454356575564583236.434566453663666565373547436577467
38 2454556387255496658644174565.53765675326556375652846436765644536
39 5747445474366565567775467474764.34346655867486723555545436775647
40 534362745636656374775744565658663634465186766.565553545674735465
41 2454556387255496658644174565.53765675326556375652846436765644536
42 59496454345447435.5557647452566656566655443284343595545434777669
43 445453618545549445.644376765875745675324756377652846438763646336
44 5545645474388363547775467676586814346653.87668745555745456755645
45 445453618545549445.644376765875745675324756377652846438763646336
46 55856652965861853473334.5656744656788237665464765739547856355625
47 645455616565347425864457494365756587514653437565464623.745468356
48 55658654763.8163545555485656566636568455885666767557745658555845
49 645455616565347425864457494365756587514653437565464623.745468356
50 35458636743883657455534674565666143686338.5846765555963456553625
51 667637456565545625446457456563358585536.334351636648456547466754
52 2454556387255496658644174565.53765675326556375652846436765644536
53 5747445474366565567775467474764.34346655867486723555545436775647
54 6.5.554543655634494466758363455745457766554373434486654325686758
55 6474554365655474256444574745655387.75148332353656848458765448554
56 534362745636656374775744565658663634465186766.565553545674735465
57 3545.65456386363765535465634568436588433683666585575745656555647
58 68385745436536364746647565414377434575665545736342644563074.6558
59 55658654763.8163545555485656566636568455885666767557745658555845
60 445455.349453454656648352765655565453564538377274464216765644576
61 46563565654574544566863565.7673743433766758355434666634365844754
62 665653852745563267466.534565475567433784536377256484434565846796
63 .676334543855634254466956545255567635586534555638446476545468574
64 4656752763479454654464558367475525457744794735656666.72365644734
65 6.5.554543655634494466758363455745457766554373434486654325686758
66 5383647278564385547315483636744478786235445466585737347.74335445
67 6454552583477476436662576545655745657346774755.36626676547466534
68 4474534385457494458444376567873567875326554355654.48656783626534
69 55856652965861853473334.5656744656788237665464765739547856355625
70 33638674585643657453154636365462565864334656463.5555545874333445
71 534362745636656374775744565658663634465186766.565553545674735465
72 2454556387255496658644174565.53765675326556375652846436765644536
73 55856652965861853473334.5656744656788237665464765739547856355625
74 35458636743883657455534674565666143686338.5846765555963456553625
75 35458636743883657455534674565666143686338.5846765555963456553625
76 2434756747255656.54646334345655545255742576757474462652565642556
77 3545.65456386363765535465634568436588433683666585575745656555647
78 3545.65456386363765535465634568436588433683666585575745656555647
79 445453618545549445.644376765875745675324756377652846438763646336

以上是使用点表示十个匹配项的结果。可以看到，这恢复了除第13、54和65位之外的所有位的映射，其中发现了两个可能的匹配项。

80位中有77位只用了十个样本就相当不错了。诚然，如果位模式包含结构或不仅仅是随机位，或者必须考虑从多个位计算出的位，则效果不会那么好。但是，如果您可以访问足够大的样本集，则可以发现所有可能的映射。

- Daniel Brückner

不错的概念，但添加如何处理？这也可能通过异或运算来实现。会尝试并报告。 - Luka Rahne

添加数字是最简单的情况，因为它们在所有样本中都相等。您可以在预处理步骤中检测它们，或者只需向参考输入添加固定模式 01 并将添加的两个位与此关联。当然，您也可以处理倒置位或从多个参考位计算出的位。为此，您不仅需要计算位与一个参考位之间的相关性，还需要计算位与所有可能的 n 个参考位组之间的相关性。将 n 设置为二将揭示取决于两个参考位的位 - 例如 and、or 和 xor。 - Daniel Brückner

将n设置为三将揭示取决于三个参考位的位，以此类推。但增加n将迅速需要更多的样本才能可靠地检测到潜在函数。例如找到一个位作为奇偶校验，几乎是不可能用这种方法实现的。 - Daniel Brückner

我表达不够清楚，我的意思是加法/求和。添加常量可能会改变多个位。我明白了如何处理附加。 - Luka Rahne

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Joe Koberg · Accepted Answer

这似乎是一个遗传编程问题。

"基因"是可以发生的单个位变换。适应性函数是输入集合中正确转换的位数。遗传编程库可以重新排列基因，试图找到更好的适应性，并通过“繁殖”具有高适应性水平的个体来尝试创建更适合的个体。

请查看pyEvolve。