Data smoothing is a classical statistics technique that removes noise from a dataset so that overall patterns and trends are visible. There are many algorithms for smoothing. I put together a demo of data smoothing using the Nadaraya-Watson (NW) kernel smoothing technique, with the C# language.
The output of the demo program is:
Begin Nadaraya-Watson kernel smoothing demo Loading simple XXy data Done First three data X: 0.1000 0.1000 0.2000 0.2000 0.3000 0.3000 First three data y: 0.0998 0.3987 0.0955 Creating NW kernel smoother with RBF sigma = 0.1600 Done Computing smoothed y values Done X y smooth y ------------------------------------- 0.10 0.10 0.0998 0.2069 0.20 0.20 0.3987 0.2303 0.30 0.30 0.0955 0.2474 0.50 0.50 0.5794 0.5599 0.60 0.60 0.5646 0.6681 0.70 0.70 0.9442 0.7357 0.90 0.90 0.4833 0.5556 1.00 1.00 0.5415 0.5255 End NW kernel smoothing demo
The source data is:
0.1000, 0.1000, 0.0998 0.2000, 0.2000, 0.3987 0.3000, 0.3000, 0.0955 0.5000, 0.5000, 0.5794 0.6000, 0.6000, 0.5646 0.7000, 0.7000, 0.9442 0.9000, 0.9000, 0.4833 1.0000, 1.0000, 0.5415
There are eight data items. The first two values on each line are the elements of a two-dimensional X vector, such as (0.10, 0.10). The third value is a dependent y value. The data is artificial but you can imagine the X values are inputs to some system and the y values are outputs.
Data smoothing is most often used with small datasets that have a single x value and a single y value. This allows the source data and the smoothed data to be visualized using a graph. However, I used data with two x values, such as (0.10, 0.10), where both values are artificially the same, to demonstrate that NW kernel smoothing can use multidimensional X data with several values.
Understanding the Radial Basis Function
In order to understand NW kernel smoothing, you must understand the radial basis function (RBF) function. The RBF function computes a measure of similarity between two vectors. There are several RBF versions. The version used by the demo is often called the sigma (bandwidth) version:
rbf(v1, v2) = exp(-1 * ||v1 - v2||^2 / (2 * sigma^2))
The v1 and v2 are vectors. The exp() function is Euler’s constant (approximately 2.71828) raised to a power. The ||v1 – v2||^2 is the squared Euclidean distance between vectors v1 and v2. The sigma, also called the bandwidth, is an arbitrary constant.
If the two vectors passed to RBF are the same, then rbf(v1, v2) = 1.0 (maximum similarity). As the two vectors get more and more different, the value of rbf(v1, v2) gets closer and closer to 0. RBF is symmetric so rbf(v1, v2) = rbf(v2, v1).
Suppose v1 = (2.50, -3.25, 1.00) and v2 = (2.0, -3.0, 1.0) and sigma = 1.5, then the squared distance term is:
||v1 - v2||^2 = (2.50 - 2)^2 + (-3.25 - (-3))^2 + (1.00 - 1)^2
= (0.50)^2 + (-0.25)^2 + (0.00)^2
= 0.2500 + 0.0625 + 0.0000
= 0.3125
and the RBF value is:
rbf(v1, v2) = exp( -1 * ||v1 - v2||^2 / (2 * sigma^2) )
= exp( -0.3125 / (2 * 1.5^2) )
= exp( -0.3125 / 4.50 )
= exp(-0.0694)
Computing a NW Kernel Smoothed y Value
Computing a NW smoothed data point is best explained using a concrete example. Suppose you want to compute the smoothed y’ value for x = (0.70, 0.70) in the demo data. The actual y value is 0.9442. The smoothed y’ value is 0.7357. It is computed as follows:
x = (0.70, 0.70)
x0 = (0.10, 0.10) w0 = rbf(x, x0) = 0.0000 y0 = 0.0998 w0 * y0 = 0.0000
x1 = (0.20, 0.20) w1 = rbf(x, x1) = 0.0001 y1 = 0.3987 w1 * y1 = 0.0000
x2 = (0.30, 0.30) w2 = rbf(x, x2) = 0.0019 y2 = 0.0955 w2 * y2 = 0.0001
x3 = (0.50, 0.50) w3 = rbf(x, x3) = 0.2096 y3 = 0.5794 w3 * y3 = 0.1214
x4 = (0.60, 0.60) w4 = rbf(x, x4) = 0.6766 y4 = 0.5646 w4 * y4 = 0.3820
x5 = (0.70, 0.70) w5 = rbf(x, x5) = 1.0000 y5 = 0.9442 w5 * y5 = 0.9442
x6 = (0.90, 0.90) w6 = rbf(x, x6) = 0.2096 y6 = 0.4833 w6 * y6 = 0.1013
x7 = (1.00, 1.00) w7 = rbf(x, x7) = 0.0297 y7 = 0.5415 w7 * y7 = 0.0161
------- -------
sum weights = 2.1276 sum weighted y = 1.5653
smooth y' = sum weighted y / sum weights
= 1.5653 / 2.1276
= 0.7357
There are eight data points. A weight, wi, is computed for each data point, where the weights are the RBF values between the x value and each data points. Each weight is multiplied by associated actual y value, and those products are summed to give the numerator term of the smoothed value. The denominator is the sum of the weight values.
I miss the days when I used to read a daily newspaper to get all my news and information. Here is some old health advice.
Demo program. Replace “lt” (less than), “gt”, “lte”, “gte” with Boolean operator symbols (my blog editor chokes on symbols).
using System;
using System.IO;
using System.Collections.Generic;
namespace KernelNWSmoothing
{
internal class KernelNWSmoothingProgram
{
static void Main(string[] args)
{
Console.WriteLine("\nBegin Nadaraya-Watson" +
" kernel smoothing demo ");
Console.WriteLine("\nLoading simple XXy data ");
string dataFile = "..\\..\\..\\Data\\simple_xxy_8.txt";
double[][] X = MatLoad(dataFile,
new int[] { 0, 1 }, ',', "#");
double[] y = MatToVec(MatLoad(dataFile,
new int[] { 2 }, ',', "#"));
Console.WriteLine("Done ");
Console.WriteLine("\nFirst three data X: ");
for (int i = 0; i "lt" 3; ++i)
VecShow(X[i], 4, 8, true);
Console.WriteLine("\nFirst three data y: ");
for (int i = 0; i "lt" 3; ++i)
Console.WriteLine(y[i].ToString("F4").PadLeft(8));
double sigma = 0.16; // larger sigma = smoother
Console.WriteLine("\nCreating NW kernel smoother" +
" with RBF sigma = " + sigma.ToString("F4"));
KernelSmoother ks = new KernelSmoother("rbf", sigma);
Console.WriteLine("Done ");
Console.WriteLine("\nComputing smoothed y values ");
ks.Fit(X, y); // copy dataX and dataY
Console.WriteLine("Done ");
Console.WriteLine("\n X y smooth y");
Console.WriteLine("--------------------------------");
for (int i = 0; i "lt" X.Length; ++i)
{
double[] x = X[i];
double actY = y[i];
double smoothY = ks.SmoothedY(x);
VecShow(x, 2, 6, false);
Console.Write(" " + actY.ToString("F4"));
Console.WriteLine(" " + smoothY.ToString("F4"));
}
Console.WriteLine("\nEnd NW kernel smoothing demo ");
Console.ReadLine();
} // Main
// ------------------------------------------------------
// helpers for Main(): MatLoad(), MatToVec(), VecShow()
// ------------------------------------------------------
static double[][] MatLoad(string fn, int[] usecols,
char sep, string comment)
{
List"lt"double[]"gt" result =
new List"lt"double[]"gt"();
string line = "";
FileStream ifs = new FileStream(fn, FileMode.Open);
StreamReader sr = new StreamReader(ifs);
while ((line = sr.ReadLine()) != null)
{
if (line.StartsWith(comment) == true)
continue;
string[] tokens = line.Split(sep);
List"lt"double"gt" lst = new List"lt"double"gt"();
for (int j = 0; j "lt" usecols.Length; ++j)
lst.Add(double.Parse(tokens[usecols[j]]));
double[] row = lst.ToArray();
result.Add(row);
}
sr.Close(); ifs.Close();
return result.ToArray();
}
static double[] MatToVec(double[][] M)
{
int nRows = M.Length;
int nCols = M[0].Length;
double[] result = new double[nRows * nCols];
int k = 0;
for (int i = 0; i "lt" nRows; ++i)
for (int j = 0; j "lt" nCols; ++j)
result[k++] = M[i][j];
return result;
}
static void VecShow(double[] vec, int dec, int wid,
bool newLine)
{
for (int i = 0; i "lt" vec.Length; ++i)
Console.Write(vec[i].ToString("F" + dec).
PadLeft(wid));
if (newLine == true)
Console.WriteLine("");
}
} // class Program
// ========================================================
public class KernelSmoother
{
public string kernel; //
public double sigma; // RBF sigma, aka bandwidth
public double[][] dataX;
public double[] dataY;
public KernelSmoother(string kernel, double sigma)
{
if (kernel != "rbf")
Console.WriteLine("Only rbf kernel supported ");
this.kernel = kernel; // dummy not used this version
this.sigma = sigma;
}
public void Fit(double[][] dataX, double[] dataY)
{
this.dataX = dataX; // copy by reference
this.dataY = dataY;
}
public double SmoothedY(double[] x)
{
int n = this.dataX.Length;
double numer = 0.0; // sum of weighted y values
double denom = 0.0; // sum of weights (RBF values)
for (int i = 0; i "lt" n; ++i)
{
double currRbf = RbfSigma(x, this.dataX[i],
this.sigma);
numer += currRbf * this.dataY[i];
denom += currRbf;
}
return numer / denom; // assume no div by 0
}
private static double RbfSigma(double[] x1, double[] x2,
double sigma)
{
// rbf(x1,x2) = exp(-1 * ||x1-x2||^2 / (2 * sigma^2))
int dim = x1.Length;
double sum = 0.0;
for (int i = 0; i "lt" dim; ++i)
sum += (x1[i] - x2[i]) * (x1[i] - x2[i]);
return Math.Exp(-1 * sum / (2 * sigma * sigma));
}
private static double RbfGamma(double[] x1, double[] x2,
double gamma)
{
// rbf(x1,x2) = exp(-1 * gamma * ||x1-x2||^2
int dim = x1.Length;
double sum = 0.0;
for (int i = 0; i "lt" dim; ++i)
sum += (x1[i] - x2[i]) * (x1[i] - x2[i]);
return Math.Exp(-1 * gamma * sum);
}
} // class KernelSmoother
} // ns
Demo data:
# simple_xxy_8.txt # 0.1000, 0.1000, 0.0998 0.2000, 0.2000, 0.3987 0.3000, 0.3000, 0.0955 0.5000, 0.5000, 0.5794 0.6000, 0.6000, 0.5646 0.7000, 0.7000, 0.9442 0.9000, 0.9000, 0.4833 1.0000, 1.0000, 0.5415
.NET Test Automation Recipes
Software Testing
SciPy Programming Succinctly
Keras Succinctly
R Programming
Visual Studio Live
Microsoft MLADS Conference
DevIntersection Conference
Machine Learning Week
Ai4 Conference
G2E Conference
iSC West Conference
You must be logged in to post a comment.