алгоритм кластеризации maxmin

Question

Я прочитал статью, в которой упоминается алгоритм max min clustering, но я не совсем понимаю, что делает этот алгоритм. Алгоритм «max min clustering» алгоритма поиска в googling не дает никакого полезного результата. кто-нибудь знает, что означает этот алгоритм? это выдержка из статьи:

Макс-мин-кластеризация продолжается, выбирая случайное наблюдение в качестве первого центроида c1 и устанавливая набор C центроидов на {c1}. Во время i-й итерации ci выбирается так, чтобы максимизировать минимальное евклидово расстояние между ci и наблюдениями в C. Макс-мин-кластеризация предпочтительнее алгоритма кластеризации на основе плотности (например, k-средств), который будет иметь тенденцию выбирать множество примеров из плотной группы точек данных, не связанных с захватом.

Я не совсем понимаю смелую часть. Ссылка на бумагу here

Answer 1

Мы выбираем каждый новый центр тяжести как можно дальше от существующих центроидов. Вот код Python.

def maxminclustering(observations, k): 
    observations = set(observations) 
    if k < 1 or not observations: return set() 
    centroids = set([observations.pop()]) 
    for i in range(min(k - 1, len(observations))): 
     newcentroid = max(observations, 
          key=lambda observation: 
            min(distance(observation, centroid) 
             for centroid in centroids)) 
     observations.remove(newcentroid) 
     centroids.add(newcentroid) 
    return centroids 

Answer 2

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

Это удивительно простая, но довольно эффективная стратегия. В принципе, он найдет множество данных, которые хорошо распределены, что может привести к быстрому сближению k-средств. Обычно отбрасывается первая (случайная) точка данных.

Он работает только при низких значениях k, хотя (он избегает размещения центроидов в центре набора данных!), И он не очень благоприятен для нескольких прогонов - он снова выбирает те же начальные центроиды.

K-mean ++ можно рассматривать как более рандомизированную версию этого. Вместо того, чтобы всегда выбирать объект farthes, он выбирает далеко идущие объекты с повышенной вероятностью, но может наугад также выбирать ближайшего соседа. Таким образом, вы получаете более разнообразные результаты при работе с ним несколько раз.

Вы можете попробовать его в ELKI, он называется FarthestPointsInitialMeans. Если вы выберете алгоритм SingleAssignmentKMeans, то он не будет выполнять итерации k-означает, но только выполняет начальное назначение. Это, вероятно, даст вам этот алгоритм «MaxMin clustering».