Tezislər / Theses
Sıxlığa əsaslanan klasterləşdirmə alqoritmləri
Yüklə 17,55 Mb. Pdf görüntüsü
|
- Bu səhifədəki naviqasiya:
- THE 3 rd INTERNATIONAL SCIENTIFIC CONFERENCES OF STUDENTS AND YOUNG RESEARCHERS
|
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 |