Prosedur pengelompokan di mana setiap kelompok memiliki jumlah poin yang sama?

Saya memiliki beberapa poin dalam , dan saya ingin mengelompokkan poin sehingga:R $X=\{x_1,...,x_n\}$$R^p$

1. Setiap cluster berisi jumlah elemen . (Asumsikan bahwa jumlah cluster dibagi .)$X$$n$

2. Setiap cluster "kohesif spasial" dalam beberapa hal, seperti cluster dari berarti.$k$

Sangat mudah untuk memikirkan banyak prosedur pengelompokan yang memuaskan satu atau yang lainnya, tetapi apakah ada yang tahu cara untuk mendapatkan keduanya sekaligus?

Saya menyarankan pendekatan dua langkah:

1. dapatkan perkiraan awal yang baik dari pusat-pusat klaster, mis. menggunakan hard-atau fuzzy K-means.

2. Gunakan penugasan Global Nearest Neighbor untuk mengaitkan titik dengan pusat klaster: Hitung matriks jarak antara setiap titik dan setiap pusat klaster (Anda dapat membuat masalahnya sedikit lebih kecil dengan hanya menghitung jarak yang masuk akal), mereplikasi setiap pusat klaster X kali, dan menyelesaikan linier masalah penugasan . Anda akan mendapatkan, untuk setiap pusat gugus, X yang cocok dengan titik data, sehingga, secara global, jarak antara titik data dan pusat gugus diminimalkan.

Perhatikan bahwa Anda dapat memperbarui pusat-pusat klaster setelah langkah 2 dan ulangi langkah 2 untuk menjalankan K-means pada dasarnya dengan jumlah poin tetap per kluster. Namun, itu akan menjadi ide yang baik untuk mendapatkan tebakan awal yang baik terlebih dahulu.

Coba variasi k-means ini:

Inisialisasi :

• pilih kpusat dari dataset secara acak, atau bahkan lebih baik menggunakan strategi kmeans ++
• untuk setiap titik, hitung jarak ke pusat cluster terdekat, dan buat tumpukan untuk ini
• menarik poin dari heap, dan menugaskan mereka ke cluster terdekat, kecuali jika cluster sudah penuh. Jika demikian, hitung pusat cluster terdekat berikutnya dan masukkan kembali ke tumpukan

Pada akhirnya, Anda harus memiliki paritioning yang memenuhi persyaratan Anda dari + -1 jumlah objek yang sama per cluster (pastikan beberapa cluster terakhir juga memiliki nomor yang tepat. mCluster pertama harus memiliki ceilobjek, sisanya persis floorobjek.)

Langkah iterasi :

Persyaratan: daftar untuk setiap cluster dengan "swap proposal" (objek yang lebih suka berada di cluster yang berbeda).

Langkah E : hitung pusat-pusat cluster yang diperbarui seperti dalam k-means reguler

Langkah M : Iterasi semua poin (baik hanya satu, atau semuanya dalam satu batch)

Hitung pusat klaster terdekat dengan objek / semua pusat klaster yang lebih dekat dari kluster saat ini. Jika cluster berbeda:

• Jika cluster lain lebih kecil dari cluster saat ini, cukup pindahkan ke cluster baru
• Jika ada proposal swap dari kluster lain (atau klaster mana pun dengan jarak lebih rendah), tukar penugasan dua elemen kluster elemen (jika ada lebih dari satu penawaran, pilih satu dengan peningkatan terbesar)
• jika tidak, tunjukkan proposal swap untuk cluster lain

Ukuran cluster tetap invarian (+ - perbedaan langit-langit / lantai), suatu objek hanya dipindahkan dari satu cluster ke yang lain selama itu menghasilkan peningkatan estimasi. Karena itu ia harus menyatu di beberapa titik seperti k-means. Mungkin sedikit lebih lambat (yaitu lebih banyak iterasi).

Saya tidak tahu apakah ini sudah diterbitkan atau diterapkan sebelumnya. Itu hanya apa yang akan saya coba (jika saya akan mencoba k-means. Ada banyak algoritma clustering.)

Tempat yang baik untuk memulai mungkin dengan implementasi k-means di ELKI , yang tampaknya sudah mendukung tiga inisialisasi yang berbeda (termasuk k-means ++), dan penulis mengatakan mereka juga ingin memiliki strategi iterasi yang berbeda, untuk mencakup semua berbagai kesamaan varian dalam mode modular (mis. Lloyd, MacQueen, ...).

Ini adalah masalah optimisasi. Kami memiliki pustaka java open source yang memecahkan masalah ini (pengelompokan di mana kuantitas per cluster harus berada di antara rentang yang ditetapkan). Anda akan membutuhkan jumlah total poin maksimum beberapa ribu - tidak lebih dari 5000 atau mungkin 10000.

Perpustakaan ada di sini:

https://github.com/PGWelch/territorium/tree/master/territorium.core

Perpustakaan itu sendiri adalah pengaturan untuk masalah tipe geografis / GIS - sehingga Anda akan melihat referensi ke X dan Ys, lintang dan bujur, pelanggan, jarak dan waktu, dll. Anda dapat mengabaikan elemen 'geografis' dan menggunakannya sebagai murni clusterer.

