OPTİK algoritması - OPTICS algorithm

Kümeleme yapısını tanımlamak için noktaları sıralama ( OPTICS ), uzamsal verilerde yoğunluğa dayalı kümeleri bulmaya yönelik bir algoritmadır . Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel ve Jörg Sander tarafından sunuldu . Temel fikri DBSCAN'a benzer , ancak DBSCAN'ın en büyük zayıflıklarından birini ele alıyor: değişen yoğunluktaki verilerde anlamlı kümeleri tespit etme sorunu. Bunu yapmak için, veritabanının noktaları (doğrusal olarak) öyle sıralanır ki, sıralamada uzamsal olarak en yakın noktalar komşu olur. Ek olarak, her bir nokta için, her iki noktanın da aynı kümeye ait olması için bir küme için kabul edilmesi gereken yoğunluğu temsil eden özel bir mesafe saklanır. Bu bir dendrogram olarak temsil edilir .

Temel fikir

Gibi DBSCAN : OPTİK iki parametre gerektiren $£ değenni$ dikkate maksimum mesafe (yarıçap) tarif ve $MinPts$ bir küme oluşturmak için gerekli puan sayısını tanımlayan. Bir $p$ noktası , $ε$ -komşusunda ( $p$ noktasının kendisi dahil ) en azından $MinPts$ noktaları bulunursa , bir çekirdek noktadır . DBSCAN'ın aksine , OPTICS ayrıca daha yoğun bir şekilde paketlenmiş bir kümenin parçası olan noktaları da dikkate alır, bu nedenle her noktaya $MinPts'nin$ en yakın noktasına olan mesafeyi tanımlayan bir çekirdek mesafe atanır : $N_{\varepsilon }(p)$

{\text{çekirdek-dist}}_{\mathit {\varepsilon ,MinPts}}(p)={\begin{durumlar}{\text{TANIMLANMAMIŞ}}&{\metin{eğer }}|N_ {\varepsilon }(p)|<{\mathit {MinPts}}\\{\mathit {MinPts}}{\text{-}}N_{\varepsilon }(p)&{\text{aksi takdirde en küçük mesafe) }}\end{durumlar}}

Ulaşılabilirlik mesafeli bir noktası $o$ noktası gelen $p$ ya arasındaki mesafedir $o$ ve $p$ , ya da çekirdek mesafe $p$ büyük olanının:

{\text{erişilebilirlik-dist}}_{\mathit {\varepsilon ,MinPts}}(o,p)={\begin{cases}{\text{TANIMLANMAMIŞ}}&{\text{if }} |N_{\varepsilon }(p)|<{\mathit {MinPts}}\\\max({\text{core-dist}}_{\mathit {\varepsilon ,MinPts}}(p),{\text {dist}}(p,o))&{\metin{aksi halde}}\end{durumlar}}

Eğer $p$ ve $o$ en yakın komşu, bu zamanlar sahip varsaymak gerekir $p$ ve $o$ aynı kümeye aittir. $\varepsilon '<\varepsilon$

Yeterince yoğun küme (wrt $ε$ ) mevcut değilse, hem çekirdek-mesafe hem de erişilebilirlik-mesafe tanımsızdır . Yeterince büyük bir $ε$ verildiğinde , bu asla olmaz, ancak daha sonra her $ε$ -komşu sorgusu tüm veritabanını döndürür ve çalışma zamanı ile sonuçlanır . Bu nedenle, artık ilginç olmayan kümelerin yoğunluğunu kesmek ve algoritmayı hızlandırmak için $ε$ parametresi gereklidir. ${\ Displaystyle O(n^{2})}$

$ε$ parametresi kesinlikle gerekli değildir. Basitçe mümkün olan maksimum değere ayarlanabilir. Bununla birlikte, bir uzamsal indeks mevcut olduğunda, karmaşıklık açısından pratik bir rol oynar. OPTICS, bu parametreyi kaldırarak DBSCAN'dan, en azından sadece maksimum değeri vermek zorunda kalacak şekilde özetler.

