DEV Community: Raphael Gutierrez

Basics of Minkowski Distance

Raphael Gutierrez — Wed, 08 Feb 2023 04:20:40 +0000

Classification problem involving Minkowski distance at p=2 in Iris dataset

Distance metrics are used by proximity-based models to find certain paths between two points.

One of the best applications of distance metrics is in the travelling salesman problem where nearest neighbour, an approximation algorithm, is usually utilized. Aside from combinatorial optimization, distance metrics are also widely used in classification, clustering, and special relativity problems.

In this article, we will tackle one of the basic distance metrics, named after the German mathematician Hermann Minkowski—the Minkowski distance.

By definition

Minkowski distance is a distance metric, or a similarity measurement, between two points in a normed vector space. It uses a parameter $p$ which represents the order of the norm.

Let’s say we have $X_n$ and $Y_n$ denoted as:

X = (x_1,x_2,...,x_n),

Y = (y_1,y_2,...,y_n)

The distance of two points can be measured by getting the absolute value of the difference of $X_i$ and $Y_i$ ( $X_i - Y_i|$ ). Hence, to get the distances of all $X, Y$ points ( $D (X, Y)$ ), the formula will be in the form of:

\displaystyle\sum_{i=1}^n{|x_i - y_i|}^p

To satisfy the Minkowski distance, adding $1p\frac{1}{p}$ (which, again, represents the order of the norm) completes the equation:

\bigg(\displaystyle\sum_{i=1}^n {|x_i - y_i|}^p\bigg)^{\frac{1}{p}}

Minkowski distance can also be derived as:

\sqrt[p]{|x_{1}-y_{1}|^p + |x_{2}-y_{2}|^p + ... + |x_{n}-y_{n}|^p} } ,

\sqrt[p]{|x_{i1}-x_{j1}|^p + |x_{i2}-x_{j2}|^p + ... + |x_{in}-x_{jn}|^p}

Orders of the norm

Unit circles with various values of p

The order of the norm (denoted by the parameter $p$ ) varies the distance norm of the points.

The case where $p = 1$ is equivalent to the Manhattan distance—named after the rectilinear street layout of Manhattan since it measures the distance between two points in a city if we can only travel along orthogonal city blocks.

Manhattan distance can be calculated using:

\bigg(\displaystyle\sum_{i=1}^n {|x_i - y_i|}\bigg) } ,

D(i,j) = {|x_{i1}-x_{j1}| + |x_{i2}-x_{j2}| + ... + |x_{in}-x_{jn}|}

The case where $p = 2$ is equivalent to the Euclidean distance (or the Pythagorean distance, since it can be calculated from the Cartesian coordinates of the points using the Pythagorean theorem).

Euclidean distance can be calculated using:

\bigg(\displaystyle\sum_{i=1}^n {|x_i - y_i|}^2\bigg)^{\frac{1}{2}} } ,

\sqrt{|x_{i1}-x_{j1}|^2 + |x_{i2}-x_{j2}|^2 + ... + |x_{in}-x_{jn}|^2}

Therefore, Minkowski distance can also be considered as a generalization of both the Euclidean distance and the Manhattan distance.

The parameter $p$ can extend to more than the value of $2$ to $∞\infty$ that is equal to the Chebyshev distance. Having $p < 1$ violates the triangle inequality—an advanced topic that is out of the scope of this article.

Applications of Minkowski distance

Minkowski distance is widely used in machine learning (classification, clustering, and feature extraction) and special relativity (Minkowski space) problems.

One example is in Chess programming. The Minkowski distance at $p = 1$ can be used in the static evaluation of the late endgame, where for instance races of the two king to certain squares is often an issue—or in so called Mop-up evaluation, which considers the Manhattan-Distance between winning and losing king.^[1]

$p = 2$ has its best usage in calculating the length of a line segment between the two points. It is widely used in geocoding/reverse geocoding applications, such as finding the distance between the geocoded point and the true address location is computed to evaluate the positional accuracy of a geocoding procedure.^[2]

