Мне нужно несколько советов о том, как улучшить алгоритм кластеризации. Ответ может быть тривиальным или невозможным. Я много гуглил, но я либо не понимаю аналогии между моей проблемой и известными алгоритмами кластеризации, либо такой аномалии нет. Я не специалист по информатике, и, возможно, я неправильно понимаю много жаргона.
Проблема
Мне дан набор N элементов, и мне нужно сгруппировать эти элементы в K групп, с K неизвестно. Группировка основана на вызове функции measure(group), которая возвращает меру того, насколько близко элементы в группе находятся. group обозначает коллекцию по крайней мере из двух элементов. Еще одним усложняющим фактором является то, что результат measure очень неопределенный, когда group имеет только два элемента, и что вызов этой функции стоит дорого.
Мое решение
Возьмите пустой список назначенных элементов, A.
Поскольку результат measure не является точным для двух элементов, чтобы начать "заполнение" группы, я беру первый элемент x0, добавляю его к A, а затем перебираю все остальные элементы, xi. Я звоню measure с комбинациями из двух точек (x0, xi), пока не получу measure, который настолько мал, что я могу быть уверен в этом. Если этого никогда не произойдет, x0 является группой из одного элемента, и я продолжаю. Если я получу хорошую меру, xi добавится в группу и в список назначенных элементов A. Как только это начальное число найдено, я перезапускаю итерацию по всем элементам, исключая элементы уже в A (возможно, я пропустил некоторые элементы в группе, потому что measure неопределенно для двух элементов). Для каждого нового элемента-кандидата x я звоню measure с group, собранным до сих пор, и x, добавленным к нему. Если x не увеличивает "много" measure из group, оно добавляется к group и A. У меня есть способ точно определить «много», но это деталь конкретной проблемы, с которой я столкнулся.
Когда я заканчиваю итерацию по всем элементам, я перезапускаю новую группу с первого элемента, которого еще нет в A, всегда пропуская элементы в A, пока не сгруппирую все элементы.
Что с ним не так?
Решение замечательно устойчиво для конкретной проблемы, с которой я работаю. Однако в худшем случае это n^2 (итерация по всем комбинациям элементов в группах по 2). На практике такого никогда не бывает, и мой n редко превышает несколько сотен, но в некоторых патологических случаях приближается к худшему. Поскольку вызов measure стоит очень дорого, решение проблемы с меньшим количеством итераций было бы весьма полезным. И, думаю, решение n^2 никогда не бывает идеальным ...