3.3 Міри подібності

Важливим етапом кластерного аналізу є обчислення міри подібності між об’єктами, оскільки при здійсненні кластеризації у кожен кластер повинні потрапити об’єкти з подібними характеристиками. У кожній конкретній задачі цей вибір здійснюється різним чином, з урахуванням головної мети дослідження, фізичної і статистичної природи використовуваної інформації тощо.

У кластерному аналізі можуть використовуватися міри подібності: коефіцієнти кореляції, міри відстані, коефіцієнти асоціативності, імовірнісні коефіцієнти подібності (рис. 3.7):

Міри подібності в кластерному аналізі

Кожен з цих показників має свої переваги та недоліки, які попередньо потрібно врахувати.

Міри подібності в кластерному аналізі

Рис. 3.7: Міри подібності в кластерному аналізі

У процесі кластеризації кожен об’єкт розглядається як точка в багатовимірному просторі ознак, що використовуються для його опису. Подібність і відмінність між точками знаходяться у відповідності з метричними відстанями між ними. Для цього однорідність об’єктів задається:

  • введенням правила обчислень відстаней \(d(x_i,x_j)\) між будь-якою парою досліджуваних об’єктів \((x_1,x_2,…,x_n)\);
  • заданням деякої функції \(r(x_i,x_j)\), що характеризує ступінь близькості \(i\)‑го і \(j\)‑го об’єктів.

Міра подібності є метрикою, якщо виконуються наступні умови:

  1. Симетрія. Відстань між об’єктами \(x\) і \(y\) повинна задовольняти: \[d(x,y)=d(y,x)≥0;\]
  2. Нерівність трикутника. Відстань між об’єктами \(x\), \(y\) і \(z\): \[d(x,y)≤d(x,z)+d(y,z);\]
  3. Розрізненість нетотожних об’єктів. Дано два об’єкта \(x\) і \(y\); якщо \[d(x,y)≠0,\,\,то\,\,\,x≠y;\]
  4. Нерозрізненість ідентичних об’єктів. Якщо \(x\) і \(x’\) ідентичні, то: \[d(x, x')=0.\]

Розглянемо міри подібності, які використовують у кластерному аналізі: коефіцієнт кореляції, ймовірнісний коефіцієнт подібності, міри відстані, коефіцієнти асоціативності.

Коефіцієнт кореляції

Природна міра подібності.

\[ r_{ij}=\frac{\sum_{h=1}^N(x_{hi}-m_i)(x_{hj}-m_j)}{\delta_i \delta_j}, \]

\[ -1\leq r_{ij}\leq 1, \] де \(x_{hi}\), \(x_{hj}\) — значення \(h\)-ї ознаки для \(i\)-го та \(j\)-го об’єктів;

\(m_i, m_j, δ_i, δ_j\) — відповідні середні та середньоквадратичні відхилення для характеристик \(i\) і \(j.\)

\(r_{ij}=-1\) — наявність зворотного тісного між об’єктами \(i\) і \(j\);

\(r_{ij}=0\) — відсутність зв’язку між об’єктами \(i\) і \(j\);

\(r_{ij}=1\) — наявність прямого тісного зв’язку між об’єктами \(i\) і \(j\).

Імовірнісний коефіцієнт подібності

Міра близькості імовірнісного типу.

\[ I_{ij}=\sum_{x,y}p_{xy}log\frac{p_{xy}}{p_x^ip_y^j}, \]

де \(p_{xy}\) — ймовірність спільної появи ознак \(x\) і \(y\);

\(p_x^i\) — ймовірність появи ознаки \(x\) в об’єкті \(i\);

\(p_y^j\) — ймовірність появи ознаки \(y\) в об’єкті \(j\).

Міри відстані

У кластерному аналізі використовують наступні міри відстані: евклідова відстань, зважена евклідова відстань, city-block (Мангетенська), відстань Мінковського.

Евклідова: \[ d_{ij}\sqrt{\sum_{k=1}^m(x_{ik}-x_{jk})^2}, \] де \(d_{ij}\) — відстань між об’єктами \(i\) і \(j, i, j=1,…,n; k=1,…,m\);

\(x_{ik}\) — значення \(k\)-ї змінної для \(i\)-го об’єкта;

\(x_{jk}\) — значення \(k\)-ї змінної для \(j\)-го об’єкта.

Зважена евклідова: \[ d_{ij}=\sqrt{(\sum_{k=1}^m w_k\cdot(x_{ik}-x_{jk} )^2 )}, \] де \(w_k\) — вага \(k\)-ї ознаки, \(0≤w≤1\).

City-block (Мангетенська): \[ d_{ij}=\sum_{k=1}^m \mid x_{ik}-x_{jk}\mid. \]

Відстань Мінковського: \[ d_{ij}=(\sum_{k=1}^m|x_{ik}-x_{jk}|^p )^{1/r}, \] де \(p, r\) — параметри, що визначені користувачем.

Відстань Махаланобіса: \[ d_{ij}=(X_i-X_j )^T\cdot S^{-1}\cdot(X_i-X_j), \] де \(X_i, X_j\) — вектори значень \(i\)-го та \(j\)-го об’єктів;

\(S\) — загальна коваріаційна матриця.

Коефіцієнти асоціативності

Для бінарних даних, змінні, що беруть участь в конструюванні цих заходів, описуються таблицею асоціативності, де «1» вказує на наявність змінної, а «0» — її відсутність:

\(1\) \(0\)
\(1\) \(a\) \(b\)
\(0\) \(c\) \(d\)

Простий коефіцієнт зустрічності: \[ S=\frac{(a+d)}{(a+b+c+d)}. \]

Коефіцієнт Жаккара: \[ J=\frac{a}{(a+b+c)}. \]

Коефіцієнт Гауера: \[ S_{ij}=\frac{\sum_{k=1}^pS_{ijk}}{\sum_{k=1}^pW_{ijk}}, \] де \(S_{ijk}\) — «вклад» у подібність об’єктів, який враховує значущість ознаки \(k\), у порівнянні об’єктів \(i\) і \(j\);

\(W_{ijk}\) — ваговий коефіцієнт, який приймає значення 1, якщо порівняння об’єктів за ознакою \(k\) варто враховувати і 0 — в іншому випадку.