分割一個浮動數組相似片段（聚類）

我有浮標一個這樣的數組：分割一個浮動數組相似片段（聚類）

[1.91, 2.87, 3.61, 10.91, 11.91, 12.82, 100.73, 100.71, 101.89, 200]

現在，我想到陣列這樣劃分：

[[1.91, 2.87, 3.61] , [10.91, 11.91, 12.82] , [100.73, 100.71, 101.89] , [200]]

// [ 200]將被視爲異常值，因爲較少集羣支持

我必須爲幾個數組找到這種類型的段，我不知道分區大小應該是多少。我試圖通過使用hierarchical clustering (Agglomerative)來完成，它給我帶來滿意的結果。然而，問題是，我被建議不要使用聚類算法來處理一維問題，因爲它們沒有理論上的理由（因爲它們是用於多維數據）來做到這一點。

我花了很多時間找到解決方案。然而，建議似乎很不一樣，如：this和this VS. this和this和this。

我發現了另一個建議，而不是聚類，即natural breaks optimization。但是，這也需要像K-means（右？）那樣聲明分區號。

這很令人困惑（特別是因爲我必須在幾個陣列上執行這種分割，所以不可能知道最佳分割數）。

是否有任何方法可以找到分區（因此我們可以通過一些理論上的理由來減少分區內的方差並最大化分區之間的差異）？

任何指向文章/論文的指針（如果可用的C/C++/Java實現）和一些理論上的理由將對我非常有用。

來源

2013-07-05 alessandro

我很好奇，爲什麼羣集不適合一個維數據 - 如果你以某種方式增加維例如，添加sqrt（n）作爲維度，有點像SVM中發生的情況？ –

@ZiyaoWei，「爲什麼聚類不適合一維數據」 - 我真的不知道。我在課堂上被告知，在1-d數據中使用聚類是瘋狂的。但是，我發現沒有文章說明爲什麼我不能（或可以）。 – alessandro

@ZiyaoWei沒有理由增加尺寸似乎不是一個好的解決方案。 – alessandro

我想我會對數據進行排序（如果它尚未），然後採取相鄰的差異。將差異除以數字中較小的一個，以獲得百分比變化。設置一個閾值，當更改超過該閾值時，啓動一個新的「羣集」。

編輯：快速演示代碼在C++：

#include <iostream> 
#include <vector> 
#include <algorithm> 
#include <iterator> 
#include <numeric> 
#include <functional> 

int main() { 
    std::vector<double> data{ 
     1.91, 2.87, 3.61, 10.91, 11.91, 12.82, 100.73, 100.71, 101.89, 200 
    }; 

    // sort the input data 
    std::sort(data.begin(), data.end()); 

    // find the difference between each number and its predecessor 
    std::vector<double> diffs; 
    std::adjacent_difference(data.begin(), data.end(), std::back_inserter(diffs)); 

    // convert differences to percentage changes 
    std::transform(diffs.begin(), diffs.end(), data.begin(), diffs.begin(), 
     std::divides<double>()); 

    // print out the results 
    for (int i = 0; i < data.size(); i++) { 

     // if a difference exceeds 40%, start a new group: 
     if (diffs[i] > 0.4) 
      std::cout << "\n"; 

     // print out an item: 
     std::cout << data[i] << "\t"; 
    } 

    return 0; 
}

結果：

1.91 2.87 3.61 
10.91 11.91 12.82 
100.71 100.73 101.89 
200

來源

2013-07-05 01:57:34

你能不能詳細說明一下？我無法得到它（如果可能的話，可能是僞代碼）？ – alessandro

@alessandro：參見編輯答案。 –

聚類通常假定多維數據。

如果你有一維數據，排序它，然後用核密度估計，或者只是掃描最大的差距。

在1維中，問題變得相當容易，因爲可以對數據進行排序。如果你使用聚類算法，不幸的是而不是利用這個，所以使用1維方法！

考慮找到1維數據中最大的缺口。這是微不足道的：排序（n日誌n，但在實踐中儘可能快），然後查看兩個相鄰值以獲得最大差異。

現在嘗試定義在2個維度「最大的差距」，以及一個有效的算法來找到它......

來源

2013-07-05 07:44:13

分割一個浮動數組相似片段（聚類）

回答

相關問題