机器学习

We have computed the distance between points as the Euclidean distance, which is something
that you learnt about in high school. However, it is not the only option, nor is it necessarily the most
useful. In this section we will look at the underlying idea behind distance calculations and possible
alternatives.
If I were to ask you to find the distance between my house and the nearest shop, then your first
guess might involve taking a map of my town, locating my house and the shop, and using a ruler to
measure the distance between them. By careful application of the map scale you can now tell me how
far it is. However, when I set out to buy some milk I’m liable to find that I have to walk rather further
than you’ve told me, since the direct line that you measured would involve walking through (or over)
several houses, and some serious fence-scaling. Your ‘as the crow flies’ distance is the shortest possible
path, and it is the straight-line, or Euclidean, distance. You can measure it on the map by just using a
ruler, but it essentially consists of measuring the distance in one direction (we’ll call it
north-south) and then the distance in another direction that is perpendicular to the first (let’s call it
east-west) and then squaring them, adding them together, and then taking the square root of that.
Writing that out, the Euclidean distance that we are all used to is:
where (x1, y1) is the location of my house in some coordinate system (say by using a GPS tracker) and
(x2, y2) is the location of the shop.
If I told you that my town was laid out on a grid block system, as is common in towns that were
built in the interval between the invention of the motor car and the invention of innovative town
planners, then you would probably use a different measure. You would measure the distance between
my house and the shop in the ‘north-south’ direction and the distance in the ‘east-west’ direction, and
then add the two distances together. This would correspond to the distance I actually had to walk. It is
often known as the city-block or Manhattan distance and looks like:
The point of this discussion is to show that there is more than one way to measure a distance,
and that they can provide radically different answers. These two different distances can be seen in
Figure 11. Mathematically, these distance measures are known as metrics. A metric function or norm
takes two inputs and gives a scalar (the distance) back, which is positive, and 0 if and only if the two
points are the same, symmetric (so that the distance
to the shop is the same as the distance back), and obeys the triangle inequality, which says that the
distance from a to b plus the distance from b to c should not be less than the direct distance from a to FIGURE 10: The Euclidean and city-block distances between two points.
Most of the data that we are going to have to analyse lives in rather more than two dimensions.
Fortunately, the Euclidean distance that we know about generalises very well to higher dimensions (and
so does the city-block metric). In fact, these two measures are both instances of a class of metrics that
work in any number of dimensions. The general measure is the Minkowski metric and it is written as:
If we put k = 1 then we get the city-block distance (Equation (7.12)), and k = 2 gives the
Euclidean distance (Equation (7.11)). Thus, you might possibly see the Euclidean metric written as the L2
norm and the city-block distance as the L1 norm. These norms have another interesting feature.
Remember that we can define different averages of a set of numbers. If we define the average as the
point that minimises the sum of the distance to every datapoint, then it turns out that the mean
minimises the Euclidean distance (the sum-of-squares distance), and the median minimises the L1
metric.
There are plenty of other possible metrics to choose, depending upon the dataspace. We
generally assume that the space is flat (if it isn’t, then none of these techniques work, and we don’t
want to worry about that). However, it can still be beneficial to look at other metrics. Suppose that we
want our classifier to be able to recognise images, for example of faces. We take a set of digital photos
of faces and use the pixel values as features. Then we use the nearest neighbour algorithm that we’ve
just seen to identify each face. Even if we ensure that all of the photos are taken fully face-on, there are
still a few things that will get in the way of this method. One is that slight variations in the angle of the
head (or the camera) could make a difference; another is that different distances between the face and
the camera (scaling) will change the results; and another is that different lighting conditions will make a
difference. We can try to fix all of these things in preprocessing, but there is also another alternative:
use a different metric that is invariant to these changes, i.e., it does not vary as they do. The idea of
invariant metrics is to find measures that ignore changes that you don’t want. So if you want to be able
to rotate shapes around and still recognize them, you need a metric that is invariant to rotation.
A common invariant metric in use for images is the tangent distance, which is an approximation
to the Taylor expansion in first derivatives, and works very well for small rotations and scalings; for
example, it was used to halve the final error rate on nearest neighbor classification of a set of
handwritten letters. Invariant metrics are an interesting topic for further study, and there is a reference
for them in the Further Reading section if you are interested.