^[1] https://www.chessprogramming.org/Manhattan-Distance
^[2] https://www.sciencedirect.com/science/article/pii/B9780124095489095932

Formulas Behind Linear Regression

Raphael Gutierrez — Tue, 12 Jul 2022 16:28:00 +0000

Linear regression is an approach for predicting a quantitative response Y on the basis of a single predictor variable X (or in multiple linear regression, on the basis of multiple predictors). It's a simple yet powerful model to estimate continuous variables.

Here, I'll be discussing important formulas behind linear regression.

Linear model

Since linear regression is a linear model, it assumes that the dependence of Y on X1, X2, …, Xp is also linear. Because of that, a simple linear regression can be interpreted in the form:

Y=β0+β1X+ϵY=\beta_0+\beta_1X+\epsilon

Where:
    β0 = intercept term (expected value of Y when X=0)
    β1 = the average increase in Y associated with a one-unit increase in X
    ϵ = a catch-all for what we miss with this simple model. We assume that the error term is independent of X

Here, X is the independent variable and Y is the dependent variable (also the estimated value), but what we're most interested to look at here are the coefficients β0 (slope) and β1 (intercept).

Recall your high school geometry class where slope-intercept form was introduced. It's basically similar as to what's happening in a simple linear regression equation, where the higher the slope is, the steeper the line goes and the greater the rate of change becomes. Meanwhile, the intercept controls the location where it intersects an axis.

To build a linear model, we must find first the values of these coefficients. This is a job for the least squares approach.

Least squares and residuals

The least squares approach chooses the values of B̂0 and B̂1 (hat symbol means estimates) that minimize residuals. A residual is the difference between the i th observed response value and the i th response value that is predicted by the linear model, or in the form:

ei=yi−y^ie_i=y_i-\hat{y}_i

This is a single instance of a residual, and sometimes it comes up negative, so we usually get the sum of the squares of all residuals, hence the residual sum of squares (RSS):

RSS=e_1^2+e_2^2+...+e_n^2

RSS=∑i=1n(yi−y^i)2RSS=\textstyle\sum_{i=1}^n(y_i-\hat{y}_i)^2

Since we're all set, we can now compute for the values of B̂0 and B̂1 using the formulas:

β1^=∑i=1n(xi−xˉ)(yi−yˉ)∑i=1n(xi−xˉ)2\hat{\beta_{1}}={\textstyle\sum_{i=1}^n(x_i-\bar{x})(y_i-\bar{y}) \over \textstyle\sum_{i=1}^n(x_i-\bar{x})^2}

β0^=yˉ−β1^xˉ\hat{\beta_0}=\bar{y}-\hat{\beta_1}\bar{x}

These are derived from the formula of the regression line. Once the coefficients are calculated, we can now compute for estimates and assess the accuracy of the model.

Assessing accuracy

There are various metrics we can use to assess the accuracy of a linear model. Some of them are residual standard error (RSE), R² statistic, and mean squared error.

The residual standard error or RSE is considered a measure of the lack of fit of the model to the data. If the predictions obtained using the model are very close to the true outcome values, then RSE will be small and we can conclude that the model fits the data very well.

RSE is also an estimate of the standard deviation of ϵ. Roughly speaking, it is the average amount that the response will deviate from the true regression line.

It uses RSS to compute its value, thus having a form of:

RSE=1n−2RSSRSE=\sqrt{ {1 \over {n-2}} RSS }

The coefficient of determination or R² statistic is the percentage of variation in Y which is explained by all the X variables. In other terms, it is the square of the correlation R of the data (statistical relationship between variables).

R² has an interpretational advantage over RSE since unlike RSE, it always lies between 0 and 1.

The formula to find R² is:

R2=1−RSS∑i=1n(yi−yˉ)2R^2=1-{RSS \over {\textstyle\sum_{i=1}^n}(y_i-\bar{y})^2}

If you recall in other references, the denominator is the total sum of squares (TSS). With that, we can rewrite the formula to:

R2=1−RSSTSSR^2=1-{RSS \over TSS}

Finally, the mean squared error or MSE tells us the average squared difference between the predicted values and the actual values. The lower the MSE, the better a model fits the data.

