पूर्ण विचलन

Question

की गणना के लिए ऑनलाइन एल्गोरिदम मैं एक वेक्टर online के पूर्ण विचलन की गणना करने की कोशिश कर रहा हूं, जैसा कि पूरे वेक्टर का उपयोग किए बिना वेक्टर में प्रत्येक आइटम प्राप्त होता है।

मुझे पता है कि एक वेक्टर के विचरण को इस तरीके से गणना की जा सकती: निरपेक्ष विचलन एक वेक्टर में प्रत्येक आइटम के बीच पूर्ण अंतर और मतलब का योग है। विचरण निरपेक्ष विचलन के समान है, लेकिन प्रत्येक अंतर चुकता है:

इस प्रकार

विचरण के लिए ऑनलाइन एल्गोरिथ्म है:

n = 0 
mean = 0 
M2 = 0 

def calculate_online_variance(x): 
    n = n + 1 
    delta = x - mean 
    mean = mean + delta/n 
    M2 = M2 + delta*(x - mean) # This expression uses the new value of mean 
    variance_n = M2/n 
    return variance_n 

वहाँ पूर्ण की गणना के लिए इस तरह के एक एल्गोरिथ्म है विचलन? मैं खुद को एक पुनरावर्ती परिभाषा तैयार नहीं कर सकता, लेकिन बुद्धिमान सिर प्रबल हो सकते हैं!

Answer 1

मुझे नहीं लगता कि यह संभव है।

भिन्नता के सूत्र में x और x शर्तों को अलग करना संभव है, ताकि यह उन रकम (और n) का ट्रैक रखने के लिए पर्याप्त हो। पूर्ण विचलन के लिए सूत्र में यह संभव नहीं है।

मुझे लगता है कि सबसे अच्छा कोई भी कर सकता है (पूरे वेक्टर को रखने और मांग पर पूर्ण विचलन की गणना के अलावा) तत्वों की एक क्रमबद्ध सूची रखता है। यह प्रत्येक नए तत्व के लिए ओ (लॉग (एन)) है, लेकिन जब आप तत्व जोड़ते हैं तो पूर्ण विचलन को पुन: गणना करने की लागत ओ (लॉग (एन)) है। यह आपके आवेदन के आधार पर सार्थक हो सकता है या नहीं भी हो सकता है।

Answer 2

आपके द्वारा दिए गए भिन्नता के लिए सूत्र संभव है जो कई संभव है (मैं गणना करने के तीन अलग-अलग तरीकों के बारे में सोच सकता हूं) हालांकि मैंने सत्यापित नहीं किया है कि आपका सही है। यह मुझे याद करने के लिए उचित रूप से करीब दिखता है।

समस्या यह है कि विचलन के वर्गों की तुलना में पूर्ण मूल्य वास्तव में अधिक "nonlinear" है। यह आपको लूप में एक पुनरावर्ती रूप में उस गणना को करने में सक्षम होने से रोकता है, कम से कम x के पिछले सभी मानों को बनाए रखने के बिना नहीं। आपको उस योग के लिए अग्रिम रूप से समग्र माध्य की गणना करनी होगी।

संपादित करें: मुझे लगता है कि बीटा मेरे साथ सहमत है। यदि आपने पिछले सभी बिंदुओं को एक क्रमबद्ध सूची में सहेजा है, तो आप अद्यतन वांछित विचलन को कुशलतापूर्वक गणना कर सकते हैं। लेकिन यह आपके अनुरोध की भावना का मुकाबला है।

Answer 3

चूंकि एक्स और माध्य के बीच पूर्ण विचलन को वर्ग अंतर के वर्ग रूट के रूप में परिभाषित किया जा सकता है, तो अनुकूलन एक छोटा लेकिन पक्षपातपूर्ण अनुमान से खुश है (अर्थात् अनंतता की सीमा अपेक्षित मान है) :

n = 0 
mean = 0 
M2 = 0 

def calculate_online_avg_abs_dev(x): 
    n = n + 1 
    delta = x - mean 
    mean = mean + delta/n 
    M2 = M2 + sqrt(delta*(x - mean)) 
    avg_abs_dev_n = M2/n 

यह औसत पूर्ण विचलन के मामले में है। आम तौर पर पागल का उपयोग किया जाता है (औसत पूर्ण विचलन), जो पुनरावर्ती कार्यक्रम के लिए असंभव है। लेकिन औसत मामलों में औसत पूर्ण विचलन उपयोगी है। जब हम निकट-से-सामान्य वितरण से सैकड़ों मूल्यों के बारे में बात कर रहे हैं, तो दोनों मूल्य बहुत करीब हैं।

यदि आप केवल पूर्ण समर्पण की राशि चाहते हैं, तो जीवन भी आसान है: बस एम 2 लौटाएं।

इस तथ्य से अवगत रहें कि आपके द्वारा दिए गए एल्गोरिदम और पूर्ण विचलन के लिए मामूली अनुकूलन थोड़ा पक्षपातपूर्ण है।

एल्गोरिथ्म साबित करने के लिए आर में एक सिमुलेशन इस तरह से काम करता है:

लाल रेखा सही मूल्य है, काली रेखा एल्गोरिथ्म ऊपर बताई गई प्रगतिशील मूल्य है।

कोड:

calculate_online_abs_dev <- function(x,n){ 
    M2=0 
    mean=0 
    out <- numeric(n) 
    for(i in 1:n) { 
     delta <- x[i] - mean 
     mean <- mean + delta/i 
     M2 = M2 + sqrt(delta*(x[i] - mean)) 
     out[i] <- M2/i 

    } 
    return(out) 
} 

set.seed(2010) 
x <- rnorm(100) 

Abs_Dev <- calculate_online_abs_dev(x,length(x)) 
True_Val <- sapply(1:length(x),function(i)sum(abs(x[1:i]-mean(x[1:i])))/i) 

plot(1:length(x),Abs_Dev,type="l",xlab="number of values",lwd=2) 
lines(1:length(x),True_Val,col="red",lty=2,lwd=2) 
legend("bottomright",lty=c(1,2),col=c("black","red"), 
    legend=c("Online Calc","True Value"))