Calculate Standard deviation incrementally one batch at a time

-
In this article, I would like to display a way to calculate standard deviation in an incremental way. Unlike existing articles, that shows how to update the calculation when adding one more element. I will display a method to calculate standard deviation (std.dev) from existing batch of data and additional batch of data.

Motivation - suppose you have an ETL system that processes batches of data every day like Apache Spark and you need to display statistical data for all the data like std.dev. If you calculate it on the entire set of data the calculation will become increasingly "harder" since the data set will always grow in size and the calculation will require more and more time.

The definition of standard deviation is:

So once additional data is added the entire formula should be re-calculated. And the "hard" parts (where we do a full scan of the data) is in the average and the squared difference from the mean should be recalculated.

However, if we have the average, standard deviation and count of the additional data (denoted as b) then we can do the following for the average:

From the average definition:
 
and for the existing data and the additional batch:
[1] Average for the total data
So the total average can be calculated as the sum of products between average and number of elements divided by the total number of elements.

For the standard deviation, let us denote:
Additionally
[2] Sum of square
 

The squared difference from the mean for the total data is
 
Using [2] we can write
[3] Squared difference from the mean for the total data.

The standard deviation for the total data is:

By plugging [1] and [2] we get the bellow expression for the total std.dev expressed in terms of the existing data, denoted as a, and the additional batch, denoted as b.

 
Conclusion - This approach enables us to do statistical calculation incrementally and keep the calculation time and resources bound to the batch size and not to the total data size.

 

Comments

Post a Comment

Popular posts from this blog

5 ways to calculate max of row in Spark

-
Image
5 ways to calculate max of row in Spark/PySpark In this post I tested the performance of 5 different methods to calculate a maximal value of a single row. You might encounter this situation before: you have multiple columns with some value, integer or float for example, and you want to calculate the maximum value per row for all the data frame and append it as additional column. We will test 5 different ways to calculate maximum value: udf - user define function 'array' and 'array_max' functions 'greatest' function rdd 'map' transformation data frame groupBy and max-aggregation For each of these methods will count the time it take to read a CSV file, calculate the maximal value and add it as 'max' column. For the data, we are going to generate 10 columns of integer values over 1 million rows via Python code. The values will be in the range of 1 to 1000. import random def gen_csv (): f = open ( "../data_10x1m.csv...
Read more

Create Custom Datasource With Spark 3 - Part 1

-
Image
This article is the first of a series on how to create a custom data source that will plug in to Spark mechanism. The idea is to write something like: Dataset < Row > df = sparkSession . read () . option ( "filename" , "path-to-data-file" ) . option ( "other-options" , "some value" ) . format ( "com.roizaig.mydatasource" ) . load (); To read a file, parse it according to some custom logic and return a dataset that represents it. Why Create Custom Data Source? Spark support out of the box in Parquet , CSV , JSON and ORC  and more. In most cases these formats will be more than okay and if not, you can always read it as a text file and do some string manipulation in Spark. However, there are some cases where we would like to "teach" Spark to read our own custom format. Flexibility is a key point, with a custom datasource you can read every format y...
Read more

Spark - How to read a JSON file

-
Image
First thing to notice it the file structure. Its actually a collection of json objects *each one in a single line*. { "field_name": "value", "field_name": "value", ... } { "field_name": "value", "field_name": "value", ... } { "field_name": "value", "field_name": "value", ... } Unlike csv() method the json() method does not have inferSchema parameter. The schema is inferred from the json types. from pyspark.sql import SparkSession import pyspark.sql.types as t import pyspark.sql.functions as f spark = SparkSession . builder \ . master( 'local' ) \ . appName( 'Read JSON file' ) \ . getOrCreate() df = spark . read \ . json( 'data.json' , multiLine = True ) df . printSchema() df . show(truncate = False ) root |-- Address: string (nullable = true) |-- Age: long (nullable = true) |-- Birth Date: string (nu...
Read more