The formula to calculate the MSE is:

MSE=1n∑i=1n(yi−y^i)2MSE={1 \over n} {\textstyle\sum_{i=1}^n}(y_i-\hat{y}_i)^2

Upon observation, we can see that the MSE can also be computed by dividing the RSS to the total number of data points n.

Reference:
James, G., Witten, D., Hastie, T., & Tibshirani, R. (2021). An Introduction to Statistical Learning with Applications in R (2nd ed.).

Considerations when performing ETL

Raphael Gutierrez — Fri, 25 Mar 2022 16:32:46 +0000

ETL Process (c) Project SPARTA

Extract-transform-load (ETL) is an essential part of Data Value Chain and has been the go-to data pipeline procedure when performing data warehousing due to its advantages such as ease in development and having a schema that matches what businesses need.

ETL basically combines data from multiple data sources into a single, consistent data storage that is loaded into a data warehouse or other target system.

To deliver business requirements accurately through a successful ETL, there are few considerations needed to keep in mind.

What-When-How

Organizations deal with huge amount of data everyday and finding out what exact data is needed is vital in performing extraction and transformation.

Which data is important and will finally end up in the data warehouse?

It's important to know what is needed and what will be needed in the future according to the business requirement. This is to save memory (by also avoiding noise data) and to improve computing performance.

Knowing also when to extract is a key factor. When performing ETL, it should not affect the production environment. Avoid extracting during peak hours as it may slow down the system in the production, affecting user experience, and worst, may cause data loss. Instead, performing batch extraction after office hours is more advisable.

Lastly, an important rule in ETL is to not tap the production database. One must create an indirect route to the source (eg. extracting from dump files created from IT batch run). Also, identifying how to extract involves consultations. This includes reviewing data governance and privacy policies of the organization.

Data Dictionary & Mapping

It is not uncommon to work with a vast number of data just to answer a single business requirement. However, problems may arise if attributes have inconsistencies and the data is not prepared well.

A data dictionary is a centralized repository of metadata and metadata is data about data, as defined by Kelly Bourne in his book "Application Administrators Handbook." It includes data elements with detailed description of its format and relationships.

Keeping a data dictionary that contains a list of fields and definitions of a schema helps not to get lost when working with potentially hundreds of fields with conflicting, ambiguous, and sometimes, analogous names. When working with relational databases with multiple related tables, mapping out and documenting the attributes helps not to get confused.

Business Rules

According to Michael Eisner in his article on ProcessMaker, business rules are directives that define activities and help provide guidelines to organizations. They bring forth efficiency, consistency, predictability, and many other benefits

Knowing business rules especially in transformation phase helps identify which is which and what to do according to the limitations set in the database, since these rules impose some form of constraint on a specific aspect of the database, such as the elements within a field specification for a particular field or the characteristics of a given relationship.

These are some of my notes in Week 1 of Project SPARTA's SP701 "SQL for Data Engineering" course.

Is it Really More Fun in the Philippines?: An EDA on the State of the Philippines in World Happiness Reports

Raphael Gutierrez — Sun, 13 Mar 2022 16:41:00 +0000

In 2016, the Department of Tourism of the Philippines unveiled its new tourism campaign dubbed "It's more fun in the Philippines" aiming to highlight Philippine culture, Filipino characters of being joyful and hospitable, cuisine and lifestyle, and the tourism industry to attract foreign visitors.

Years have passed, many events have happened, and a new administration has overtook, the department still holds the tourism campaign and this brings the question if the tagline is still true and relevant these days.

The World Happiness Report is a publication of the Sustainable Development Solutions Network that publishes annual reports of national happiness based on the ratings of each criteria. These criteria are:

the natural log GDP per capita,
social support,
healthy life expectancy at birth,
freedom to make life choices,
generosity, and
perceptions of corruption.

The main feature of the dataset is the happiness score, also referred to as Cantril life ladder, or ladder score. Respondents are asked to think of a ladder, with the best possible life for them being a 10, and the worst possible life being a 0. The report correlates the life evaluation results with other features mentioned earlier.

