金融データ・マイニング/動的クラスタリングとクラスター変化検出 のバックアップ(No.5)

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• 金融データ・マイニング/動的クラスタリングとクラスター変化検出 へ行く。
  • 1 (2023-12-22 (金) 15:31:51)
  • 2 (2023-12-22 (金) 16:28:42)
  • 3 (2023-12-22 (金) 20:41:58)
  • 4 (2023-12-23 (土) 15:52:11)
  • 5 (2023-12-23 (土) 19:53:43)
  • 6 (2023-12-25 (月) 11:56:35)
  • 7 (2023-12-26 (火) 11:03:47)

---

動的クラスタリングについてのメモ

種別 †

• 動的クラスタリング (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) による動的クラスタリングの定義 †

原文 †

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)
  • 動的クラスタリングの定義

クラスター変化検出 (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
2. Self-Organizing Maps
3. Heuristic Algorithms
4. Online Algorithms for Evolving Data Streams

意訳 †

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

1. 進化的クラスタリング (Evolutionary Clustering)
2. 自己組織化マップ (Self-Organizing Maps)
3. ヒューリスティック・アルゴリズム (Heuristic Algorithms)
4. 進化するデータ・ストリームのためのオンライン・アルゴリズム (Online Algorithms for Evolving Data Streams)

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

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