Практика · Ієрархічна кластеризація та DBSCAN> Лекція: lecture.html · Тест: quiz.html · Домашнє: homework.mdУ темі 11 k-means провалився на трьох наборах даних: витягнутісмуги, вкладені кільця й дві групи різної щільності. Тут ми беремо ті самі три форми йдивимось, що з ними роблять два інші методи.Що зробимо:1. згенеруємо три форми, на яких k-means помиляється;2. напишемо DBSCAN з нуля й звіримо мітки з sklearn — вони мають збігтися точно;3. проженемо три методи на трьох формах і складемо таблицю з adjusted_rand_score;4. підберемо eps за графіком відстані до k-го сусіда;5. порівняємо чотири звʼязки ієрархічної кластеризації на тих самих даних;6. побудуємо дендрограму через scipy.cluster.hierarchy;7. прикладемо всі три методи до справжньої дошки оголошень і чесно звіримо результат із колонкою шахрайське, якої жоден алгоритм не бачив.Генератор випадкових чисел зафіксовано зерном 42 — числа у тебе будуть ті самі.¶
In [1]:
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import KMeans, DBSCAN, AgglomerativeClustering
from sklearn.neighbors import NearestNeighbors
from sklearn.metrics import adjusted_rand_score, precision_score, recall_score, f1_score
from scipy.cluster.hierarchy import linkage, dendrogram, fcluster
# зерно фіксує всю випадковість: у тебе вийдуть точно ті самі числа
rng = np.random.default_rng(42)
pd.set_option("display.width", 130)
pd.set_option("display.max_columns", 12)
print("numpy", np.__version__, "· pandas", pd.__version__)
numpy 2.5.1 · pandas 2.3.3
1 · Три форми, на яких k-means помиляєтьсяКожен набір робимо руками, щоб було видно, звідки береться форма:* дві смуги — точки на двох паралельних прямих із невеликим розкидом;* вкладені кільця — щільна купка в центрі й кільце навколо неї;* різна щільність — тісна купка й розсіяна хмара поруч.Правильні відповіді (групи) ми знаємо, бо самі їх задали. Жоден алгоритм їх не побачить —вони потрібні лише нам, щоб порівняти результати.¶
In [2]:
def дві_смуги(скільки=65):
# обидві смуги йдуть під нахилом 0.6, різниця тільки у зсуві по вертикалі
зсув = 0.75
x_верх = rng.uniform(-2.6, 2.6, скільки)
y_верх = 0.6 * x_верх + зсув + rng.normal(0, 0.13, скільки)
x_низ = rng.uniform(-2.6, 2.6, скільки)
y_низ = 0.6 * x_низ - зсув + rng.normal(0, 0.13, скільки)
точки = np.c_[np.r_[x_верх, x_низ], np.r_[y_верх, y_низ]]
групи = np.r_[np.zeros(скільки, int), np.ones(скільки, int)]
return точки, групи
def вкладені_кільця(внутрішніх=45, зовнішніх=85):
# кут беремо рівномірно по колу, радіус — навколо 0.5 і навколо 2.0
кут_всередині = rng.uniform(0, 2 * np.pi, внутрішніх)
радіус_всередині = rng.normal(0.5, 0.12, внутрішніх)
кут_ззовні = rng.uniform(0, 2 * np.pi, зовнішніх)
радіус_ззовні = rng.normal(2.0, 0.13, зовнішніх)
точки = np.c_[
np.r_[радіус_всередині * np.cos(кут_всередині), радіус_ззовні * np.cos(кут_ззовні)],
np.r_[радіус_всередині * np.sin(кут_всередині), радіус_ззовні * np.sin(кут_ззовні)]]
групи = np.r_[np.zeros(внутрішніх, int), np.ones(зовнішніх, int)]
return точки, групи
def різна_щільність(щільних=95, розсіяних=55):
# розкид у другої групи втричі більший — саме це й зламає DBSCAN
купка = rng.normal([-1.8, 0.0], [0.5, 0.7], (щільних, 2))
хмара = rng.normal([1.0, -0.4], [1.5, 1.7], (розсіяних, 2))
точки = np.vstack([купка, хмара])
групи = np.r_[np.zeros(щільних, int), np.ones(розсіяних, int)]
return точки, групи
форми = {
"витягнуті смуги": дві_смуги(),
"вкладені кільця": вкладені_кільця(),
"різна щільність": різна_щільність(),
}
for назва, (точки, групи) in форми.items():
print(f"{назва:16s} точок: {len(точки):3d} групи: {np.bincount(групи)}")
витягнуті смуги точок: 130 групи: [65 65] вкладені кільця точок: 130 групи: [45 85] різна щільність точок: 150 групи: [95 55]
Подивимось на них очима — саме так, як їх бачить людина й не бачить k-means.
In [3]:
фігура, осі = plt.subplots(1, 3, figsize=(12, 3.8))
for вісь, (назва, (точки, групи)) in zip(осі, форми.items()):
for група, колір in [(0, "#c2185b"), (1, "#0f766e")]:
обрані = групи == група
вісь.scatter(точки[обрані, 0], точки[обрані, 1], s=12, color=колір, alpha=0.75)
вісь.set_title(назва)
вісь.set_aspect("equal")
вісь.grid(alpha=0.2)
plt.tight_layout()
plt.show()
print("кольори — правильна відповідь, яку алгоритмам не показують")
кольори — правильна відповідь, яку алгоритмам не показують
2 · DBSCAN з нуляУвесь метод — це два числа й три ролі точки:* eps — радіус околу;* min_samples — скільки точок має бути в цьому радіусі (разом із самою точкою), щоб вона вважалась ядерною;* точка, у якої сусідів замало, але яка потрапила в чийсь чужий окіл, — гранична;* решта — шум, мітка -1.Далі алгоритм просто обходить точки: знайшов ядерну — відкрив кластер і розрісся по їїсусідах, і по сусідах тих сусідів, поки є куди рости.¶
In [4]:
def dbscan_власний(точки, eps, min_samples):
кількість = len(точки)
мітки = np.full(кількість, -1) # -1 = шум, поки не доведено інше
відвідані = np.zeros(кількість, bool)
# попарні відстані одразу для всіх: на кількох сотнях точок це дешево
відстані = np.sqrt(((точки[:, None, :] - точки[None, :, :]) ** 2).sum(axis=2))
сусіди = [np.flatnonzero(рядок <= eps) for рядок in відстані]
номер_кластера = -1
for старт in range(кількість):
if відвідані[старт]:
continue
відвідані[старт] = True
if len(сусіди[старт]) < min_samples:
continue # не ядерна — поки що лишається шумом
номер_кластера += 1
мітки[старт] = номер_кластера
черга = list(сусіди[старт])
while черга:
точка = черга.pop(0)
if мітки[точка] == -1:
мітки[точка] = номер_кластера # гранична: забираємо її з шуму
if відвідані[точка]:
continue
відвідані[точка] = True
# кластер росте далі тільки через ядерні точки
if len(сусіди[точка]) >= min_samples:
черга.extend(сусіди[точка])
return мітки
print("функція готова — 25 рядків, і це весь метод")
функція готова — 25 рядків, і це весь метод
Тепер найцінніша клітинка практики: всередині бібліотечного DBSCAN немає магії. Дамообом реалізаціям ті самі дані й ті самі параметри — мітки мають збігтися повністю.adjusted_rand_score дорівнює 1.0, якщо два розбиття однакові з точністю доперейменування кластерів.
In [5]:
для_звірки, _ = форми["вкладені кільця"]
наші_мітки = dbscan_власний(для_звірки, eps=0.6, min_samples=5)
бібліотечні = DBSCAN(eps=0.6, min_samples=5).fit_predict(для_звірки)
print("наші кластери: ", np.bincount(наші_мітки[наші_мітки >= 0]))
print("кластери sklearn: ", np.bincount(бібліотечні[бібліотечні >= 0]))
print("шумових у нас / у них:", int((наші_мітки == -1).sum()), "/", int((бібліотечні == -1).sum()))
print("збіг розбиттів (ARI): ", round(adjusted_rand_score(наші_мітки, бібліотечні), 6))
assert adjusted_rand_score(наші_мітки, бібліотечні) == 1.0, "розбиття розійшлись!"
assert ((наші_мітки == -1) == (бібліотечні == -1)).all(), "шум розійшовся!"
print("✅ збігається")
наші кластери: [45 85] кластери sklearn: [45 85] шумових у нас / у них: 0 / 0 збіг розбиттів (ARI): 1.0 ✅ збігається
3 · Три методи на трьох формахУмови однакові для всіх, як і в лекції:* k-means — при k = 2, з десяти випадкових стартів;* DBSCAN — eps = 0.6, min_samples = 5: одні параметри на всі три набори;* ієрархічна — звʼязок Ворда (він стоїть за замовчуванням), дерево розрізане на дві групи.Міряємо adjusted_rand_score зі справжніми групами: 1.0 — ідеально, 0 — збіг нарівні випадкового перемішування.¶
In [6]:
рядки = []
розбиття = {}
for назва, (точки, групи) in форми.items():
мітки_kmeans = KMeans(n_clusters=2, n_init=10, random_state=42).fit_predict(точки)
мітки_dbscan = DBSCAN(eps=0.6, min_samples=5).fit_predict(точки)
мітки_ward = AgglomerativeClustering(n_clusters=2, linkage="ward").fit_predict(точки)
розбиття[назва] = (мітки_kmeans, мітки_dbscan, мітки_ward)
рядки.append({
"набір": назва,
"k-means": round(adjusted_rand_score(групи, мітки_kmeans), 3),
"DBSCAN": round(adjusted_rand_score(групи, мітки_dbscan), 3),
"ієрархічна (Ворд)": round(adjusted_rand_score(групи, мітки_ward), 3),
"кластерів DBSCAN": len(set(мітки_dbscan[мітки_dbscan >= 0])),
"шуму DBSCAN": int((мітки_dbscan == -1).sum()),
})
таблиця_методів = pd.DataFrame(рядки)
print(таблиця_методів.to_string(index=False))
набір k-means DBSCAN ієрархічна (Ворд) кластерів DBSCAN шуму DBSCAN витягнуті смуги 0.033 1.000 0.027 2 0 вкладені кільця 0.023 1.000 -0.002 2 0 різна щільність 0.677 0.637 0.701 3 29
Читається таблиця так. На смугах і кільцях DBSCAN дає 1.0 — ідеально, — а k-means іВорд не дають нічого: їхній ARI майже нуль, тобто розбиття не краще за випадкове.На різній щільності порядок перевертається: Ворд найкращий, k-means трохи гірший, аDBSCAN відстає й половину розсіяної хмари викидає в шум.Тепер те саме очима — девʼять картинок.
In [7]:
фігура, осі = plt.subplots(3, 3, figsize=(11, 10))
назви_методів = ["k-means", "DBSCAN (eps=0.6)", "ієрархічна (Ворд)"]
палітра = ["#c2185b", "#0f766e", "#c2620f", "#5b3fa8", "#1d6fbf"]
for рядок, (назва, (точки, групи)) in enumerate(форми.items()):
for стовпець, мітки in enumerate(розбиття[назва]):
вісь = осі[рядок, стовпець]
# шум малюємо сірими хрестиками, кластери — кольорами
шум = мітки == -1
вісь.scatter(точки[шум, 0], точки[шум, 1], s=16, marker="x", color="#9aa5b1")
for номер in sorted(set(мітки[~шум])):
обрані = мітки == номер
вісь.scatter(точки[обрані, 0], точки[обрані, 1], s=12,
color=палітра[номер % len(палітра)], alpha=0.8)
вісь.set_aspect("equal")
вісь.set_xticks([]); вісь.set_yticks([])
if рядок == 0:
вісь.set_title(назви_методів[стовпець], fontsize=11)
if стовпець == 0:
вісь.set_ylabel(назва, fontsize=10)
plt.tight_layout()
plt.show()
print("сірі хрестики — точки, які DBSCAN відніс до шуму")
сірі хрестики — точки, які DBSCAN відніс до шуму
4 · Звідки брати epsПрийом стандартний: для кожної точки знайти відстань до її k-го найближчого сусіда(k беруть рівним min_samples − 1), відсортувати ці відстані й шукати коліно — місце,де крива з пологої різко йде вгору. Висота коліна і є розумний eps.Щоб було цікавіше, підкинемо до двох смуг 15 розкиданих одинаків — точок, які неналежать жодній групі. Саме їх DBSCAN і має віднести до шуму.¶
In [8]:
точки_смуг, групи_смуг = форми["витягнуті смуги"]
# одинак — точка, яка стоїть не ближче ніж 0.55 до будь-якої точки смуг
одинаки = []
while len(одинаки) < 15:
кандидат = rng.uniform([-2.8, -2.6], [2.8, 2.8])
до_смуг = np.hypot(точки_смуг[:, 0] - кандидат[0], точки_смуг[:, 1] - кандидат[1])
if до_смуг.min() > 0.55:
одинаки.append(кандидат)
смуги_з_шумом = np.vstack([точки_смуг, np.array(одинаки)])
номери_одинаків = set(range(len(точки_смуг), len(смуги_з_шумом)))
print("точок разом:", len(смуги_з_шумом), "· з них підкинутих одинаків:", len(номери_одинаків))
точок разом: 145 · з них підкинутих одинаків: 15
In [9]:
# n_neighbors=5: перший «сусід» — сама точка, тому четвертий справжній сусід у стовпці 4
сусіди = NearestNeighbors(n_neighbors=5).fit(смуги_з_шумом)
відстані_до_сусідів, _ = сусіди.kneighbors(смуги_з_шумом)
четвертий_сусід = np.sort(відстані_до_сусідів[:, 4])
plt.figure(figsize=(7, 3.4))
plt.plot(четвертий_сусід, color="#c2185b")
plt.axhline(0.5, color="#17212b", linestyle="--", linewidth=1)
plt.text(2, 0.53, "коліно ≈ 0.5", fontsize=9)
plt.xlabel("точки, впорядковані за відстанню")
plt.ylabel("відстань до 4-го сусіда")
plt.grid(alpha=0.25)
plt.show()
print(f"медіана: {np.median(четвертий_сусід):.3f}")
print(f"вище 0.5: {int((четвертий_сусід > 0.5).sum())} точок зі {len(четвертий_сусід)}")
медіана: 0.241 вище 0.5: 19 точок зі 145
Тепер перевіримо коліно ділом: візьмемо eps з нього й подивимось, чи стануть шумом рівноті точки, які ми підкинули.
In [10]:
мітки_з_коліна = DBSCAN(eps=0.5, min_samples=5).fit_predict(смуги_з_шумом)
знайдений_шум = set(np.flatnonzero(мітки_з_коліна == -1).tolist())
print("кластерів:", len(set(мітки_з_коліна[мітки_з_коліна >= 0])))
print("шумових точок:", len(знайдений_шум))
print("це рівно підкинуті одинаки:", знайдений_шум == номери_одинаків)
print("ARI на самих смугах:",
round(adjusted_rand_score(групи_смуг, мітки_з_коліна[:len(точки_смуг)]), 3))
кластерів: 2 шумових точок: 15 це рівно підкинуті одинаки: True ARI на самих смугах: 1.0
Перевіримо, що коліно не бреше: проженемо кілька значень eps і подивимось, де ARIдорівнює одиниці. І одразу зробимо те саме на «різній щільності» — там коліна немає, іжодне значення eps не рятує.
In [11]:
точки_щільності, групи_щільності = форми["різна щільність"]
рядки = []
for eps in [0.3, 0.4, 0.5, 0.6, 0.8, 1.0, 1.2]:
мітки = DBSCAN(eps=eps, min_samples=5).fit_predict(точки_щільності)
рядки.append({"eps": eps,
"кластерів": len(set(мітки[мітки >= 0])),
"шуму": int((мітки == -1).sum()),
"ARI": round(adjusted_rand_score(групи_щільності, мітки), 3)})
перебір_eps = pd.DataFrame(рядки)
print(перебір_eps.to_string(index=False))
найкращий_dbscan = перебір_eps["ARI"].max()
ari_kmeans = таблиця_методів.loc[таблиця_методів["набір"] == "різна щільність", "k-means"].item()
ari_ward = таблиця_методів.loc[таблиця_методів["набір"] == "різна щільність", "ієрархічна (Ворд)"].item()
print(f"\nнайкращий DBSCAN: {найкращий_dbscan} k-means: {ari_kmeans} Ворд: {ari_ward}")
eps кластерів шуму ARI 0.3 2 70 0.409 0.4 1 56 0.636 0.5 1 48 0.679 0.6 3 29 0.637 0.8 4 11 0.598 1.0 2 7 0.656 1.2 1 3 0.030 найкращий DBSCAN: 0.679 k-means: 0.677 Ворд: 0.701
На різній щільності коліна немає, і жодне значення eps не рятує: при малому радіусірозсіяна хмара майже вся йде в шум, при великому — зливається з купкою. Найкраще, щовдається витиснути, — приблизно рівень k-means і гірше за Ворда. Причому вибрати цезначення можна лише підглядаючи у правильну відповідь, якої в реальній задачі немає.## 5 · Чотири звʼязки ієрархічної кластеризаціїlinkage відповідає на питання «що таке відстань між двома групами»:* single — між двома найближчими точками груп;* complete — між двома найдальшими;* average — середнє з усіх попарних відстаней;* ward — наскільки зросте сума квадратів усередині груп після злиття.Вибір міняє результат сильніше, ніж будь-що інше в методі.
In [12]:
рядки = []
for назва, (точки, групи) in форми.items():
рядок = {"набір": назва}
for звʼязок in ["single", "complete", "average", "ward"]:
мітки = AgglomerativeClustering(n_clusters=2, linkage=звʼязок).fit_predict(точки)
менша_група = min(np.bincount(мітки))
рядок[звʼязок] = round(adjusted_rand_score(групи, мітки), 3)
рядок[звʼязок + " (менша)"] = менша_група
рядки.append(рядок)
таблиця_звʼязків = pd.DataFrame(рядки)
print(таблиця_звʼязків.to_string(index=False))
набір single single (менша) complete complete (менша) average average (менша) ward ward (менша) витягнуті смуги 1.00 65 0.013 39 0.012 53 0.027 56 вкладені кільця 1.00 45 -0.040 24 -0.002 31 -0.002 31 різна щільність 0.01 1 0.655 41 0.677 42 0.701 47
Дивись на два стовпці: single дає 1.0 на смугах і кільцях — і 0.01 на різній щільності,де він відкушує від хмари дві точки й лишає велетня з усього іншого (стовпець «менша»показує це прямо). ward — рівно навпаки. Один і той самий звʼязок виграє в одномунаборі й програє в іншому.## 6 · Дошка оголошеньДалі — справжні дані: та сама дошка про вживані телефони, що і втемі 08. Блок нижче — код звідти без змін, щоб таблицязбіглася до цифри.
In [13]:
кількість = 1200
моделі = ["Alfa A5", "Alfa A7", "Beta 12", "Beta 12 Pro", "Gamma X", "Gamma X Ultra"]
ціна_нового = {"Alfa A5": 5200, "Alfa A7": 7400, "Beta 12": 12000,
"Beta 12 Pro": 17500, "Gamma X": 24000, "Gamma X Ultra": 34000}
частки_моделей = [0.24, 0.22, 0.18, 0.16, 0.12, 0.08]
# ВАЖЛИВО: дошку генеруємо власним генератором із зерном 42, щоб числа збіглися
# з темами 22, 25 і 26 — вище ми вже витратили частину послідовності на форми
гсч_дошки = np.random.default_rng(42)
модель = гсч_дошки.choice(моделі, size=кількість, p=частки_моделей)
рік = гсч_дошки.integers(2017, 2025, size=кількість)
стан = гсч_дошки.choice(["нове", "дуже добре", "добре", "задовільне"],
size=кількість, p=[0.08, 0.32, 0.42, 0.18])
памʼять = гсч_дошки.choice([64, 128, 256, 512], size=кількість, p=[0.30, 0.38, 0.24, 0.08])
вік_акаунта = np.round(гсч_дошки.exponential(420, size=кількість) + 3).astype(int)
базова = np.array([ціна_нового[m] for m in модель])
знос = 0.82 ** (2024 - рік)
коефіцієнт_стану = np.array(
[{"нове": 1.0, "дуже добре": 0.88, "добре": 0.75, "задовільне": 0.58}[s] for s in стан])
коефіцієнт_памʼяті = np.array(
[{64: 0.85, 128: 1.0, 256: 1.15, 512: 1.32}[m] for m in памʼять])
типова_ціна_за_паспортом = базова * знос * коефіцієнт_стану * коефіцієнт_памʼяті
ціна = типова_ціна_за_паспортом * гсч_дошки.lognormal(0, 0.13, size=кількість)
шанс_шахрайства = 0.10 + 0.30 * np.exp(-вік_акаунта / 120)
шахрайське = гсч_дошки.random(кількість) < шанс_шахрайства
ставить_дешево = гсч_дошки.random(кількість) < 0.74
дешева_приманка = шахрайське & ставить_дешево
дорога_приманка = шахрайське & ~ставить_дешево
ціна[дешева_приманка] = (типова_ціна_за_паспортом[дешева_приманка]
* гсч_дошки.uniform(0.20, 0.45, дешева_приманка.sum()))
ціна[дорога_приманка] = (типова_ціна_за_паспортом[дорога_приманка]
* гсч_дошки.uniform(2.6, 3.8, дорога_приманка.sum()))
ціна = np.round(ціна, -1)
скарг = np.where(шахрайське, 1 + гсч_дошки.poisson(3.0, кількість),
гсч_дошки.poisson(0.03, кількість))
дошка = pd.DataFrame({
"модель": модель, "рік": рік, "стан": стан, "памʼять_гб": памʼять,
"вік_акаунта": вік_акаунта, "скарг": скарг, "ціна": ціна,
"шахрайське": шахрайське.astype(int),
})
# ті самі шість неприємностей із теми 08
колекційні = дошка.index[дошка["модель"] == "Gamma X"][:4]
дошка.loc[колекційні, ["рік", "стан", "памʼять_гб"]] = [2017, "нове", 512]
дошка.loc[колекційні, "ціна"] = [82000.0, 88000.0, 91000.0, 95000.0]
дошка.loc[колекційні, ["шахрайське", "скарг"]] = 0
одруки = дошка.index[(дошка["ціна"] > 7000) & (дошка["ціна"] < 9600)
& (дошка["шахрайське"] == 0)][:2]
дошка.loc[одруки, "ціна"] = дошка.loc[одруки, "ціна"] * 10
памʼять_текстом = дошка["памʼять_гб"].astype(str)
із_одиницями = гсч_дошки.random(len(дошка)) < 0.18
памʼять_текстом[із_одиницями] = памʼять_текстом[із_одиницями] + " ГБ"
дошка["памʼять_гб"] = памʼять_текстом
ймовірність_пропуску = np.where(дошка["шахрайське"] == 1, 0.25, 0.03)
дошка.loc[гсч_дошки.random(len(дошка)) < ймовірність_пропуску, "ціна"] = np.nan
дошка.loc[гсч_дошки.random(len(дошка)) < 0.04, "стан"] = np.nan
повтори = гсч_дошки.choice(дошка.index, size=12, replace=False)
дошка = pd.concat([дошка, дошка.loc[повтори]], ignore_index=True)
print("таблиця як у темі 08:", дошка.shape)
assert дошка.shape == (1212, 8), "форма розійшлась із темою 22"
print("✅ форма збігається")
таблиця як у темі 08: (1212, 8) ✅ форма збігається
Далі — ті самі дві ознаки, що й у темі 11: логарифм ціни й рік випуску, обидвіприведені до z-оцінок. Обидва наші методи рахують відстані, тож без спільної шкали вонидивились би лише на ціну.
In [14]:
ринок = дошка.drop_duplicates().reset_index(drop=True)
ринок["памʼять_гб"] = ринок["памʼять_гб"].astype(str).str.replace(" ГБ", "", regex=False).astype(int)
ринок = ринок.dropna(subset=["ціна"]).reset_index(drop=True)
ціни = ринок["ціна"].to_numpy(float)
роки = ринок["рік"].to_numpy(int)
шахрайське_справді = ринок["шахрайське"].to_numpy()
масштабувач = StandardScaler().fit(np.c_[np.log(ціни), роки])
масштабовані = масштабувач.transform(np.c_[np.log(ціни), роки])
print("оголошень для кластеризації:", len(ринок))
print("шахрайських серед них:", int(шахрайське_справді.sum()),
f"({100 * шахрайське_справді.mean():.1f} %)")
print("розкид після масштабування:", масштабовані.std(axis=0).round(6))
оголошень для кластеризації: 1100 шахрайських серед них: 139 (12.6 %) розкид після масштабування: [1. 1.]
Дендрограма двадцяти восьми оголошеньДерево на 1 100 листків не читається, тому візьмемо випадкові 28 оголошень — ті самі, щов лекції. scipy малює дендрограму сам: висота перемички — відстань між групами в моментзлиття.¶
In [15]:
гсч_вибірки = np.random.default_rng(1)
вибрані = np.sort(гсч_вибірки.choice(len(масштабовані), 28, replace=False))
підвибірка = масштабовані[вибрані]
дерево = linkage(підвибірка, method="average")
plt.figure(figsize=(10, 4))
dendrogram(дерево, color_threshold=1.3, no_labels=True)
plt.axhline(1.3, color="#17212b", linestyle="--", linewidth=1)
plt.title("28 оголошень · звʼязок «середній» · зріз на висоті 1.3")
plt.ylabel("відстань злиття")
plt.show()
for висота in [0.5, 0.9, 1.3, 1.6, 2.0, 3.0]:
групи_на_зрізі = fcluster(дерево, висота, criterion="distance")
print(f"зріз {висота:.1f} → груп: {len(set(групи_на_зрізі)):2d} "
f"· розміри: {sorted(np.bincount(групи_на_зрізі)[1:].tolist(), reverse=True)}")
зріз 0.5 → груп: 12 · розміри: [6, 4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] зріз 0.9 → груп: 7 · розміри: [9, 6, 5, 3, 3, 1, 1] зріз 1.3 → груп: 5 · розміри: [11, 6, 5, 3, 3] зріз 1.6 → груп: 2 · розміри: [19, 9] зріз 2.0 → груп: 2 · розміри: [19, 9] зріз 3.0 → груп: 1 · розміри: [28]
Одне дерево — і скільки завгодно розбиттів. Кількість груп обираєш після побудови,дивлячись на висоти: між 1.6 і 2.8 нічого не змінюється, а це означає, що поділ на двігрупи тут стійкий.Подивимось, що це за групи, коли ріжемо на три.
In [16]:
три_групи = fcluster(дерево, 3, criterion="maxclust")
опис = pd.DataFrame({
"група": [f"група {c}" for c in sorted(set(три_групи))],
"оголошень": [int((три_групи == c).sum()) for c in sorted(set(три_групи))],
"медіанна ціна": [int(np.median(ціни[вибрані][три_групи == c])) for c in sorted(set(три_групи))],
"медіанний рік": [int(np.median(роки[вибрані][три_групи == c])) for c in sorted(set(три_групи))],
})
print(опис.to_string(index=False))
група оголошень медіанна ціна медіанний рік група 1 9 12920 2024 група 2 5 5400 2018 група 3 14 2045 2020
DBSCAN на всій дошціТепер щільність на справжніх даних. Візьмемо eps = 0.3 і min_samples = 5 — і подивимосьне стільки на кластери, скільки на шум.¶
In [17]:
мітки_дошки = DBSCAN(eps=0.3, min_samples=5).fit_predict(масштабовані)
шум = мітки_дошки == -1
print("кластерів:", len(set(мітки_дошки[~шум])))
print("розміри:", sorted(np.bincount(мітки_дошки[~шум]).tolist(), reverse=True))
print("шумових оголошень:", int(шум.sum()))
print("з них шахрайських:", int(шахрайське_справді[шум].sum()),
f"({100 * шахрайське_справді[шум].mean():.1f} %)")
print("\nціни шумових оголошень, грн:")
print(np.sort(ціни[шум]).astype(int))
кластерів: 12 розміри: [157, 144, 138, 137, 123, 120, 118, 112, 7, 7, 6, 5] шумових оголошень: 26 з них шахрайських: 25 (96.2 %) ціни шумових оголошень, грн: [ 130 190 200 290 290 330 360 370 390 420 420 430 550 590 730 850 880 13130 15010 20280 27960 38570 45320 52620 59840 83500]
Шум DBSCAN — це майже чисті шахраї: ціни-приманки по 130–880 грн і завищені десятки тисяч.Порахуємо це як детектор тими самими метриками, що й утемі 05, і порівняємо з двома попередніми спробами.
In [18]:
прогноз_за_шумом = шум.astype(int)
print(f"precision: {precision_score(шахрайське_справді, прогноз_за_шумом):.3f}")
print(f"recall: {recall_score(шахрайське_справді, прогноз_за_шумом):.3f}")
print(f"F1: {f1_score(шахрайське_справді, прогноз_за_шумом):.3f}")
print("\nдля порівняння:")
print(" найдешевший кластер k-means (тема 11): F1 = 0.296")
print(" модель із учителем (тема 29): F1 = 0.796")
precision: 0.962 recall: 0.180 F1: 0.303 для порівняння: найдешевший кластер k-means (тема 11): F1 = 0.296 модель із учителем (тема 29): F1 = 0.796
Точність майже ідеальна, повнота мізерна: DBSCAN ловить лише тих шахраїв, які виставилигеть дику ціну. Звичайний шахрай сидить у гущі оголошень, і жодна щільність його невідрізнить — саме тому в темі 29 довелось будувати ознаку «ціна відносно типової».А тепер обіцяна чесність про 12 кластерів: це не сегменти ринку.
In [19]:
крок_між_роками = 1 / роки.std()
print(f"один рік у z-оцінках = {крок_між_роками:.3f}")
print("а eps ми взяли 0.3 — менше, ніж відстань між сусідніми роками\n")
for eps in [0.2, 0.3, 0.45, 0.5, 0.6]:
мітки = DBSCAN(eps=eps, min_samples=5).fit_predict(масштабовані)
розміри = sorted(np.bincount(мітки[мітки >= 0]).tolist(), reverse=True)
print(f"eps={eps:.2f}: кластерів {len(розміри):2d}, шум {int((мітки == -1).sum()):3d}, "
f"найбільший {розміри[0] if розміри else 0}")
один рік у z-оцінках = 0.433 а eps ми взяли 0.3 — менше, ніж відстань між сусідніми роками eps=0.20: кластерів 12, шум 44, найбільший 157
eps=0.30: кластерів 12, шум 26, найбільший 157 eps=0.45: кластерів 3, шум 9, найбільший 1077
eps=0.50: кластерів 2, шум 6, найбільший 1089 eps=0.60: кластерів 2, шум 1, найбільший 1094
Ось і вся відповідь DBSCAN про дошку: поки радіус менший за відстань між роками, він ріжедані на горизонтальні смуги «всі оголошення 2019 року»; щойно радіус її перевищує — усядошка стає одним кластером. Проміжного варіанта немає, бо щільнісно відокремлених групна цій дошці не існує.### Ієрархічна на всій дошціОстанній крок: чотири звʼязки на 1 100 оголошеннях, три групи. Тут добре видноланцюжковий ефект.
In [20]:
рядки = []
for звʼязок in ["single", "complete", "average", "ward"]:
мітки = AgglomerativeClustering(n_clusters=3, linkage=звʼязок).fit_predict(масштабовані)
рядки.append({
"звʼязок": звʼязок,
"розміри груп": sorted(np.bincount(мітки).tolist(), reverse=True),
"ARI з шахрайством": round(adjusted_rand_score(шахрайське_справді, мітки), 4),
})
порівняння_звʼязків = pd.DataFrame(рядки)
print(порівняння_звʼязків.to_string(index=False))
мітки_kmeans = KMeans(n_clusters=3, n_init=10, random_state=42).fit_predict(масштабовані)
мітки_ward = AgglomerativeClustering(n_clusters=3, linkage="ward").fit_predict(масштабовані)
print(f"\nARI між k-means і Вордом на дошці: {adjusted_rand_score(мітки_kmeans, мітки_ward):.3f}")
print("розміри k-means:", sorted(np.bincount(мітки_kmeans).tolist(), reverse=True))
звʼязок розміри груп ARI з шахрайством
single [1094, 5, 1] 0.0029
complete [656, 433, 11] 0.0156
average [1089, 8, 3] 0.0420
ward [439, 360, 301] -0.0025
ARI між k-means і Вордом на дошці: 0.353 розміри k-means: [481, 355, 264]
Одиночний і середній звʼязки дали безглузді розбиття: один велетень і дві порошинки —класичний ланцюжковий ефект на реальних даних. Ворд дав співмірні групи, але навіть вінне збігається з k-means: ARI близько 0.35, тобто це помітно інші сегменти, хоч обидваметоди мінімізують ту саму суму квадратів.І жоден із методів не має нічого спільного з колонкою шахрайське — ARI біля нуля. Це непоразка: кластеризація знаходить те, що є в геометрії даних, а не те, що нам цікаво.---## Завдання### 🟢 Рівень 1 — БазаДодай до трьох форм четверту — два півмісяці (у sklearn цеdatasets.make_moons(n_samples=200, noise=0.06, random_state=42)) і прожени на ній усітри методи так само, як у розділі 3.Що має бути в результаті: рядок таблиці з трьома значеннями ARI й одне речення про те,який метод переміг і чому саме він.### 🟡 Рівень 2 — ПлюсДосліди, наскільки вузька «смужка правильних відповідей» у DBSCAN. Для набору«вкладені кільця» побудуй сітку: eps від 0.2 до 1.2 з кроком 0.05, min_samples від3 до 10. Для кожної пари порахуй ARI зі справжніми групами й намалюй теплову карту(plt.imshow).Питання, на які треба відповісти числами: скільки пар із сітки дають ARI вище 0.95? Якачастка це від усієї сітки? Чи є серед них суцільна область, чи вони розкидані?### 🔴 Рівень 3 — ВикликРеалізуй агломеративну кластеризацію з нуля для звʼязків single і complete:1. почни з матриці попарних відстаней і списку груп, у кожній по одній точці;2. знайди дві найближчі групи, злий їх, запиши висоту злиття;3. перерахуй відстані від нової групи до решти (для single — мінімум із двох, для complete — максимум);4. повтори, поки не лишиться одна група.Порівняй свої мітки з AgglomerativeClustering на всіх трьох формах при n_clusters=2.Зроблено, якщо adjusted_rand_score між твоїм і бібліотечним розбиттям дорівнює 1.0 дляобох звʼязків на всіх трьох наборах — і якщо ти можеш пояснити одним реченням, чомуsingle і complete можна рахувати на звичайних відстанях, а Ворда — ні.