基于最高相似度的聚类元素
Clustering elements based on highest similarity
我正在处理 Docker 图像，这些图像由一组可重复使用的图层组成。现在给定一组图像，我想合并具有大量共享层的图像。
更准确地说：给定 N 个图像的集合，我想创建集群，集群中的所有图像彼此共享超过 X% 的服务。每张图片只允许属于一个集群。
我自己的研究方向是聚类算法，我使用相似性度量来决定哪些图像一起属于一个聚类。我知道怎么写的相似性度量。但是，我很难找到一个确切的算法或伪算法来开始。
有人可以推荐一个算法来解决这个问题或者请提供伪代码吗？
编辑：经过更多搜索后，我相信我正在寻找类似这种层次聚类（https://github.com/lbehnke/hierarchical-clustering-java）但阈值 X 的东西，这样相似度小于 X% 的邻居就不会合并，留在单独的集群中。
我相信您是一名开发人员并且没有数据科学方面的经验？
有多种聚类算法，它们各有优缺点（请参考https://en.wikipedia.org/wiki/Cluster_analysis），但我认为解决您的问题比想象的要容易。
我假设 N 足够小，所以您可以在 RAM 内存中存储具有 N^2 个浮点值的矩阵？如果是这样的话，你就处于一个非常舒适的境地。你写道你知道如何实现相似性度量，所以只需计算所有 N^2 对的度量并将其存储在矩阵中（它是一个对称矩阵，因此只能存储一半）。请确保您的相似性度量为一对图像分配特殊值，其中相似性度量小于 X%，例如 0 或无穷大（这取决于您将函数视为相似性度量还是距离）。我认为完美的解决方案是为相似度大于 X% 阈值的对分配 1，否则为 0。
之后，对待就像一个图表。获取第一个顶点并进行例如深度优先搜索或任何其他图形遍历例程。这是您的第一个集群。之后首先获取未访问的顶点并重复图形遍历。当然你可以将图存储为邻接表以节省内存。
该算法假定您真的不关注有多少图像相似以及哪些对比其他图像更相似，但如果它们足够相似（相似性度量大于给定阈值）。
不幸的是，在聚类分析中，通常必须计算 100% 的可能对。 k-nearest 邻居搜索可以使用一些奇特的数据结构来节省一些距离调用，但你必须确保你的相似性度量保持三角不等式。
如果您对此答案不满意，请详细说明您的问题并阅读：
K-means（主要缺点：您必须指定簇数）
层次聚类（计算时间慢，在顶部所有图像都在一个簇中，你必须在适当的距离切割树状图）
谱聚类（用于图形，但我认为对于这个简单的问题来说太复杂了）
我最终通过使用层次聚类解决了这个问题，然后从上到下遍历树状图的每个分支，直到找到距离低于阈值的聚类。最坏的情况是没有这样的集群，但我最终会出现在树状图的一片叶子中，这意味着该元素在它自己的集群中。
我正在处理 Docker 图像，这些图像由一组可重复使用的图层组成。现在给定一组图像，我想合并具有大量共享层的图像。
更准确地说：给定 N 个图像的集合，我想创建集群，集群中的所有图像彼此共享超过 X% 的服务。每张图片只允许属于一个集群。
我自己的研究方向是聚类算法，我使用相似性度量来决定哪些图像一起属于一个聚类。我知道怎么写的相似性度量。但是，我很难找到一个确切的算法或伪算法来开始。
有人可以推荐一个算法来解决这个问题或者请提供伪代码吗？
编辑：经过更多搜索后，我相信我正在寻找类似这种层次聚类（https://github.com/lbehnke/hierarchical-clustering-java）但阈值 X 的东西，这样相似度小于 X% 的邻居就不会合并，留在单独的集群中。
我相信您是一名开发人员并且没有数据科学方面的经验？
有多种聚类算法，它们各有优缺点（请参考https://en.wikipedia.org/wiki/Cluster_analysis），但我认为解决您的问题比想象的要容易。
我假设 N 足够小，所以您可以在 RAM 内存中存储具有 N^2 个浮点值的矩阵？如果是这样的话，你就处于一个非常舒适的境地。你写道你知道如何实现相似性度量，所以只需计算所有 N^2 对的度量并将其存储在矩阵中（它是一个对称矩阵，因此只能存储一半）。请确保您的相似性度量为一对图像分配特殊值，其中相似性度量小于 X%，例如 0 或无穷大（这取决于您将函数视为相似性度量还是距离）。我认为完美的解决方案是为相似度大于 X% 阈值的对分配 1，否则为 0。
之后，对待就像一个图表。获取第一个顶点并进行例如深度优先搜索或任何其他图形遍历例程。这是您的第一个集群。之后首先获取未访问的顶点并重复图形遍历。当然你可以将图存储为邻接表以节省内存。
该算法假定您真的不关注有多少图像相似以及哪些对比其他图像更相似，但如果它们足够相似（相似性度量大于给定阈值）。
不幸的是，在聚类分析中，通常必须计算 100% 的可能对。 k-nearest 邻居搜索可以使用一些奇特的数据结构来节省一些距离调用，但你必须确保你的相似性度量保持三角不等式。
如果您对此答案不满意，请详细说明您的问题并阅读：
K-means（主要缺点：您必须指定簇数）
层次聚类（计算时间慢，在顶部所有图像都在一个簇中，你必须在适当的距离切割树状图）
谱聚类（用于图形，但我认为对于这个简单的问题来说太复杂了）
我最终通过使用层次聚类解决了这个问题，然后从上到下遍历树状图的每个分支，直到找到距离低于阈值的聚类。最坏的情况是没有这样的集群，但我最终会出现在树状图的一片叶子中，这意味着该元素在它自己的集群中。