Adım Adım Birleştirme

Coddy'nin Machine Learning Journey'sinin Denetimsiz Öğrenme bölümünün bir parçası. Ders 16 / 51.

Bu bölüm, verilerinizin bir aile ağacını oluşturur, ardından onu gruplara ayırır. İşte boyut ve ağırlıklarına göre on spor topu:

On spor topunu gösteren bir ağaç diyagramı. Golf, tenis ve beyzbol gibi küçük toplar bir tarafta aşağıda birleşirken futbol ve basketbol gibi büyük toplar diğer tarafta birleşiyor ve kesikli bir çizgi ağacı bu iki gruba ayırıyor

Ağaç aşağıdan yukarıya doğru büyür. Her noktayı tek başına başlatın, birbirine en yakın iki grubu birleştirin ve tekrarlayın:

Bir nehir boyunca 2, 7, 15, 19 ve 33 metrede bulunan beş çadır, beş sırada çizilmiştir. 1. adımda 15 ve 19 birleştirilir, 2. adımda 2 ve 7 birleştirilir, 3. adımda bu iki grup birleştirilir, 4. adımda 33 eklenir

İki grup arasındaki fark, ortalamaları arasındaki farktır. Listeler olarak birleştirme:

groups = [[2], [7], [15, 19], [33]]
groups[0] = groups[0] + groups[1]  # listeleri birleştir
groups.pop(1)  # [7] öğesini kaldır, artık grup 0'da
print(groups)

Bu, [[2, 7], [15, 19], [33]] çıktısını verir. Birleştirme üstüne birleştirme; buna birleştirici kümeleme denir.

Görev

Orta

Aileler plaj şemsiyelerini birbirine yakın diker. spots içindeki 10 şemsiyeyi, geriye wanted grup kalana kadar birleştirerek gruplayın. closest_pair(groups), birbirine en yakın iki grubun i ve j konumlarını döndürür.

Her şemsiyeyle tek başına, bir elemanlı bir listede başlayın.
wanted değerinden fazla grup olduğu sürece: birleştirmeyi yazdırın, çifti birleştirin, ikinci grubu kaldırın.
Geriye kalan grupları yazdırın.

Diğer şemsiyeler ve wanted değerinin 3 olduğu durumda:

Merge [33] and [35]
Merge [30] and [33, 35]
Merge [3] and [8]
3 groups: [[3, 8], [30, 33, 35], [70]]

Kendin dene

import numpy as np

# 10 plaj şemsiyesinin cankurtaran kulesine göre metre cinsinden konumları
spots = [2, 9, 11, 31, 45, 46, 69, 74, 92, 96]


# i, j (i < j) değerlerini döndürür: ortalamaları birbirine en yakın iki grubun konumları
def closest_pair(groups):
    best_i, best_j = 0, 1
    best_gap = abs(np.mean(groups[0]) - np.mean(groups[1]))
    for i in range(len(groups)):
        for j in range(i + 1, len(groups)):
            gap = abs(np.mean(groups[i]) - np.mean(groups[j]))
            if gap < best_gap:
                best_i, best_j, best_gap = i, j, gap
    return best_i, best_j


wanted = int(input())

# Kodunuzu aşağıya yazın