以 OPTICS 演算法識別階層性密度差異的時空群聚結構

Abstract

點事件之時空群聚代表事件之發生熱區，過去之時空群聚演算法僅能識別出密度值高於特定閾值之群聚範圍，無法識別出具備密度差異與階層性之時空群聚結構。本研究基於 OPTICS 演算法，發展 HST-OPTICS 演算法，此演算法可以用來識別點事件階層性時空群聚之密度斷層，進而獲取完整之時空群聚結構。密度斷層發生在具有密度明顯差異的時空邊界，邊界內的範圍可識別為群聚範圍，範圍內的時空密度與範圍外的時空度具有極劇差異。所得之時空群聚除了具排除雜訊點、總群聚數非經給定、群聚範圍明確以及形狀任意之特性，由群聚結構亦可識別出過去演算法無法得知的密度差異與群聚階層關係。本研究發展 HST-OPTICS 演算法時，放寬 OPTICS 演算法中陡度的定義，彈性地查找密度斷層範圍並進一步切分出時空群聚結構，並模擬群聚數、階層關係不同之多組群聚結構，以驗證演算法可以找出過去時空群聚演算法無法有效識別之階層性時空群聚結構。研究結果表示，HST-OPTICS 可以有效識別出重疊且具有高低密度差異之群聚結構、多個群聚隸屬於同一群聚的階層性時空群聚結構，以及時空群聚範圍變動且具備階層性關係的時空群聚結構。未來研究可以善用此演算法於各領域之實務應用中，探討合適之參數設定方式，並著重階層性時空群聚驗證指標設計以及演算法效能提高。

The HST-OPTICS algorithm improves upon previous spatio-temporal clustering methods by identifying density faults in hierarchical clusters. This approach reveals complete clustering structures, including density differences and hierarchical relationships previously undetectable. The algorithm relaxes the OPTICS steepness definition, allowing for flexible identification of density fault ranges. It can detect overlapping clusters with varying density, hierarchical structures where multiple clusters belong to one cluster, and clustering structures with varying spatial ranges. HST-OPTICS produces clusters with noise exclusion, an undefined total count, clear boundaries, and arbitrary shapes. Simulations have verified its effectiveness in identifying complex hierarchical spatio-temporal clustering structures. Future work could explore practical applications, the design of verification metrics, and efficiency improvements.