math - 计算两个相同数据集之间的汉明距离

Question

如何计算相同点的两个数据集之间的汉明距离？两个数据集看起来完全一样。
http://postimg.org/image/u11qnsolh/

有两个相同点数的数据集。
总点数-19

---

第一个数据集有 3 个集群。
集群 A 有 4 个点
集群 B 有 2 个点
集群 C 有 4 个点

其余点在集群之外

---

第二个数据集有 3 个集群。
集群 A 有 8 个点
集群 B 有 5 个点
集群 C 有 6 个点

Answer 1

首先，让我们索引点：

您对两组集合之间的汉明距离感兴趣：

L = { {1,2,3,4}, {5,6}, {7}, {8}, {9}, {10}, {11}, {12}, {13}, {14, 15,17,18}, {16}, {19} }

R = { {1,2,3,4,5,6,7,8}, {9,10,11,12,13}, {14,15,16,17,18,19} }

---

改编自[1]（第2节），将汉明距离推广到两个集合X，Y，距离可以定义为：

改编自[2]（3.4节），两组集合之间的并集和差集可以定义为：

和

所以在你的情况下：

L ⋃ R = { {1,2,3,4,5,6,7,8}, {9,10,11,12,13}, {14,15,16,17,18,19} }

L - R = { {} }

R - L = { {5,6,7,8}, {1,2,3,4,7,8}, {1,2,3,4,5,6,8}, {1,2, 3,4,5,6,7}，{10,11,12,13}，{9,11,12,13}，{9,10,12,13}，{9,10,11,13} , {9,10,11,12}, {16,19}, {14,15,17,18,19}, {14,15,16,17,18} }

(LR) ⋃ (RL) = { {}, {5,6,7,8}, {1,2,3,4,7,8}, {1,2,3,4,5,6,8 }，{1,2,3,4,5,6,7}，{10,11,12,13}，{9,11,12,13}，{9,10,12,13}，{9 ,10,11,13}, {9,10,11,12}, {16,19}, {14,15,17,18,19}, {14,15,16,17,18} }

所以

|(左) ⋃ (右)| = 13

和

|左⋃右| = 3

所以 d(L,R) = 13 / 3 = 4.333

---

[ 1 ]将汉明距离推广到有限集以对异构对象进行分类 [Bezem, Keijzer, Volmac]

[ 2 ]概念模型中的模式匹配——一种形式化的多建模语言方法 [Delfmann, Herwig, Lis, Stein]