TDSM 10.1

From The Data Science Design Manual Wikia
Revision as of 06:03, 27 November 2017 by Mohadeseh (talk | contribs) (Created page with " To prove that Euclidean distance is in fact a metric, we should prove these facts: <math> 1.\hspace{0.2cm}d(x,y) \geq 0 </math> <math> 2.\hspace{0.2cm}d(x,y) =0\hspace{0.2c...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

To prove that Euclidean distance is in fact a metric, we should prove these facts:

1.d(x,y)0

2.d(x,y)=0 if and only if x=y

3.d(x,y)=d(y,x) for all x,y

4.d(x,y)d(x,z)+d(z,y) for all x,y,z

The Euclidean metric is defined as:

d(x,y)=Di=1|xiyi|2


1. It is clear that d(x,y)0

2. d(x,x)=Di=1|xixi|2=0 and if d(x,x)=0 then sum of some nonnegative terms is 0, so all of them should be zero then for all i,xi=yi then x=y

3. d(x,y)=Di=1|xiyi|2=Di=1|yixi|2=d(y,x)

4. To prove this fact, we first prove Cauchy-Schwartz and then using this theorem we can prove this fact.

Cauchy-Schwartz theorem: if x=(x1,,xD) and y=(y1,,yD) then: |Di=1xiyi|(Di=1x2i)1/2(Di=1y2i)1/2

Proof: Since |Di=1xiyi|Di=1|xi||yi| it is sufficient to prove the inequality for xi,yi0. Furthermore, the inequality is obvious if either x=0 or y=0 so we assume at least one xi and one yi is nonzero.

For every α,βR we have:

0Di=1(αxiβyi)2

Expanding the square on the right-hand side and rearranging the terms, we get that:

2αβDi=1xiyiα2Di=1x2i+β2Di=1y2i

we choose:

α=(Di=1y2i)1/2 , β=(Di=1x2i)1/2

Then division of the resulting inequality by 2αβ proves the theorem.

we know that xy=x1y1++xDyD and |x|=xx and d(x,y)=|xy|

by using Cauchy-Schwartz we have:

(x+y)2=(x+y)(x+y)=|x2|+2(xy)+|y2||x2|+2|xy|+|y2||x2|+2|x||y|+|y2|=(|x|+|y|)2

which results in:

x+y|x|+|y|

now consider 3 points:

d(x,y)=|xy|=|xz+zy||xz|+|zy|=d(x,z)+d(z,y)