Изменение алгоритма K-средних с одинаковым размером кластера

Question

Я ищу самый быстрый алгоритм для группировки точек на карте в группы одинакового размера по расстоянию. алгоритм кластеризации k-средних выглядит простым и многообещающим, но не дает групп одинакового размера.

Существует ли разновидность этого алгоритма или другой, который допускает равное количество членовдля всех кластеров?

См. также: Группировать n точек в k кластерах одинакового размера

Answer 1

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

Например, у меня есть таблица с именем tb_points, которая имеет 4000 координатных точек, и вы хотите разделить ее на 10 одинаковых по размеру групп, которые будут содержать 400 координатных точек каждая. Вот пример структуры таблицы

CREATE TABLE tb_points (
  id SERIAL PRIMARY KEY,
  outlet_id INTEGER,
  longitude FLOAT,
  latitide FLOAT,
  group_id INTEGER
);

Тогда что вам нужно сделать:

1. Найдите первую координату, которая будет вашей отправной точкой
2. Найти ближайшую координату от вашей начальной точки, упорядочить по возрастанию расстояния, ограничить результат числом вашего предпочтительного члена (в данном случае 400)
3. Обновить результат, обновив столбец group_id
4. Выполните 3 шага выше 10 раз для остальных данных, столбец group_id которых по-прежнему равен NULL

Это реализация в python:

import psycopg2

dbhost = ''
dbuser = ''
dbpass = ''
dbname = ''
dbport = 5432

conn = psycopg2.connect(host = dbhost,
       user = dbuser,
       password = dbpass,
       database = dbname,
       port = dbport)

def fetch(sql):
    cursor = conn.cursor()
    rs = None
    try:
        cursor.execute(sql)
        rs = cursor.fetchall()
    except psycopg2.Error as e:
        print(e.pgerror)
        rs = 'error'
    cursor.close()
    return rs

def execScalar(sql):
    cursor = conn.cursor()
    try:
        cursor.execute(sql)
        conn.commit()
        rowsaffected = cursor.rowcount
    except psycopg2.Error as e:
        print(e.pgerror)
        rowsaffected = -1
        conn.rollback()
    cursor.close()
    return rowsaffected


def select_first_cluster_id():
    sql = """ SELECT a.outlet_id as ori_id, a.longitude as ori_lon,
    a.latitude as ori_lat, b.outlet_id as dest_id, b.longitude as
    dest_lon, b.latitude as dest_lat,
    ST_Distance(CAST(ST_SetSRID(ST_Point(a.longitude,a.latitude),4326)
    AS geography), 
    CAST(ST_SetSRID(ST_Point(b.longitude,b.latitude),4326) AS geography))
    AS air_distance FROM  tb_points a CROSS JOIN tb_points b WHERE
    a.outlet_id != b.outlet_id and a.group_id is NULL and b.group_id is
    null order by air_distance desc limit 1 """
    return sql

def update_group_id(group_id, ori_id, limit_constraint):
    sql = """ UPDATE tb_points
    set group_id = %s
    where outlet_id in
    (select b.outlet_id
    from tb_points a,
    tb_points b
    where a.outlet_id = '%s'
    and a.group_id is null
    and b.group_id is null
    order by ST_Distance(CAST(ST_SetSRID(ST_Point(a.longitude,a.latitude),4326) AS geography),
    CAST(ST_SetSRID(ST_Point(b.longitude,b.latitude),4326) AS geography)) asc
    limit %s)
    """ % (group_id, ori_id, limit_constraint)
    return sql

def clustering():
    data_constraint = [100]
    n = 1
    while n <= 10:
        sql = select_first_cluster_id()
        res = fetch(sql)
        ori_id = res[0][0]

        sql = update_group_id(n, ori_id, data_constraint[0])
        print(sql)
        execScalar(sql)

        n += 1

clustering()

Надеюсь, это поможет

Answer 2

Также посмотрите на дерево Kd, которое разбивает данные до тех пор, пока элементы каждого из разделов не станут меньше BUCKET_SIZE, который является входом для алгоритма.

Это не заставляет сегменты / разделы быть одинаковымиразмер, но они будут все меньше, чем BUCKET_SIZE.

Answer 3

Могу ли я смиренно предложить вам попробовать этот проект ekmeans .

Реализация кластеризации Java K-означает с необязательной специальной равной опцией, которая применяет ограничение равной мощности накластеры, оставаясь как можно более пространственно сплоченными.

Это пока экспериментально, поэтому просто помните об известных ошибках .

Answer 4

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