如何計算大樣本的 Rousseeuw’s and Croux' (1993) Qn 尺度估計量？

讓所以對於一個非常短的樣本，比如它可以通過找到成對差異的階靜態：

   7 6 5 3 2 1
1   6 5 4 2 1
2   5 4 3 1
3   4 3 2
5   2 1
6   1
7

h=[n/2]+1=4

k=h(h-1)/2=8

因此

顯然，對於包含 80,000 條記錄的大樣本，我們需要非常大的內存。

反正有沒有計算在一維空間而不是二維空間？

答案的鏈接ftp://ftp.win.ua.ac.be/pub/preprints/92/Timeff92.pdf 雖然我不能完全理解。

更新：問題的癥結在於，為了實現 $ O(n\log(n)) $ 時間複雜度，一個需要的順序 $ O(n) $ 貯存。

---

不， $ O(n\log(n)) $ 是時間複雜度的理論下限（見（1））選擇 $ k^{th} $ 元素之中 $ \frac{n(n-1)}{2} $ 可能的 $ |x_i - x_j|: 1 \leq i \lt j \leq n $ .

你可以得到 $ O(1) $ 空間，但只能通過天真地檢查所有組合 $ x_i-x_j $ 及時 $ O(n^2) $ .

好消息是您可以使用 $ \tau $ 規模估計器（參見 (2) 和 (3) 以了解改進版本和一些時序比較），在 包中的函數scaleTau2()中實現。單變量Rrobustbase $ \tau $ 估計器是規模的兩步（即重新加權）估計器。它具有 95% 的高斯效率、50% 的擊穿點和復雜度 $ O(n) $ 時間和 $ O(1) $ 空間（加上它可以很容易地“在線”，在重複使用中減少一半的計算成本——儘管你必須深入研究R代碼來實現這個選項，這很簡單）。

1. X + Y 中選擇和排序的複雜性以及具有排序列的矩陣 GN Frederickson 和 DB Johnson，計算機和系統科學雜誌第 24 卷，第 2 期，1982 年 4 月，第 197-208 頁。
2. Yohai, V. 和 Zamar, R. (1988)。通過最小化有效尺度的回歸的高分解點估計。美國統計協會雜誌 83 406–413。
3. Maronna, R. 和 Zamar, R. (2002)。高維數據集的位置和分散的穩健估計。技術計量學 44 307–317

編輯使用這個

1. 啟動R（它是免費的，可以從這裡下載）
2. 通過鍵入以下命令安裝包：

install.packages("robustbase")

3. 通過鍵入以下內容加載包：

library("robustbase")

4. 加載數據文件並運行函數：

mydatavector <- read.table("address to my file in text format", header=T)
scaleTau2(mydatavector)

引用自：https://stats.stackexchange.com/questions/3989