sözde kod

OPTICS'in temel yaklaşımı DBSCAN'a benzer , ancak bilinen, ancak şimdiye kadar işlenmemiş küme üyelerini bir kümede tutmak yerine, bir öncelik kuyruğunda tutulurlar (örneğin, dizinlenmiş bir yığın kullanarak ).

function OPTICS(DB, eps, MinPts) is
    for each point p of DB do
        p.reachability-distance = UNDEFINED
    for each unprocessed point p of DB do
        N = getNeighbors(p, eps)
        mark p as processed
        output p to the ordered list
        if core-distance(p, eps, MinPts) != UNDEFINED then
            Seeds = empty priority queue
            update(N, p, Seeds, eps, MinPts)
            for each next q in Seeds do
                N' = getNeighbors(q, eps)
                mark q as processed
                output q to the ordered list
                if core-distance(q, eps, MinPts) != UNDEFINED do
                    update(N', q, Seeds, eps, MinPts)

update() öğesinde, Seeds öncelik sırası , sırasıyla ve öğesinin -neighborhood ile güncellenir : ${\görüntüleme stili\varepsilon }$ ${\görüntüleme stili p}$ ${\görüntüleme stili q}$

function update(N, p, Seeds, eps, MinPts) is
    coredist = core-distance(p, eps, MinPts)
    for each o in N
        if o is not processed then
            new-reach-dist = max(coredist, dist(p,o))
            if o.reachability-distance == UNDEFINED then // o is not in Seeds
                o.reachability-distance = new-reach-dist
                Seeds.insert(o, new-reach-dist)
            else               // o in Seeds, check for improvement
                if new-reach-dist < o.reachability-distance then
                    o.reachability-distance = new-reach-dist
                    Seeds.move-up(o, new-reach-dist)

OPTICS, bu nedenle, en küçük erişilebilirlik mesafeleriyle açıklamalı olarak belirli bir sıralamadaki noktaları çıkarır (orijinal algoritmada, çekirdek mesafe de dışa aktarılır, ancak bu daha sonraki işlemler için gerekli değildir).

Kümeleri ayıklama

Bir erişilebilirlik grafiği (özel bir tür dendrogram ) kullanılarak, kümelerin hiyerarşik yapısı kolayca elde edilebilir. OPTICS tarafından işlenen noktaların x ekseninde ve y ekseninde erişilebilirlik mesafesinin sıralandığı 2B bir çizimdir. Bir kümeye ait noktalar, en yakın komşularına düşük bir erişilebilirlik mesafesine sahip olduğundan, kümeler erişilebilirlik grafiğinde vadiler olarak görünür. Vadi ne kadar derin olursa, küme o kadar yoğun olur.

Yukarıdaki resim bu kavramı göstermektedir. Sol üst alanında, sentetik bir örnek veri seti gösterilmektedir. Sağ üst kısım , OPTICS tarafından üretilen yayılma ağacını görselleştirir ve alt kısım, OPTICS tarafından hesaplanan erişilebilirlik grafiğini gösterir. Bu çizimdeki renkler etiketlerdir ve algoritma tarafından hesaplanmaz; ancak arsadaki vadilerin yukarıdaki veri setindeki kümelere nasıl karşılık geldiği iyi görülebilir. Bu görüntüdeki sarı noktalar gürültü olarak kabul edilir ve erişilebilirlik grafiğinde hiçbir vadi bulunmaz. Hiyerarşik bir sonuçta her yerde bulunan "tüm veriler" kümesi dışında genellikle kümelere atanmazlar.

Bu çizimden kümelerin çıkarılması, görsel incelemeden sonra x ekseninde bir aralık seçilerek, y ekseninde bir eşik seçilerek manuel olarak yapılabilir (sonuç, aynı ve minPts parametreleriyle DBSCAN kümeleme sonucuna benzer ; burada 0.1 değeri iyi sonuçlar verebilir) veya vadileri diklik, diz tespiti veya yerel maksimum ile tespit etmeye çalışan farklı algoritmalarla. Bu şekilde elde edilen kümelemeler genellikle hiyerarşiktir ve tek bir DBSCAN çalıştırmasıyla elde edilemez. ${\görüntüleme stili\varepsilon }$

karmaşıklık

Gibi DBSCAN , OPTİK birer kez noktası ve gerçekleştirir işler -neighborhood sorgu bu işlem sırasında. Çalışma zamanında bir komşuluk sorgusu veren bir uzamsal dizin verildiğinde , genel bir çalışma zamanı elde edilir. Orijinal OPTICS belgesinin yazarları, DBSCAN'a kıyasla 1,6'lık bir gerçek sabit yavaşlama faktörü bildirmektedir. Çok büyük bir değer, bir komşuluk sorgusunun maliyetini doğrusal karmaşıklığa yükseltebileceğinden, değerinin algoritmanın maliyetini büyük ölçüde etkileyebileceğini unutmayın . ${\görüntüleme stili\varepsilon }$ ${\ Displaystyle O(\log n)}$ ${\ Displaystyle O(n\cdot \log n)}$ ${\görüntüleme stili\varepsilon }$

Özellikle, seçim (veri kümesindeki maksimum mesafeden daha büyük) mümkündür, ancak her komşu sorgusu tam veri kümesini döndürdüğü için ikinci dereceden karmaşıklığa yol açar. Hiçbir uzamsal indeks mevcut olmadığında bile, bu, yığının yönetilmesinde ek maliyet getirir. Bu nedenle veri seti için uygun seçilmelidir. $\varepsilon >\max _{x,y}d(x,y)$ ${\görüntüleme stili\varepsilon }$

Uzantılar

OPTICS-OF, OPTICS'e dayalı bir aykırı değer algılama algoritmasıdır. Ana kullanım, mevcut bir OPTICS çalışmasından aykırı değerlerin, farklı bir aykırı değer algılama yöntemi kullanmaya kıyasla düşük maliyetle çıkarılmasıdır. Daha iyi bilinen LOF versiyonu aynı kavramlara dayanmaktadır.

DeLi-Clu, Density-Link-Clustering, tek bağlantılı kümeleme ve OPTICS'ten gelen fikirleri birleştirerek parametreyi ortadan kaldırır ve OPTICS'e göre performans iyileştirmeleri sunar. ${\görüntüleme stili\varepsilon }$

HiSC, OPTICS'e dayalı hiyerarşik bir alt uzay kümeleme (eksen-paralel) yöntemidir.

HiCO, OPTICS'e dayalı hiyerarşik bir korelasyon kümeleme algoritmasıdır.

DiSH, HiSC üzerinde daha karmaşık hiyerarşiler bulabilen bir gelişmedir.

FOPTICS, rastgele projeksiyonlar kullanan daha hızlı bir uygulamadır.

HDBSCAN*, kümelerden sınır noktalarını hariç tutarak ve dolayısıyla Hartigan'ın yoğunluk seviyelerinin temel tanımını daha sıkı takip ederek, DBSCAN'ın iyileştirilmesine dayanmaktadır.

kullanılabilirlik

OPTICS, OPTICS-OF, DeLi-Clu, HiSC, HiCO ve DiSH'nin Java uygulamaları ELKI veri madenciliği çerçevesinde mevcuttur (çeşitli mesafe fonksiyonları için indeks hızlandırmalı ve ξ çıkarma yöntemini kullanan otomatik küme çıkarma ile). Diğer Java uygulamaları, Weka uzantısını içerir (ξ küme çıkarma desteği yoktur).

R, paket "dbscan" bir ile (her ikisi de geleneksel dbscan benzeri ve ξ küme ekstre ile) optik C ++ uygulaması içerir kd ağaç Öklid mesafe sadece dizin hızlanma için.

OPTICS'in Python uygulamaları, PyClustering kitaplığında ve scikit-learn içinde mevcuttur . HDBSCAN*, hdbscan kitaplığında mevcuttur.

Languages

In other projects