众所周知,电影可以按照题材分类,然而题材本身是如何定义的?由谁来判定某部电影属于哪个题材?也就是说同一题材的电影具有哪些公共特征?这些都是在进行电影分类时必须要考虑的问题。没有哪个电影人会说自己制作的电影和以前的某部电影类似,但我们确实知道每部电影在风格上的确可能会和同题材的电影相近。那么动作片具有哪些共有特征,使得动作片之间非常类似,而与爱情片存在着明显的差别呢?动作片中也会存在接吻镜头,爱情片中也会存在打斗场景,我们不能单纯依靠是否存在打斗或接吻来判断影片的类型。但是爱情片中的接吻镜头更多、动作片中的打斗场景也更频繁,基于此类场景在某部电影中出现的次数可以用来进行电影分类。
以上是《机器学习实战》中介绍 K 最邻近算法给出的示例,通过该示例我们可以了解到 K 最邻近算法应用的一个场景:解决影片分类问题。
我们首先,先介绍一下该算法的基本原理,由于篇幅的限制,详细的理论部分可以参见对应的维基百科。
1. K 最邻近算法
K 最邻近算法(K-NN )是一种基于特征空间中最近训练实例对目标进行分类的方法。它是所有机器学习算法中最简单的一种:一个对象通过其邻居的多数票进行分类,对象被分配到其最近的 K 个邻居中最常见的类(K 是一个正整数,通常很小)。
更详细的介绍,见维基百科:
https://en./wiki/K-nearest_neighbors_algorithm
K邻近算法 2. 欧氏距离
这就是我们最熟悉的 2-范数,即两点间的距离公式。
更详细的介绍,见维基百科:
https://en./wiki/Euclidean_distance
欧氏距离 3. 编辑距离
在信息论和计算机科学中,Levenshtein 距离是测量两个序列之间差异的一个字符串度量,也被称为编辑距离。非正式地说,两个单词之间的 Levenshtein 距离是将一个单词更改为另一个单词所需的最小字符编辑数(即插入、删除或替换)。
更详细的介绍,见维基百科:
https://en./wiki/Levenshtein_distance
编辑距离 有了以上的基础,我们再来介绍代码的实现与应用,比较相似性就要定义距离,我们在这里定理了欧氏距离和编辑距离,大家可以根据使用场景,通过实现IDistance<T>
接口的方式来定义更多的距离。在使用 K 最邻近算法 KNearestNeighbors<T>
时,使用依赖注入的方式把所用的距离对象注入进去就好。
1. 距离的定义。
定义接口:
public interface IDistance <T > { double Distance (T x, T y) ; }
定义欧氏距离:
public sealed class Euclidean : IDistance<double []> { public double Distance (double [] x, double [] y) { double sum = 0.0 ; for (int i = 0 ; i < x.Length; i++) { double u = x[i] - y[i]; sum += u * u; } return Math.Sqrt(sum); } }
定义编辑距离:
public sealed class Levenshtein : IMetric<string > { public double Distance (string x, string y) { if (string .IsNullOrEmpty(x)) { if (y == null || y.Length != 0 ) return 0 ; return y.Length; } if (string .IsNullOrEmpty(y)) return x.Length; int [,] d = new int [x.Length + 1 , y.Length + 1 ]; for (int i = 0 ; i <= x.Length; i++) d[i, 0 ] = i; for (int i = 0 ; i <= y.Length; i++) d[0 , i] = i; for (int i = 0 ; i < x.Length; i++) { for (int j = 0 ; j < y.Length; j++) { int cost = (x[i] == y[j]) ? 0 : 1 ; int a = d[i, j + 1 ] + 1 ; int b = d[i + 1 , j] + 1 ; int c = d[i, j] + cost; d[i + 1 , j + 1 ] = Math.Min(Math.Min(a, b), c); } } return d[x.Length, y.Length]; } }
2. K 最邻近算法的封装。
public class KNearestNeighbors <T> { private int _k; private IDistance<T> _distance; private double [] _distances; public int K { get { return _k; } set { if (value <= 0 || value > Inputs.Length) throw new Exception(@"k的值应大于零且小于输入样本总数。" ); _k = value; } } public IDistance<T> Distance { get { return _distance; } set { _distance = value; } } public int ClassCount { get; private set ; } public T[] Inputs { get; private set ; } public int [] Outputs { get; private set ; } private static void CheckArgs (int k, int classes, T[] inputs, int [] outputs, IDistance<T> distance) { if (k <= 0 ) throw new Exception(@"邻居数应大于零。" ); if ( classes <= 0 ) throw new Exception(@"类的数目应大于零。" ); if (inputs == null) throw new ArgumentNullException(); if (outputs == null) throw new ArgumentNullException(); if (inputs.Length != outputs.Length) throw new Exception(@"输入向量的数量应与相应输出标签的数量匹配。" ); if (distance == null) throw new ArgumentNullException(); } private void Initialize (int k, int classes, T[] inputs, int [] outputs, IDistance<T> distance) { _k = k; _distance = distance; _distances = new double [inputs.Length]; Inputs = inputs; Outputs = outputs; ClassCount = classes; } public KNearestNeighbors (int k, int classes, T[] inputs, int [] outputs, IDistance<T> distance) { CheckArgs(k, classes, inputs, outputs, distance); Initialize(k, classes, inputs, outputs, distance); } public KNearestNeighbors (int k, T[] inputs, int [] outputs, IDistance<T> distance) { int classCount = outputs.Distinct().Length; CheckArgs(k, classCount, inputs, outputs, distance); Initialize(k, classCount, inputs, outputs, distance); } public virtual int Compute (T input) { double [] scores; return Compute(input, out scores); } public virtual int Compute (T input, out double [] scores) { for (int i = 0 ; i < Inputs.Length; i++) _distances[i] = _distance.Distance(input, Inputs[i]); int [] idx = _distances.Bottom(_k, true ); scores = new double [ClassCount]; for (int i = 0 ; i < idx.Length; i++) { int j = idx[i]; int label = Outputs[j]; double d = _distances[i]; scores[label] += 1.0 / (1.0 + d); } int result; scores.Max(out result); return result; } }
3. K 最邻近算法的应用
下面的示例演示如何创建和使用 K 最邻近算法,对一组数字向量进行分类。
首先,创建一些示例学习数据。在这个数据中,前两个实例属于一类,接下来的四个实例属于一类,最后三个实例属于一类。
double [][] inputs = { //类 0 new double [] {-5 , -2 , -1 }, new double [] {-5 , -5 , -6 }, //类 1 new double [] {2 , 1 , 1 }, new double [] {1 , 1 , 2 }, new double [] {1 , 2 , 2 }, new double [] {3 , 1 , 2 }, //类 2 new double [] {11 , 5 , 4 }, new double [] {15 , 5 , 6 }, new double [] {10 , 5 , 6 }, };int [] outputs = { 0 ,0 , 1 ,1 ,1 ,1 , 2 ,2 ,2 , };
现在我们将创建 K 最邻近算法。对于这个例子,我们选择 k = 4。这意味着,在给定的情况下,将使用其最近的 4个邻居来作出决定。
KNearestNeighbors<double []> knn = new KNearestNeighbors<double []>(4 , 3 , inputs, outputs, new Euclidean());
创建算法之后,我们可以对新实例进行分类:
int answer = knn.Compute(new double [] { 11 , 5 , 4 });
最后得到结果 answer = 2,样本“{ 11, 5, 4 }”属于标签为 2 的这一类。
当然,K 最邻近算法可用于任何类型的数据。在下面的例子中,我们将看到如何使用它来比较字符串。
string [] inputs = { "Car" , // 0 "Bar" , // 0 "Jar" , // 0 "Charm" , // 1 "Chair" // 1 };int [] outputs = { 0 , 0 , 0 , 1 , 1 , };
现在我们创建 K 最邻近算法。对于这个例子,我们选择 k = 1。这意味着,在给定的情况下,只使用其最近的邻居来进行新的决策。
为了比较字符串,我们使用 Levenshtein 的字符串距离。
KNearestNeighbors<string > knn = new KNearestNeighbors<string >(1 , 2 , inputs, outputs, new Levenshtein());
创建算法后,我们可以使用它对新实例进行分类:
int answer = knn.Compute("Chars" );
最后得到结果 answer = 1,字符串 “Chars” 属于标签为 1 的这一类。