2. Sıxlığa əsaslanan klasterləşdirmə alqoritmləri
Sıxlığa əsaslanan klasterləşdirmə alqoritmləri məlumat obyektlərini
obyektlər arasındakı sıxlığa əsaslanaraq qruplaşdırır [Xu R. & Wunsch D.,
2005].
THE 3
rd
INTERNATIONAL SCIENTIFIC CONFERENCES OF STUDENTS AND YOUNG RESEARCHERS
dedicated to the 99
th
anniversary of the National Leader of Azerbaijan Heydar Aliyev
132
Cədvəl 1
. Sıxlığa əsaslanan klasterləşdirmə alqoritmləri
Sıxlığa əsaslanan klasterləşdirmə alqoritmlərində iki əsas parametrlər
mövcuddur: Eps (Epsilon,
𝜀
) – qonşuluqları təyin edən məsafə. İki nöqtə ara-
sındakı məsafə Eps-dən az və ya bərabər olduqda qonşu hesab olunur. Ri-
yazi olaraq, bu şəkildə ifadə olunur:
𝑁 𝜀(𝑎) = 𝑏 ∈ 𝐷|𝑑𝑖𝑠𝑡(𝑎, 𝑏)
𝜀
.
MinPts
(Minimum Points) - klasteri təyin etmək üçün minimum məlumat nöqtələrinin
sayı. Bu iki parametrə əsasən sıxlığa əsaslanan klasterləşdirmə alqoritmi
nöqtələri üç fərqli nöqtələr tipinə ayırır:
Əsas nöqtələr – sıx qonşuluqda yerləşən nöqtələr
(|Nε(b)| ≥ MinPts)
;
qonşuluq radiusundakı
Eps
ən azı
MinPts
nöqtəsindən ibarətdirsə, yəni qon-
şuluqdakı sıxlıq bəzi həddi keçməlidirsə, bu nöqtə
ə
sas nöqt
ə
adlanır. Sərhəd
nöqtələr –
Eps
qonşuluğu ən az minimum sayda (
MinPts
) nöqtə ehtiva etmə-
yən, yəni hər hansı klasterə aid olan, ancaq sıx qonşuluqda yerləşməyən
nöqtələrə
s
ə
rh
ə
d nöqt
ə
deyilir. Küy nöqtələr – yəni heç bir klasterə aid olmayan
nöqtələr; əgər bir nöqtə əsas nöqtə deyilsə və hər hansı əsas nöqtədən əldə
edilə bilən nöqtə deyilsə, bu nöqtə
küy nöqt
ə
kimi qiymətləndirilir.
Birbaşa sıxlıqla əldə edilə bilən –
𝑎
nöqtəsi
𝑏
nöqtəsinin
𝜀
qonşuluğunda
yerləşirsə və
𝑏
əsas nöqtədirsə, onda
𝑎
nöqtəsi
𝑏
nöqtəsindən
birba
ş
a s
ı
xl
ı
q
ə
ld
ə
edil
ə
bil
ə
n
nöqtədir.
Sıxlıq əldə edilə bilən -
𝑎 , … , 𝑎 , 𝑝 = 𝑏, 𝑎 = 𝑏
nöqtələr ardıcıllığında
𝑎
nöqtəsi
𝑎
nöqtəsindən birbaşa sıxlıq əldə edilə bilən olduğundan
𝐸𝑝𝑠
və
𝑀𝑖𝑛𝑃𝑡𝑠
parametrlərinə görə
𝑎
nöqtəsi
𝑏
nöqtəsindən
s
ı
xl
ı
q
ə
ld
ə
edil
ə
bil
ə
n
nöqtədir.
Sıxlığa bağlı - əgər
Eps və MinPts
parametrlərinə görə
𝑐
nöqtəsi hər iki
𝑎
və
𝑏
nöqtəsindən sıxlıq əldə edilə bilən nöqtədirsə, onda həmin parametrlərə
görə anöqtəsi b nöqtəsindən
s
ı
xl
ı
ğ
a ba
ğ
l
ı
nöqtədir.
DBSCAN
klasterləşdirmə alqoritmi qeyri-sferik formalı klasterləri tapmaq
üçün nəzərdə tutulmuşdur. DBSCAN alqoritminin işləmə prosesini aşağıda
kimi şərh edə bilərik:
Alqoritm ixtiyari bir nöqtədən başlayır və qonşuluq məlumatları
ε(Eps)
parametrindən alınır. Bu nöqtə
MinPts
parametrinin
ε
qonşuluğunda yerlə-
şirsə, klaster əmələ gətirir. Əks halda nöqtə küy nöqtə kimi işarələnir. Proses
yeni bir klasterin bir hissəsi ola bilən və ya küy nöqtələr kimi işarələnən yeni
bir nöqtə ilə yenidən başlayır [Bäcklund, 2011].
Sıxlığa əsaslanan klasterləşdirmə
alqoritmləri
DBSCAN
OPTİCS
DENCLUE
|