Bir kerede bellekteki tüm değerleri saklamak gerektirmeyen bir değerler kümesi, ama medyan, mod, çarpıklık, ve/veya olasılık tahmini için bir algoritma var mı?

Temel istatistik hesaplamak istiyorum:

• ortalama: aritmetik ortalama
• sapma: ortalama sapmaların ortalama
• standart sapma: varyans karesel
• medyan: küçük yarısından itibaren sayıları daha yarım ayıran değer
• mod: en sık değer kümesi bulundu
• çarpıklık: tl; dr
• kurtosis: tl; dr

Bunlar, herhangi bir hesaplama için temel formüller-okul sınıf aritmetik ve onları tanıyorum. Birçok istatistikte onları uygulayan kütüphaneler de vardır.

Sorunumu hallediyorum setleri çok sayıda (milyarlarca) değerler: Python Çalışma, sadece bir liste yapmak veya elementler milyarlarca karma edemem. Eğer C, milyar-element bunu yazsam bile diziler çok pratik değil.

Veriler sıralanır. Rastgele-the-fly, diğer işlemler tarafından üretilir. Her set boyutu oldukça değişkendir ve boyutları önceden bilinemez.

Zaten ortalama ve varyansı nasıl ele oldukça iyi, herhangi bir sırada kümesindeki her değer yineleme düşündüm. (Aslında, benim durumumda, oluşturulan sırada onları alıyorum.) İşte kullandığım algoritma, http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#On-line_algorithm nezaket:

• Başlatma üç değişken: sayı, toplam sum_of_squares
• Her biri için değeri:
  • Artış sayısı.
  • Değeri toplamına ekleyin.
  • Sum_of_squares için değeri Kare ekleyin.
• Kont böl, topla, değişken olarak saklamak.
• Bölme sayısı, değişken mean_of_squares olarak saklamak sum_of_squares.
• Kare, square_of_mean olarak saklamak.
• Mean_of_squares, sapma olarak saklama square_of_mean çıkarın.
• Çıkış ortalama ve varyans.

Bu "on-line" algoritması vardır zayıf yönlerini (örneğin, doğruluk sorunu olarak sum_of_squares hızlı büyür, daha büyük bir tamsayı veya kayan noktalı hassasiyet aralığı), ama temelde verir bana ne gerek kalmadan her değer, her set.

Ama benzer teknikler ek istatistikler () medyan, mod, çarpıklık, sivrilik tahmin etmek için var olup olmadığını bilmiyorum. Önyargılı bir tahmincisi ile, ya da belli bir dereceye kadar doğruluk tehlikeye atan bir yöntem bile, bellek N değerleri işlemek için gerekli O daha önemli ölçüde daha az olduğu sürece(N) yaşayabilirim.

Eğer kütüphane bu işlemler, bir veya daha fazla hesaplamak için işlevleri varsa kütüphane yardımcı olacak varolan bir durum beni de işaret ederek, "on-line".

Çarpıklık ve Sivrilik

-Hat üzerindeki Çarpıklık ve Kurtosis için algoritmalar (varyans çizgisinde) için, aynı wiki sayfasında görmek here paralel yüksek-moment istatistikleri için algoritmalar.

Medyan

Medyan sıralanmış veri olmadan zor. Eğer biliyorsanız, teoride yalnızca kısmen, örneğin selection algorithm kullanarak sıralamak için. Ancak, bu değerleri milyarlarca çok fazla yardımcı olmuyor. Kullanma sıklığı sayar öneririm, bir sonraki bölümü görmek istiyorum.

Frekans Sayıları ile medyan ve Mod

Eğer tamsayı ise, görüyorum frequencies, muhtemelen en yüksek ve en düşük keserek o artık geçerli değildir eminim bazı değer ötesinde değerler. Yüzer (ya da çok fazla tamsayı) için, muhtemelen kova / aralıkları oluşturmak, ve aynı yöntemi kullanın tamsayılar için. (Yaklaşık) mod ve medyan Hesaplaması daha kolay frekans tablosunu temel alır.

Normal Dağılımlı Rasgele Değişkenler

Eğer normal dağılım ise, nüfusun küçük bir alt kümesi için en çok olabilirlik tahmin edicileri olarakmean, variance, skewness, ve kurtosis örnek kullanırdım. (On-line) bu hesaplamak için algoritmalar, zaten artık. E. g. yüz bin veya birkaç milyon okuma tahmini hata yeterince küçük oluncaya kadar veri noktalarını,. Sadece sen (ilk 100 alarak bir önyargı olmadığını'000 değerler) örneğin. senin kümesinden rastgele seçmek emin olun Aynı yaklaşım, normal durumda mod ve medyan de örnek bir tahmincisi () tahmin etmek için kullanılabilir.

Daha fazla yorum

Tüm algoritmalar yukarıda eğer bu yardımcı olur paralel (birçok sıralama ve seçim algoritması, örneğin QuickSort ve QuickSelect dahil) çalıştırın.

Bilinen bir dağıtım verilen teorik anlar için örnek anlar, medyan ve mod, tahminci değil konuşuyoruz hep varsaydım (normal dağılım ile ilgili bölümü hariç).

Genel olarak, örnekleme verileri (yani sadece bakıyor bir alt kümesi olmalıdır, aksi halde çok başarılı verilen veri miktarını sürece tüm gözlemler gerçekleşmeleri aynı rasgele değişken (aynı dağılımları) ve momentler, mod ve medyan gerçekten var bu dağıtım. Son uyarı değil zararsız. Örneğin, Cauchy Distribution ortalama (ve daha yüksek anlar) yok. Bu durumda, örnek bir ortalama "küçük" alt kümesi, tam örnek örnek anlamına gelen ağır gelmiş olabilir.