不共享數據的快速/簡單數組比較算法

Question

我有兩個彼此獨立的不同系統生成的兩個數組。我想通過比較數組中生成的幾個數字來比較它們的相似性。

現在，我只比較數組的最小值，最大值和總和，但我想知道是否有更好的算法呢？任何類型的哈希算法都需要對數組之間的小浮點差異不敏感。

編輯：我想要做的是驗證兩種算法生成相同的數據，而不必直接比較數據。所以算法應該對數據的變化敏感，並且對每個元素之間的微小差異相對不敏感。

Answer 1

我不會試圖減少到一個數字;只是傳遞值的tuple，並編寫一個比較元組的close_enough函數。

例如，您可以使用(mean, stdev)作爲您的值，然後將close_enough定義爲「每個數組的平均值在其他數組均值的0.25個標準差之內」。

def mean_stdev(a): 
    return mean(a), stdev(a) 

def close_enough(mean_stdev_a, mean_stdev_b): 
    mean_a, stdev_a = mean_stdev_a 
    mean_b, stdev_b = mean_stdev_b 
    diff = abs(mean_a - mean_b) 
    return (diff < 0.25 * stdev_a and diff < 0.25 * stdev_b) 

顯然正確的值是你想調整的基礎上你的用例。也許你實際上想要基於它，例如，方差（stdev的平方），或者方差和偏斜，或者stdev和sqrt（偏斜），或者除了算術平均值之外的一些完全不同的標準化。這一切都取決於你的數字代表什麼，以及「足夠接近」的含義。

不知道任何有關您的應用領域，很難給出任何更具體的。例如，如果您正在比較音頻指紋（或DNA指紋或指紋指紋），那麼如果比較風景的JPEG壓縮圖像，則需要非常不同的東西。

---

在你的評論中，你說你想要對值的順序敏感。爲了解決這個問題，你可以生成一些關於序列「亂序」的測量。例如：

diffs = [elem[0] - elem[1] for elem in zip(seq, sorted(seq))] 

這給出了每個元素和排序位置中存在的元素之間的區別。你可以建立一個類似stdev的度量（平方值，平均值，sqrt），或者取平均絕對差值等。

或者你可以比較實際指標與「右」指數。或者，基於均值和標準差，其價值與其指數的預期值有多遠。或者......有無數的可能性。再次，這是適當的很大程度上取決於您的應用領域。

Answer 2

完全取決於你的「比較它們的相似性」的定義。

你想比較哪些功能？ 您可以識別哪些功能？是他們可識別的模式？即在該組中，存在6個關鍵點，存在2個不連續點...等等...

你已經提到了比較最小/最大/總和;手段和標準偏差也在評論中討論過。這些都是該套裝的所有功能。

最終，您應該能夠採取所有這些功能並製作n維描述符。例如[最小，最大，平均值，標準等...]

然後，您可以比較這些n維描述符來定義其中一個比另一個「更少」，「相等」還是「更多」。如果您想將其他集分類爲它們更像是「集合A」還是更像「集合B」，那麼您可以查看分類器。

參見：

Classifying High-Dimensional Patterns Using a Fuzzy Logic

Support Vector Machines