This analysis seeks to answer the following questions:

What is the state of the happiness score of the Philippines in the world?
What are the factors that highly affect the happiness score of the Philippines?
Does GDP per capita influence the happiness score of the Philippines? How strong is the correlation between two features?

State of the happiness score of the Philippines in the world

The line graph above shows the ladder scores (happiness index) of the Philippines from 2006 to 2021. The lowest recorded ladder score is during 2006 at 4.669946 and the highest is in 2019 at 6.267745.

Based on the analysis, the Philippines ranked 66th happiest country in the world in 2021 with 5.8802 ladder score. In historical data, the Philippines ranked 86th happiest country with ladder score of 5.256793. See “2021 Philippines vs. The World” and “Philippines Historical Data (2006-2021)” sections for more information.

In the ASEAN Region, the Philippines ranked 3rd happiest country with 5.8802 ladder score in 2021. In historical data, the Philippines ranked 5th happiest country with 5.256793 ladder score. See “Philippines vs. ASEAN Countries” section for more information.

Factors that highly affect the happiness score of the Philippines

The factors affecting the happiness score of the Philippines are determined using standard correlation coefficient or Pearson’s correlation. The correlation table is graphed in a heatmap to identify the spots where high positive and negative relationships are found.

On positive relationship, the log GDP per capita and healthy life expectancy at birth scores the highest positive correlation at 0.978401. This means that the two features move in the same positive direction. If the log GDP per capita increases, healthy life expectancy at birth also increases. The correlation between the two features is statistically significant at confidence level of 95% (α of 0.05 > p-value of 5.5539247012691395e-11).

Next is the freedom to make life choices and healthy life expectancy at 0.923263 (α of 0.05 > p-value of 3.423774679928049e-07). Lastly, the log GDP per capita and ladder score at 0.850987 (α of 0.05 > p-value of 2.922413061494319e-05). All are statistically significant.

On negative relationship, the perceptions of corruption and healthy life expectancy scores at -0.875596. This means that the two features move in the same negative direction. If the perceptions of corruption increases, healthy life expectancy at birth healthy life expectancy decreases. The correlation between the two features is statistically significant at confidence level of 95% (α of 0.05 > p-value of 8.84474766153686e-06).

Next is the perceptions of corruption and freedom to make life choices at -0.875319 (α of 0.05 > p-value of 8.9767790795422e-06), also statistically significant.

Influence of GDP per capita to the happiness score of the Philippines

The natural log GDP per capita of the Philippines influences the happiness score (ladder score) of the Philippines. The Pearson correlation of the two features is 0.850987 and is statistically significant at confidence level of 95% (α of 0.05 > p-value of 2.922413061494319e-05). This means for every increase of GDP per capita of the Philippines, the happiness score also increases. More information can be seen on “Sorting ladder score by log GDP per capita” section.

Other observations

In 2021, Finland topped the rankings as the happiest country in the world with a ladder score of 7.8421.
In analyzing historical data, Denmark led the rankings with 7.676504 mean ladder score from 2005-2021.
Luxembourg has the highest Log GDP per capita at 11.646564 and managed to be at 8th spot in the world at 7.3244 ladder score in 2021.
In both 2021 and historical data, all countries included in the top 10 highest ladder scores have Log GDP per capita ranging from 10 to 11, higher healthy life expectancy at birth ranging from 71 and above, freedom to make life choices and social support ranging from 0.90 and above.
Norway has the highest freedom to make life choices at 0.954847 score and managed to be included in top countries sorted by ladder score in historical data (ranked 4th).
In ASEAN Region, Singapore topped both 2021 and historical datasets at 6.3765 and 6.495141 ladder scores, respectively.
All ASEAN countries, except Brunei, are present in both datasets.
Note: Since DataFrame indices start at 0, all rankings from the datasets are adjusted (n+1) to fit the real-world scenario of ranking countries.

Datasets are retrieved from https://worldhappiness.report/ed/2021/.

Notebook of this data analysis can be accessed through https://github.com/ralphgutz/is-it-really-more-fun-in-the-philippines.