動的クラスタリングとクラスター変化検出

時間によってクラスター構造が変化するデータに対するクラスタリングについてのメモ

種別 †

時間によってクラスター構造が変化することを前提としてクラスター構造の変化を検出することを動的クラスタリング (dynamic clustering) と呼んでいたが、調査の結果、動的クラスタリングは「前回のクラスタリング結果を使ってクラスタリングを効率的に行うこと」という意味で使われており、前回のクラスタリング結果と今回のクラスタリング結果の違いを検出することはクラスター進化分析 (analysis of evolving clusters) やデータ・ストリーム・クラスタリング (data stream clustering) やクラスター変化検出 (cluster change detection) と呼ばれていることがわかった。

データ・ストリーム・クラスタリングという名前は時系列クラスタリングや動的クラスタリングを含む広い意味に受け取れてしまうので、ここでは、クラスター変化抽出と呼ぶことにする。

• 動的クラスタリング (Dynamic Clustering)
  • 以前のクラスタリング結果を使ってクラスタリングを効率的に行う手法
• クラスター変化検出 (Cluster Change Detection)
  • 以前のクラスタリング結果と今回のクラスタリング結果の違いを検出する方法
  • クラスター進化分析 (Cluster Evolution Analysis) ともいう

動的クラスタリング †

Gu (2022) による動的クラスタリングの定義 †

原文 †

Given the dataset [math]D[/math] and its clustering results [math]\mathcal{L}_D[/math], let [math]D_\mathit{new}[/math] be a new set of objects with some updates on [math]D[/math] where [math]D \cap D_\mathit{new} \neq \emptyset[/math]. Dynamic clustering computes the clustering results of [math]D_\mathit{new}[/math] based on [math]\mathcal{L}_D[/math]. The dynamic clustering is denoted by [math]F[/math] and its clustering result is denoted as [math]F(D, D_\mathit{new}, \mathcal{L}_D)[/math].

訳 †

データセット [math]D[/math] とそのクラスタリング結果 [math]\mathcal{L}_D[/math] が与えられ、[math]D[/math] を更新してできた新しいデータセットを [math]D_\mathit{new}[/math] とする。 このとき、[math]D \cap D_\mathit{new} \neq \emptyset[/math]、つまり、[math]D[/math] と [math]D_\mathit{new}[/math] には共通するデータが存在する。 動的クラスタリングは、[math]\mathcal{L}_D[/math] に基づいて [math]D_\mathit{new}[/math] のクラスタリング結果を計算する。 動的クラスタリングを [math]F[/math]、その結果を[math]F(D, D_\mathit{new}, \mathcal{L}_D)[/math] と表す。

動的クラスタリングの目的 †

データセット [math]D[/math] が与えられたときに [math]D[/math] のクラスタリング結果 [math]\mathcal{L}_D[/math] を得るバッチ・アルゴリズム [math]\mathcal{L}_D = B(D)[/math] に対して、[math]B(D_\mathit{new})[/math] より効率的に [math]F(D, D_\mathit{new}, \mathcal{L}_D) \approx \mathcal{L}_{D_\mathit{new}}[/math] を得ること。

Gruenheid (2014) による動的クラスタリングの定義 †

Record linkageは、二つのデータセットの中からペアになる事例を見つけること。 Gruenheid (2014) では incremental record linkage という名前を使っているけど、Gu (2022) のこの論文を引用して定義しており、動的クラスタリングだと考えて良いと思う。

原文 †

Let [math]D[/math] be a set of records and [math]\Delta D[/math] be an increment to [math]D[/math]. Let [math]\mathcal{L}_D[/math] be the clustering of records in [math]D[/math]. Incremental linkage clusters records in [math]D + \Delta D[/math] based on [math]\mathcal{L}_D[/math]. We denote the incremental linkage method by [math]f[/math], and denote the results by [math]f(D, \Delta D, \mathcal{L}_D)[/math].

訳 †

[math]D[/math] をレコードの集合、[math]\Delta D[/math] を [math]D[/math]　の増分、[math]D[/math]　のクラスタリング結果を [math]\mathcal{L}_D[/math] とする。 動的クラスタリング は、[math]\mathcal{L}_D[/math]　に基づいて [math]D + \Delta D[/math] に含まれるレコードをクラスタリングする。 動的クラスタリングの手法を [math]f[/math]、その結果を [math]f(D, \Delta D, \mathcal{L}_D)[/math] と表す。

