Элементы кластеризации, основанные на самом высоком сходстве

Question

Я работаю с изображениями Докера, которые состоят из набора повторно используемых слоев. Теперь, учитывая коллекцию изображений, я хотел бы объединить изображения, которые имеют большое количество общих слоев.

Чтобы быть более точным: учитывая коллекцию N изображений, я хочу создать кластеры, где все изображения в кластере разделяют более X процентов услуг с eachother. Каждому изображению разрешено принадлежать только одному кластеру.

Мои собственные исследовательские точки в направлении кластерных алгоритмов, где я использую меру подобия, чтобы решить, какие изображения принадлежат кластеру вместе. Мера подобия, которую я знаю, как писать. Однако мне трудно найти точный алгоритм или псевдо-алгоритм для начала.

Может кто-нибудь порекомендовать алгоритм для решения этой проблемы или предоставить псевдокод, пожалуйста?

EDIT: после некоторого поиска я считаю, что ищу что-то вроде этой иерархической кластеризации (https://github.com/lbehnke/hierarchical-clustering-java), но с порогом X, так что соседи с менее чем сходством X% не объединяются и остаются в отдельном кластере ,

Answer 1

Я закончил решение проблемы, используя иерархическую кластеризацию, а затем пройдя каждую ветвь дендрограммы сверху вниз, пока не найду кластер, где расстояние ниже порога. В худшем случае нет такого кластера, но тогда я попаду в лист дендрограммы, что означает, что элемент находится в своем собственном кластере.

Answer 2

Я считаю, что вы разработчик, и у вас нет опыта работы с наукой о данных?

Существует несколько алгоритмов кластеризации, и у них есть свои преимущества и недостатки (обратитесь к https://en.wikipedia.org/wiki/Cluster_analysis), но я думаю, что решение для вашей проблемы проще, чем можно подумать.

Я предполагаю, что N достаточно мало, чтобы вы могли хранить матрицу с N^2 поплавковыми значениями в ОЗУ? Если это так, вы находитесь в очень удобной ситуации. Вы пишете, что знаете, как реализовать меру подобия, поэтому просто вычислите меру для всех пар N^2 и сохраните ее в матрице (это симметричная матрица, поэтому можно сохранить только половину ее). Пожалуйста, убедитесь, что ваша мера сходства присваивает особое значение для пары изображений, где показатель подобия меньше, чем некоторый X%, например 0 или бесконечность (это зависит от того, как вы относитесь к функции, такой как мера сходства или как расстояние). Я считаю, что идеальным решением является назначение 1 для пар, где сходство больше, чем порог X%, и 0 в противном случае.

После этого обработать точно так же, как график. Возьмите первую вершину и сделайте, например, глубокий первый поиск или любую другую обычную рутину. Это ваш первый кластер. После этого сначала заходите в вершину и повторяйте графическую ходьбу. Конечно, вы можете сохранить граф как список смежности для сохранения памяти.

Этот алгоритм предполагает, что вы действительно не обращаете внимания на то, насколько похожи изображения и какие пары более похожи, чем другие, но если они достаточно схожи (показатель подобия больше заданного порога).

К сожалению, в анализе кластеров часто приходится вычислять 100% возможных пар. Можно сохранить некоторое количество дистанционных вызовов, используя некоторые причудливые структуры данных для поиска k-ближайшего соседа, но вы должны заверить, что ваша схожесть измеряет неравенство треугольника.

Если вы не удовлетворены этим ответом, пожалуйста, указать более подробную информацию о вашей проблеме и прочитать о:

K-средства (главный недостаток: вы должны указать число кластеров)

Иерархическая кластеризация (медленное время вычисления, на вершине всех изображений находятся в одном кластере, вы должны вырезать дендрограммы на надлежащем расстоянии)

спектральной кластеризацию (для графов, но я думаю, что это слишком сложно для этой простой задачи)