Anda memberikan satu set kluster masukan yang awalnya kosong masing-masing dengan jumlah target minimum dan maksimum. Clusterer akan memberikan poin ke cluster input Anda, menggunakan algoritma optimasi berbasis heuristik (swap, bergerak dll). Dalam optimasi itu pertama-tama memprioritaskan menjaga setiap cluster dalam kisaran kuantitas min dan max dan kemudian kedua meminimalkan jarak antara semua titik dalam cluster dan titik pusat cluster, sehingga sebuah cluster kohesif secara spasial.

Anda memberi pemecah fungsi metrik (fungsi jarak) antara titik-titik menggunakan antarmuka ini:

https://github.com/PGWelch/territorium/blob/master/territorium.core/src/main/java/com/opendoorlogistics/territorium/problem/TravelMatrix.java

Metrik sebenarnya disusun untuk mengembalikan jarak dan 'waktu', karena dirancang untuk masalah geografis berbasis perjalanan, tetapi untuk masalah pengelompokan sewenang-wenang, hanya menetapkan 'waktu' menjadi nol dan jarak menjadi metrik aktual yang Anda gunakan di antara poin.

Anda mengatur masalah Anda di kelas ini:

https://github.com/PGWelch/territorium/blob/master/territorium.core/src/main/java/com/opendoorlogistics/territorium/problem/Problem.java

Poin Anda adalah 'Pelanggan' dan jumlah mereka adalah 1. Di kelas pelanggan memastikan Anda menetapkan costPerUnitTime = 0 dan costPerUnitDistance = 1 dengan asumsi Anda mengembalikan jarak metrik Anda di bidang 'jarak' yang dikembalikan oleh TravelMatrix.

https://github.com/PGWelch/territorium/blob/master/territorium.core/src/main/java/com/opendoorlogistics/territorium/problem/Customer.java

Lihat di sini untuk contoh menjalankan solver:

https://github.com/PGWelch/territorium/blob/master/territorium.core/src/test/java/com/opendoorlogistics/territorium/TestSolver.java

Saya menyarankan makalah baru-baru ini Diskriminatif Clustering oleh Regulasi Informasi Dimaksimalkan (dan referensi di dalamnya). Secara khusus, Bagian 2 berbicara tentang keseimbangan kelas dan asumsi cluster.

Baru-baru ini saya membutuhkan ini sendiri untuk dataset yang tidak terlalu besar. Jawaban saya, walaupun memiliki waktu operasi yang relatif lama, dijamin akan menyatu dengan optimal lokal.

def eqsc(X, K=None, G=None):
    "equal-size clustering based on data exchanges between pairs of clusters"
    from scipy.spatial.distance import pdist, squareform
    from matplotlib import pyplot as plt
    from matplotlib import animation as ani    
    from matplotlib.patches import Polygon   
    from matplotlib.collections import PatchCollection
    def error(K, m, D):
        """return average distances between data in one cluster, averaged over all clusters"""
        E = 0
        for k in range(K):
            i = numpy.where(m == k)[0] # indeces of datapoints belonging to class k
            E += numpy.mean(D[numpy.meshgrid(i,i)])
        return E / K
    numpy.random.seed(0) # repeatability
    N, n = X.shape
    if G is None and K is not None:
        G = N // K # group size
    elif K is None and G is not None:
        K = N // G # number of clusters
    else:
        raise Exception('must specify either K or G')
    D = squareform(pdist(X)) # distance matrix
    m = numpy.random.permutation(N) % K # initial membership
    E = error(K, m, D)
    # visualization
    #FFMpegWriter = ani.writers['ffmpeg']
    #writer = FFMpegWriter(fps=15)
    #fig = plt.figure()
    #with writer.saving(fig, "ec.mp4", 100):
    t = 1
    while True:
        E_p = E
        for a in range(N): # systematically
            for b in range(a):
                m[a], m[b] = m[b], m[a] # exchange membership
                E_t = error(K, m, D)
                if E_t < E:
                    E = E_t
                    print("{}: {}<->{} E={}".format(t, a, b, E))
                    #plt.clf()
                    #for i in range(N):
                        #plt.text(X[i,0], X[i,1], m[i])
                    #writer.grab_frame()
                else:
                    m[a], m[b] = m[b], m[a] # put them back
        if E_p == E:
            break
        t += 1           
    fig, ax = plt.subplots()
    patches = []
    for k in range(K):
        i = numpy.where(m == k)[0] # indeces of datapoints belonging to class k
        x = X[i]        
        patches.append(Polygon(x[:,:2], True)) # how to draw this clock-wise?
        u = numpy.mean(x, 0)
        plt.text(u[0], u[1], k)
    p = PatchCollection(patches, alpha=0.5)        
    ax.add_collection(p)
    plt.show()

if __name__ == "__main__":
    N, n = 100, 2    
    X = numpy.random.rand(N, n)
    eqsc(X, G=3)