Machine Learning Series 5: distance space (1)

One 、 What is space

         Space , Is to define certain rules on a set , This rule can be generalized to every element in the set .

        such as ： So called atmospheric space , Is refers to “ Air molecules on earth , Any space that can be reached in a natural state ”. According to this definition , The space at the bottom of the well is atmospheric space , The space in basketball does not belong to the atmospheric space , Because natural forces cannot enter .

        Distance space ： Is on a set , Define the distance function between two points , This function can be regarded as a rule , For any point in the set .

Two 、 Understanding and defining distance space

2.1 Geometric understanding of the definition of distance space

        stay mathematics in , metric space （ English ：Metric space） It's a aggregate And its Measure , The Measure It's a function -- distance function . So-called “ distance function ” Refer to ： Any two members of the set （ Usually we call it “ spot ”） The concept of distance between . The form of distance may vary , But all these functions , The following characteristics must be met ：

• The distance between each point and itself is 0,
• The distance between any two points is a positive number ,
• from A To B Distance of , Equivalent to from B To A Distance of ,
• from A To B Is less than or equal to the distance from A Go first C Until then B Distance of .

For example, below ：

In collection S in , Any point , such as A spot ,A To A The distance to 0; It's written in

In collection S in , Any two points , such as A spot B spot （ Not coincident ）, The distance is greater than 0; It's written in

In collection S in , Any three points , such as A spot B spot C spot （ Not coincident ）, The distance is ：B To A Distance of , Must be less than B To C Distance plus C To A Distance of , It's written in ：

         In the metric space, the most consistent with people's intuitive understanding of reality is three-dimensional Euclid space . in fact ,“ Measure ” The concept of is Euclid distance The generalization of four well-known properties . Euclidean metric defines the distance between two points as the A straight line paragraph The length of . Besides , There are other metric spaces , Such as Elliptic geometry And Hyperbolic geometry , The distance measured by angle on the sphere is also a degree . Special relativity Using hyperbolic geometry Hyperboloid model , As Speed The metric space of .

2.2 Algebraic understanding of the definition of distance space

         Be careful , What is the difference between algebraic understanding and geometric understanding ？ answer ： For the understanding of Geometry , The highest dimension is three-dimensional ; And algebraic understanding , It can be extended to N dimension , Even infinite dimensions .

metric space For one Ordered pair  (M,d), among  M  by aggregate and  d  For in  M  Above all Measure (metric), Function

Make for any in M Inner x、y、z, The following conditions are true ：

1.  ( Nonnegativity )
2.   ( The identity of the indistinguishable )
3.    ( symmetry )
4.    ( Trigonometric inequality ).

  Metric spaces can also be exported The opening episode And Closed set And so on. Topological properties , This leads to a more abstract Topological space A study of .

Be careful ： The algebraic understanding of distance is more abstract , So that some distance space may not be able to draw an image .

3、 ... and 、 Relatively simple distance space

The following questions need some proof , The proof requires some basic theorems , Here we first introduce these principles ：

principle 1 ： If a>b, and a>-b, that a>|b|.

principle 2： If a>|b|, So there are a>b establish ,a>-b It was also established .

        We are building mathematical models , If some attributes are found to be a distance space , that , The entire set satisfies this relationship , Can greatly simplify data complexity .  below , We will demonstrate the distance space of travel colors ：

3.1 One dimensional number axis

  Take the one-dimensional number axis as a set of points , Then the distance between any two points on the number axis ：

, namely A and B The distance between two points is the absolute value of the coordinate value difference , We verify whether it is distance space ：

• Nonnegativity ：,  establish
• identity ：, The coincidence distance between two points is zero
• symmetry ：
• Trigonometric inequality ： Must prove ( Here's the picture )：

prove ：

because ： 

 

--- This is through the above 3 The type and 6 The formula is added together .

--- This is through the above 4 The type and 5 The formula is added together .

therefore ：

（ The principle of this step is , if ）                  Certificate completion .

3.2 Manhattan distance

We are learning the principle of computer , I often meet “ Manhattan distance ”, The following proof ,“ Manhattan distance ” Conform to the definition of distance space .

  The above figure shows the Manhattan distance ： On the two-dimensional plane ,A Coordinates are （6,1）,B Point coordinates （1,5）, that A To B The distance function is ：

d(A,B)=5+4 =9 ; A more formal expression is ：

Now verify whether the distance space ：

• Nonnegativity ：,  establish
• identity ：

                  , The coincidence distance between two points is

• symmetry ：
• Trigonometric inequality ： Must prove Verified as follows ：

therefore , Just prove the objective inequality , That's all right. ：

 

  Here we only verify X Shaft part , The same principle is extended to Y Shaft part ：

（ Through the above 1、4 Merge to get ）

（ Through the above 2、3 Merge to get ）

therefore ,

There are also : 

So the above （1） Form established , That is, Manhattan distance conforms to distance space .（ Certificate completion ）

Reference article

https://zh.wikipedia.org/zh-cn/%E5%BA%A6%E9%87%8F%E7%A9%BA%E9%97%B4