聚类算法和 "extending" 聚类以包括 N 个最近的邻居
Clustering algorithm and "extending" clusters to include N nearest neighbours
这听起来像是一个微不足道的问题，但我在网上找不到任何东西。
我们有一组元素a b c d e。对于那些元素，成对距离被定义。每个元素都需要处理。为了处理一个元素 - 需要它的 N 个最近的邻居。
问题：如何将这些元素分成大小大致相等的 M 个集合，然后扩展这些集合，以便集合中的每个元素在扩展中都有 N 个最近的邻居放。这可用于原始元素的并行处理。
我正在使用 Spark - 但这可能可以抽象为任何并行计算。
这是一个例子：
We have following elements, the distance between them is just their difference.
N = 4 # number of nearest neighbours required for the computation
M = 2 # desired number of clusters
elements:
1 2 3 4 5 6
basic clusters:
1 2 3
4 5 6
extended clusters:
1 2 3 (4 5)
4 5 6 (2 3)
这个怎么称呼，是否有解决此类问题的通用方法？我的理解是严格来说这不是 clustering.
此算法（聚类 + 扩展）将在单个节点上 运行，然后大量数据将在分布式系统中加入和处理。
第一步，可以测试一个简单的贪心算法。
我的感觉是确定重叠（扩展）集，然后确定非扩展集更符合逻辑。
让我们 select K (= M ?) 点与所有其他点尽可能远。
我在这里假设 selecting 这样的极值点是可行的，在你的例子中 1 和 6。
请注意，初始点数可能低于 M。
- 这些初始点Pi决定了K集合Si。
- 然后，每个Si由Pi的需要的邻居完成。
- 对于每个集合，我们可以确定具有足够邻居的点数。
- 如果K < M，我们可以确定M-K个点尽可能在之前的集合中，并用这些点和它们的邻居建立新的集合。
- 如果所有的点和它们的所有邻居都在一个集合中：停止。
- Select 具有最少 满意 点数的集合，即与所有邻居。在此集合中，确定缺失邻居数量最少的点。 Select随机这样一个点，用这个点缺失的邻居完成集合
- 转到第 3 步，直到满足停止条件。
一个变体是继续这个过程，直到每个集合都有所需数量的满意点。
每个随机过程可能会提供不同的解决方案。可以在不同节点上并行执行多次尝试。
在您的简单示例中，该过程会立即提供解决方案：
- S0 = {1} -> S0 = {1, 2, 3, 4, 5}
- S1 = {6} -> S1 = {6, 5, 4, 3, 2}
可能会出现两个不同的集合有相同的满足点。即使这一点必须保留在每个扩展集中，它也可以从 non-extended 集
之一中删除
该算法的一个理由：我理所当然地认为极值点必须在不同的 non-extended 集合中。这意味着它们的邻居必须存在于相应的扩展集 Si 中。
这听起来像是一个微不足道的问题，但我在网上找不到任何东西。
我们有一组元素a b c d e。对于那些元素，成对距离被定义。每个元素都需要处理。为了处理一个元素 - 需要它的 N 个最近的邻居。
问题：如何将这些元素分成大小大致相等的 M 个集合，然后扩展这些集合，以便集合中的每个元素在扩展中都有 N 个最近的邻居放。这可用于原始元素的并行处理。
我正在使用 Spark - 但这可能可以抽象为任何并行计算。
这是一个例子：
We have following elements, the distance between them is just their difference.
N = 4 # number of nearest neighbours required for the computation
M = 2 # desired number of clusters
elements:
1 2 3 4 5 6
basic clusters:
1 2 3
4 5 6
extended clusters:
1 2 3 (4 5)
4 5 6 (2 3)
这个怎么称呼，是否有解决此类问题的通用方法？我的理解是严格来说这不是 clustering.
此算法（聚类 + 扩展）将在单个节点上 运行，然后大量数据将在分布式系统中加入和处理。
第一步，可以测试一个简单的贪心算法。
我的感觉是确定重叠（扩展）集，然后确定非扩展集更符合逻辑。
让我们 select K (= M ?) 点与所有其他点尽可能远。
我在这里假设 selecting 这样的极值点是可行的，在你的例子中 1 和 6。
请注意，初始点数可能低于 M。
- 这些初始点Pi决定了K集合Si。
- 然后，每个Si由Pi的需要的邻居完成。
- 对于每个集合，我们可以确定具有足够邻居的点数。
- 如果K < M，我们可以确定M-K个点尽可能在之前的集合中，并用这些点和它们的邻居建立新的集合。
- 如果所有的点和它们的所有邻居都在一个集合中：停止。
- Select 具有最少 满意 点数的集合，即与所有邻居。在此集合中，确定缺失邻居数量最少的点。 Select随机这样一个点，用这个点缺失的邻居完成集合
- 转到第 3 步，直到满足停止条件。
一个变体是继续这个过程，直到每个集合都有所需数量的满意点。
每个随机过程可能会提供不同的解决方案。可以在不同节点上并行执行多次尝试。
在您的简单示例中，该过程会立即提供解决方案：
- S0 = {1} -> S0 = {1, 2, 3, 4, 5}
- S1 = {6} -> S1 = {6, 5, 4, 3, 2}
可能会出现两个不同的集合有相同的满足点。即使这一点必须保留在每个扩展集中，它也可以从 non-extended 集
之一中删除该算法的一个理由：我理所当然地认为极值点必须在不同的 non-extended 集合中。这意味着它们的邻居必须存在于相应的扩展集 Si 中。