K-表示群集高尔夫
K-表示群集高尔夫
提问于 2017-05-09 17:18:21
K-均值聚类(维基百科)
这里的任务相当简单，在二进制矩阵上执行k均值聚类算法的一次迭代。这基本上是主要的k-均值算法的设置任务，我觉得设置可能更容易，并诱使高尔夫语言给它一个机会。传递给您的矩阵格式如下：
0 0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0 0
0 0 0 0 0 1 0 0 1
0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0
0 1 0 0 0 1 0 0 0
0 1 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 01表示一个点，而0表示缺少点。您的工作将是随机生成k-1质心，并对您生成的质心数据执行初始聚类。k被定义为min(grid#Width, grid#Height)-1。每个质心的标记应该从2一直到k。例如，在这种情况下，您可以生成以下质心：
Centroid 2 was generated at: (1.0, 4.0)
Centroid 3 was generated at: (1.0, 5.0)
Centroid 4 was generated at: (5.0, 1.0)
Centroid 5 was generated at: (3.0, 3.0)
Centroid 6 was generated at: (0.0, 2.0)
Centroid 7 was generated at: (6.0, 6.0)
Centroid 8 was generated at: (2.0, 6.0)生成质心后，您必须遍历每个用1标记的点，因为我们可以将使用0标记的点视为空空间。对于每个质心，您必须决定哪个质心最接近所讨论的点。下面是示例的距离：
(0,8) distance from centroid 2 is 4.123105625617661
(0,8) distance from centroid 3 is 3.1622776601683795
(0,8) distance from centroid 4 is 8.602325267042627
(0,8) distance from centroid 5 is 5.830951894845301
(0,8) distance from centroid 6 is 6.0
(0,8) distance from centroid 7 is 6.324555320336759
(0,8) distance from centroid 8 is 2.8284271247461903
(1,1) distance from centroid 2 is 3.0
(1,1) distance from centroid 3 is 4.0
(1,1) distance from centroid 4 is 4.0
(1,1) distance from centroid 5 is 2.8284271247461903
(1,1) distance from centroid 6 is 1.4142135623730951
(1,1) distance from centroid 7 is 7.0710678118654755
(1,1) distance from centroid 8 is 5.0990195135927845
(2,8) distance from centroid 2 is 4.123105625617661
(2,8) distance from centroid 3 is 3.1622776601683795
(2,8) distance from centroid 4 is 7.615773105863909
(2,8) distance from centroid 5 is 5.0990195135927845
(2,8) distance from centroid 6 is 6.324555320336759
(2,8) distance from centroid 7 is 4.47213595499958
(2,8) distance from centroid 8 is 2.0
(3,2) distance from centroid 2 is 2.8284271247461903
(3,2) distance from centroid 3 is 3.605551275463989
(3,2) distance from centroid 4 is 2.23606797749979
(3,2) distance from centroid 5 is 1.0
(3,2) distance from centroid 6 is 3.0
(3,2) distance from centroid 7 is 5.0
(3,2) distance from centroid 8 is 4.123105625617661
(4,5) distance from centroid 2 is 3.1622776601683795
(4,5) distance from centroid 3 is 3.0
(4,5) distance from centroid 4 is 4.123105625617661
(4,5) distance from centroid 5 is 2.23606797749979
(4,5) distance from centroid 6 is 5.0
(4,5) distance from centroid 7 is 2.23606797749979
(4,5) distance from centroid 8 is 2.23606797749979
(4,8) distance from centroid 2 is 5.0
(4,8) distance from centroid 3 is 4.242640687119285
(4,8) distance from centroid 4 is 7.0710678118654755
(4,8) distance from centroid 5 is 5.0990195135927845
(4,8) distance from centroid 6 is 7.211102550927978
(4,8) distance from centroid 7 is 2.8284271247461903
(4,8) distance from centroid 8 is 2.8284271247461903
(6,1) distance from centroid 2 is 5.830951894845301
(6,1) distance from centroid 3 is 6.4031242374328485
(6,1) distance from centroid 4 is 1.0
(6,1) distance from centroid 5 is 3.605551275463989
(6,1) distance from centroid 6 is 6.082762530298219
(6,1) distance from centroid 7 is 5.0
(6,1) distance from centroid 8 is 6.4031242374328485
(7,1) distance from centroid 2 is 6.708203932499369
(7,1) distance from centroid 3 is 7.211102550927978
(7,1) distance from centroid 4 is 2.0
(7,1) distance from centroid 5 is 4.47213595499958
(7,1) distance from centroid 6 is 7.0710678118654755
(7,1) distance from centroid 7 is 5.0990195135927845
(7,1) distance from centroid 8 is 7.0710678118654755
(7,5) distance from centroid 2 is 6.082762530298219
(7,5) distance from centroid 3 is 6.0
(7,5) distance from centroid 4 is 4.47213595499958
(7,5) distance from centroid 5 is 4.47213595499958
(7,5) distance from centroid 6 is 7.615773105863909
(7,5) distance from centroid 7 is 1.4142135623730951
(7,5) distance from centroid 8 is 5.0990195135927845
(8,1) distance from centroid 2 is 7.615773105863909
(8,1) distance from centroid 3 is 8.06225774829855
(8,1) distance from centroid 4 is 3.0
(8,1) distance from centroid 5 is 5.385164807134504
(8,1) distance from centroid 6 is 8.06225774829855
(8,1) distance from centroid 7 is 5.385164807134504
(8,1) distance from centroid 8 is 7.810249675906654
(8,8) distance from centroid 2 is 8.06225774829855
(8,8) distance from centroid 3 is 7.615773105863909
(8,8) distance from centroid 4 is 7.615773105863909
(8,8) distance from centroid 5 is 7.0710678118654755
(8,8) distance from centroid 6 is 10.0
(8,8) distance from centroid 7 is 2.8284271247461903
(8,8) distance from centroid 8 is 6.324555320336759聚类算法的最终结果是，矩阵中不存在1s，只有质心数。这就是为什么必须对2-k+1中的质心进行标记，使我们能够替换它们，如下所示：
0 0 0 0 0 0 0 0 8
0 6 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 8
0 0 5 0 0 0 0 0 0
0 0 0 0 0 5 0 0 7
0 0 0 0 0 0 0 0 0
0 4 0 0 0 0 0 0 0
0 4 0 0 0 7 0 0 0
0 4 0 0 0 0 0 0 7
0 0 0 0 0 0 0 0 0这是提供的网格上7个质心的初始聚类布局，给定的是随机生成的质心。您的工作是输出二进制输入网格的群集版本。
规则
k-1质心必须是随机生成的，并且应该是从(0,0)到(grid#Width, grid#Height)的任意位置。k的值是min(grid#Width, grid#Height)-1。- 生成的质心必须从
2编号到k。
- 输入格式必须是由0和1组成的网格，其中0表示空空间，1表示点。
- 网格要么是使用每个单元格1-char和
\n作为行分隔符的字符串，要么是一个2D数组。 - 通过的网格不能保证是正方形的，但保证它不会是空的。
- 网格要么是使用每个单元格1-char和
- 最终输出可以使用数组，也可以使用分隔字符串。
- 最短代码获胜，这是密码-高尔夫。
回答 1
Code Golf用户
发布于 2017-05-09 18:15:45
Mathematica 109 Bytes
如果我正确地理解了这个问题，这样的事情应该是可行的。"KMeans“是FindClusters和ClusteringComponents的内置方法之一。
SparseArray[Thread[(p=Position[#,1])->1+ClusteringComponents[p,Min[d=Dimensions@#]-1,1,Method->"KMeans"]],d]&用法：%@in//MatrixForm实现可视化，in是一个整数数组。
页面原文内容由Code Golf提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codegolf.stackexchange.com/questions/119807
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号