動的クラスタリングの目的 †

1. [math]D+\Delta D[/math] のクラスタリング [math]F(D + \Delta D)[/math] より動的クラスタリング [math]f(D, \Delta D, \mathcal{L}_D)[/math] を速く実行すること
2. 動的クラスタリングの結果 [math]f(D, \Delta D, \mathcal{L}_D)[/math] と（バッチ）クラスタリングの結果 [math]F(D + \Delta D)[/math] が似ていること、つまり [math]f(D, \Delta D, \mathcal{L}_D \approx F(D + \Delta D)[/math]

動的クラスタリングに関する論文 †

• Gu B, Kargar S, and Nawab F (2022). Efficient dynamic clustering: Capturing patterns from historical cluster evolution. Open Proceedings 25:351–363. doi: 10.48786/edbt.2022.21
  • 動的クラスタリングの定義
• Gruenheid A, Dong XL, and Srivastava D (2014). Incremental record linkage. VLDB Endowment 7(9):697–708. doi: 10.14778/2732939.2732943 (PDF)
  • 動的クラスタリングの定義
  • Incremental linkage と呼んでいる

クラスター変化検出 (Cluster Change Detection) †

Aggarwal (2003) ではクラスター進化分析 (Cluster Evolution Analysis or Analysis of Evolving Clusters) と呼ばれていて、 Zubaroğlu (2021) はデータ・ストリーム・クラスタリング (Data Stream Clustering) としてサーベイ論文を書いている。 しかし、データ・ストリーム・クラスタリングという名前だと動的クラスタリング (Dynamic Clustering) も含まれてしまうので、クラスター変化抽出 (Cluster Change Detection) とするのが適切では。

Aggarwal (2003) によるクラスター進化分析の説明 †

原文 †

Many interesting changes can be recorded by an analyst in an evolving data stream for effective use in a number of business applications [1]. In the context of the clustering problem, such evolution analysis also has significant importance. For example, an analyst may wish to know how the clusters have changed over the last quarter, the last year, the last decade, and so on. For this purpose, the user needs to input a few parameters to the algorithm:

• The two clock times [math]t_1[/math] and [math]t_2[/math] over which the clusters need to be compared. It is assumed that [math]t_2 > t_1[/math]. In many practical scenarios, [math]t_2[/math] is the current clock time.
• The time horizon [math]h[/math] over which the clusters are computed. This means that the clusters created by the data arriving between [math](t_2-h, t_2)[/math] are compared to those created by the data arriving between [math](t_1-h, t_1)[/math].

Another important issue is that of deciding how to present the changes in the clusters to a user, so as to make the results appealing from an intuitive point of view. We present the changes occurring in the clusters in terms of the following broad objectives:

• Are there new clusters in the data at time [math]t_2[/math] which were not present at time [math]t_1[/math]?
• Have some of the original clusters been lost because of changes in the behavior of the stream?
• Have some of the original clusters at time [math]t_1[/math] shifted in position and nature because of changes in the data?

We note that the micro-cluster maintenance algorithm maintains the idlists which are useful for tracking cluster information. The first step is to compute [math]\mathcal{N}(t_1, h)[/math] and [math]\mathcal{N}(t_2, h)[/math] as discussed in the previous section. Therefore, we divide the micro-clusters in [math]\mathcal{N}(t_1, h) \cup \mathcal{N}(t_2, h)[/math] into three categories:

• Micro-clusters in [math]\mathcal{N}(t_2, h)[/math] for which none of the ids on the corresponding idlist are present in [math]\mathcal{N}(t_1, h)[/math]. These are new micro-clusters which were created at some time in the interval [math](t_1, t_2)[/math]. We will denote this set of micro-clusters by [math]\mathcal{M}^\mathit{added}(t_1, t_2)[/math].
• Micro-clusters in [math]\mathcal{N}(t_1, h)[/math] for which none of the corresponding ids are present in [math]\mathcal{N}(t_2, h)[/math]. Thus, these micro-clusters were deleted in the interval [math](t_1, t_2)[/math]. We will denote this set of micro-clusters by [math]\mathcal{M}^\mathit{deleted}(t_1, t_2)[/math].
• Micro-clusters in [math]\mathcal{N}(t_2, h)[/math] for which some or all of the ids on the corresponding idlist are present in the idlists corresponding to the micro-clusters in [math]\mathcal{N}(t_1, h)[/math]. Such micro-clusters were at least partially created before time [math]t_1[/math], but have been modified since then. We will denote this set of micro-clusters by [math]\mathcal{M}^\mathit{retained}(t_1,t_2)[/math].

The macro-cluster creation algorithm is then separately applied to each of this set of micro-clusters to create a new set of higher level clusters. The macro-clusters created from [math]\mathcal{M}^\mathit{added}(t_1, t_2)[/math] and [math]\mathcal{M}^\mathit{deleted}(t_1, t_2)[/math] have clear significance in terms of clusters added to or removed from the data stream. The micro-clusters in [math]\mathcal{M}^\mathit{retained}(t_1, t_2)[/math] correspond to those portions of the stream which have not changed very significantly in this period. When a very large fraction of the data belongs to [math]\mathcal{M}^\mathit{retained}(t_1, t_2)[/math], this is a sign that the stream is quite stable over that time period.

意訳 †

2つの時刻 [math]t_1[/math] と [math]t_2[/math] ([math]t_2 > t_1[/math]) について、それぞれの時刻におけるクラスターをマイクロ・クラスターとする。

クラスター進化分析は、次の3つのタイプの変化を発見する。

1. [math]t_1[/math] から [math]t_2[/math] にかけて出現した新しいマイクロ・クラスターの集合 [math]\mathcal{M}^\mathit{added}(t_1, t_2)[/math]
2. [math]t_1[/math] には存在していたが [math]t_2[/math] には存在しないマイクロ・クラスターの集合 [math]\mathcal{M}^\mathit{deleted}(t_1, t_2)[/math]
3. [math]t_1[/math] から [math]t_2[/math] にかけて変化したマイクロ・クラスターの集合 [math]\mathcal{M}^\mathit{retained}(t_1, t_2)[/math]

Zubaroğlu (2021) による概念ドリフトの説明 †

データ・ストリーム・クラスタリングに関するサーベイ論文の中で、クラスター構造の変化が概念ドリフトによって生じるとし、概念ドリフトについて説明している。

原文 †

Concept drift is the unforeseen change in statistical properties of data stream instances over time. There are four types of concept drift: sudden, gradual, incremental and recurring (Ramirez-Gallego et al. 2017).

• Sudden concept drift: Between two consecutive instances, the change occurs at once, and after this time only instances of the new class are received. An instance that has properties of the previous class never arrives again.
• Gradual concept drift: The number of instances belonging to the previous class decreases gradually while the number of instances belonging to the new class increases over time. During a gradual concept drift, instances of both previous and new classes are visible.
• Incremental concept drift: Data instances belonging to the previous class evolves to a new class step by step. After the concept drift is completed, the previous class disappears. The instances that arrive during the concept drift are of transitional forms and they do not have to belong to either of the classes.
• Recurring concept drift: The data instances change between two or more statistical characteristics several times. Neither of the classes disappears permanently but both of them arrive in turns.

意訳 †

概念ドリフト (concept drift) は時間によってデータ・ストリームの統計的性質が変化することを表す。 概念ドリフトには次の4つのタイプがある (Ramirez 2017)。

• 突然の概念ドリフト：以前のクラスに属する事例が全く出現しなくなり、新しいクラスに属する事例だけが出現するようになる。
• 緩やかな概念ドリフト：以前のクラスに属する事例が徐々に少なくなり、新しいクラスに属する事例が徐々に増える。
• 段階的概念ドリフト：以前のクラスに属する事例が段階的に新しいクラスに属する。概念ドリフトが完了すると、以前のクラスは消えて失くなる。
• 再発性概念ドリフト：2つ以上のクラスの事例が交代で出現する。

Atif (2023) によるクラスター変化検出の分類 †

原文 †

Change detection refers to identifying variations in an object’s state by examining it at different time points. In the context of this article, change detection is the technique of recognizing differences in the cluster solutions generated from a stream at discrete time points. This research paper presents a comprehensive review of the applications and models for monitoring and tracking the changes in clustering solutions.

1. Evolutionary Clustering: Generate a sequence of clustering solutions and trace changes. Optimize two competing criteria for obtaining solutions.
   • Evolutionary clustering algorithm (Chakrabarti 2006)
   • Preserving cluster quality and preserving cluster membership (Chi 2007)
   • Multimode networks (Tang 2008)
   • Evolutionary DBSCAN (Zhang 2013)
   • Adaptive evolutionary (Xu 2013)
   • Relational DBSCAN (Banerjee 2018)
2. Self-Organizing Maps: Changes in clustering solutions are detected using self-organizing maps.
   • FOCUS (Genti 1999)
   • Comparing SOMs (Denny 2005)
   • ReDSOM (Denny 2008)
3. Heuristic Algorithms: Cluster the temporal data at discrete points in time. The windowing approach is adopted for discretizing the data stream.
   • MONIC (Spiliopoulou 2006)
   • MClusT (Oliveira 2010)
   • MEC (Oliveira 2012)
4. Online Algorithms for Evolving Data Streams: Cluster the data in real time using a density-based clustering algorithm. Changes are monitored online.
   • CluStrem (Aggarwal 2003)
   • DenStream (Cao 2006)
   • CEDAS (Hyde 2017)
   • ASCS (Fahy 2019)
   • MDSC (Fahy 2022)
   • MVSVDD (Huang 2020)

意訳 †

クラスター変化検出は、あるデータ・ストリーム対して異なる時間に行われたクラスタリングの結果の違いを認識する。 クラスターの変化を観察し、追跡する方法は次の4つに分類できる。

1. 進化的クラスタリング (Evolutionary Clustering)：クラスタリング結果の系列を生成し、その変化を追跡する手法。
2. 自己組織化マップ (Self-Organizing Maps)：自己組織化マップ (SOM) を用いてクラスターの変化を抽出する手法。
3. ヒューリスティック・アルゴリズム (Heuristic Algorithms)：時刻ごとにクラスタリングを行う手法。データ・ストリームを離散化するためにウィンドウが使われる。
4. 進化するデータ・ストリームのためのオンライン・アルゴリズム (Online Algorithms for Evolving Data Streams)：密度ベースのクラスタリング・アルゴリズムを用いてリアルタイムにデータをクラスタリングする。クラスター変化をオンラインでモニタリングする。

クラスター変化検出に関する論文 †

• Atif M, Shafiq M, Farooq M, et al. (2023). Monitoring changes in clustering solutions: A review of models and applications. Journal of Probability and Statistics 2023:7493623. doi: 10.1155/2023/7493623
  • クラスター変化検出についてのサーベイ論文
• Zubaroğlu　A and Atalay V (2021). Data stream clustering: A review. Artificial Intelligence Review 54:1201–1236. doi: 10.1007/s10462-020-09874-x
  • データ・ストリーム・クラスタリングについてのサーベイ論文

• CluStream
  • Aggarwal CC, Philip SY, Han J, and Wang J (2003). A framework for clustering evolving data streams. VLDB 2003:81–92. doi: 10.1016/B978-012722442-8/50016-1 (PDF)
  • クラスター進化分析 (Analysis of Evolving Clusters)　について説明
• DenStream
  • Cao F, Estert M, Qian W, and Zhou A (2006). Density-based clustering over an evolving data stream with noise. 2006 SIAM International Conference on Data Mining:328–339. doi: 10.1137/1.97816119727(PDF)
• DynStream
  • Kim IS, Liao S, and Imai K (2020). Measuring trade profile with granular product-level data. American Journal of Political Science 64(1):102–117. doi: 10.1111/ajps.12473
  • 2国間の貿易データに対してクラスタリングを行い、時間によるクラスターの変化を分析
• MONIC
  • Spiliopoulou M, Ntoutsi E, Theodoridis Y, and Schult R (2013). MONIC and followups on modeling and monitoring cluster transitions. ECML PKDD 2013:622–526. doi: 10.1007/978-3-642-40994-3_41
  • Spiliopoulou M, Ntoutsi E, Theodoridis Y, and Schult R (2006). MONIC: Modeling and monitoring cluster transitions. KDD 2006:706–711. doi: 10.1145/1150402.1150491

• 小西 智貴 (2022). 複数の時系列データに対する動的クラスタリング. 中央大学大学院研究年報 理工学研究科編 52.
  • クラスタ構造が時間によって変化するデータに対するディリクレ過程混合モデルによるクラスタリングについて説明している。 動的クラスタリングと書かれているが、Gruenheld (2014) や Gu (2022) による動的クラスタリングの定義とは異なり、クラスター変化検出に近い？