k近邻（k nearest neighbor）算法是一种监督算法，用于分类。它基本思想是计算新实例和训练集元素的**距离**，找出k个最接近的实例（neighbor），统计它们所属分类，次数最多的类别作为新实例的类别。

原理与步骤

监督算法可大致分成两个步骤：训练（train）和分类（classify）。从实现考虑还需要算法初始化过程。

本节的代码为python风格的示意代码，不能直接运行，可运行代码参考zxml。

示意代码

class KNearestNeighbor:

    def __init__(...):  pass

    def train(...):     pass

    def classify(...):  pass

训练（train）

理论上k近邻算法不需要训练，可直接使用原始数据进行分类。

归一化

数据的分类的量纲差别较大时，小量纲分类在计算的权重将被削弱。使用归一化消除这种影响。方法如下：

x̂ = (x − x_min)/(x_max − x_min)

预处理

将数据进行某种形式的处理可加快寻找k近邻的速度，常用的处理方式有KD-Tree和Ball-Tree，前者对低维欧氏距离有效，后者对所有距离有效。

示意代码

def train(self, X, C):

    '''X,C分别代表实例和类别'''

    # 实例数据归一化，并保留数据备份

    (self.X, self.C) = (normalize(X), C.copy())

    # 可选，如果需要，则构建KD-Tree()

    self.tree = KDTree()

    self.tree.create(self.X)

分类（classify）

分类的大致步骤：找出k个近邻 和*统计类别的次数* 。 分类的部分处理与训练的处理向对应，如：

• 训练对数据进行归一化，则分类是也需要归一化。
• 训练使用如KD-Tree等方式进行处理，则分类使用对应的方法寻找k个近邻。

示意代码

def classify(self, x):

    _x = normalize(x)                   # 将x归一化

    nearest = self.find_neighbors(_x)   # 找出k个近邻

    freq = frequency(nearests)          # 统计每个类型的次数

    return freq.sorted()[-1]            # 排序后，返回次数最多的类别

def find_neighbors(self, x):

    '''寻找与x最接近的k个点'''

    if self.tree == None:               # 判断是否使用了kd-tree

        ds = self.distance(x, self.X)   # 计算所有点的距离

        indices = ds.argsort()[0:k]     # 排序后，取前面k个

    else:

        indices = self.tree.find_neighbors(x, self.k)

    # indices是k个近邻的索引位置

    return self.C[indices]

初始化（init）

初始化需要设置算法参数，如k的值，距离公式。

距离

实例之间的距离一般采用欧氏距离，但不排除使用其它的距离计算方法。欧氏距离：

d = ∥x − y∥ = √(∑(x_i − y_i)²) ≥ ∥x_i − y_i∥

def __init__(self, k, distance=euclidean ):

    (self.k, self.distance) = (k, distance)

scikit-learn

下面使用scikit-learn中的k近邻算法分类的例子。

import numpy as np

from sklearn import neighbors

# 准备数据，分成A B两类。A类在[0,0]附近，B类在[1,1]附近。

X = np.array([[0, 0.1],   [-0.1, 0],

              [0.1, 0.1], [0, 0],

              [1, 1],     [1.1, 1],

              [1, 1.1],   [1.1, 1.1]])

C = ['A','A','A','A','B','B','B','B']

# 初始化

clf = neighbors.KNeighborsClassifier(n_neighbors=3, weights="uniform")

# 训练

clf.fit(X, C)

# 分类

c = clf.predict(np.array([[0.9,0.8]]))

print(c)

上面的例子可以将k近邻算法分成三步，初始化、训练和分类。初始化可设置参数，本文涉及到的参数有：

• n_neighbors: 指参数k
• weights: 指定数据分类的权重，归一化 是其中的一个方式。
• algorithm: 该参数可设定使用kd-tree等方法。
• metric: 距离计算公式

参考资料

• 《Machine Learning in Action》第2章
• https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm
• https://code.csdn.net/lemene/zxml/tree/master
• http://scikit-learn.org/stable/modules/neighbors.html

说明

类的构造函数抛出异常，不会调用该类的析构函数，资源的释放原则是编译器申请的编译器负责，程序员申请的程序员负责。
在实验代码中，子类Except的构造函数抛出异常，则Base和mMember1的构造函数是编译器调用，因此编译器会调用它们的析构函数，而mMember2由程序员主动使用new生成，因此需要程序员主动使用delete。

解决方法：

1. 在构造函数中使用try...catch结构
2. 使用类包装资源申请，如auto_ptr。

实验代码

/** 
 * @file constructor_exception.cpp
 * @brief 测试构造函数异常引起的行为
 * @copyright public domain
 */
#include <iostream>
#include <exception>
#include <memory>
class Base {
public:
Base() { std::cout << "Base()" << std::endl; }
virtual ~Base() { std::cout << "~Base()" << std::endl; }
};
class Member {
public:
Member(int id):mId(id) { std::cout << "Member():" << mId << std::endl; }
virtual ~Member() { std::cout << "~Member()" << mId << std::endl; }
protected:
int mId;
};
class Except : public Base {
public:
Except() : mMember1(1), mMember2(NULL) { 
std::cout << "Except() enter" << std::endl; 
mMember2 = new Member(2);
mMember3.reset(new Member(3));
throw std::exception();
std::cout << "Except() leave" << std::endl; 
}
virtual ~Except() { 
delete mMember2;
std::cout << "~Except()" << std::endl; 
}
protected:
Member mMember1;
Member *mMember2;
std::auto_ptr<Member> mMember3;
};
int main() {
try {
Except e;
} catch (std::exception& e) {
std::cout << e.what() << std::endl;
}
return 0;
}

运行及结果

$ g++ constructor_exception.cpp 
$ ./a.out 
Base()
Member():1
Except() enter
Member():2
Member():3
~Member()3
~Member()1
~Base()
std::exception

构造函数的调用顺序是先父类再子类。析构函数的顺序相反——先子类再父类。有继承关系的类的析构函数需要声明为virtual，但并非必须。声明virtual表明函数不能再编译期间确定，只有在运行时才能确定。这样的场景是删除基类指针，但其指向是派生类。此时编译器看到的只有基类信息，如果没有声明virtual，就没有虚函数表或者虚函数表没有析构函数项，只能调用基类的析构函数。如果不声明virtual，将子类指针赋值给父类指针是有风险的操作。

## 实验代码

```C

/**

 * @file constructor_destructor_sequence.cpp

 * @brief 测试构造析构函数的调用次序

 * @copyright public domain

 */

#include <iostream>

class Base {

public:

    Base() { std::cout << "Base()" << std::endl; }

    ~Base() { std::cout << "~Base()" << std::endl; }

};

class VBase {

public:

    VBase() { std::cout << "VBase()" << std::endl; }

    virtual ~VBase() { std::cout << "~VBase()" << std::endl; }

};

class Derived : public Base {

public:

    Derived() { std::cout << "Derived()" << std::endl; }

    ~Derived() { std::cout << "~Derived()" << std::endl; }

};

class VDerived: public VBase {

public:

    Derived() { std::cout << "VDerived()" << std::endl; }

    ~VDerived() { std::cout << "~VDerived()" << std::endl; }

};

void test_0() {

    std::cout <<"子类不声明virtual，按基类指针删除派生类" << std::endl;

    VBase* p = new VDerived;

    delete p;

}

void test_1() {

    std::cout <<"不声明virtual，按派生类指针删除派生类" << std::endl;

    Derived* p = new Derived;

    delete p;

}

void test_2() {

    std::cout <<"不声明virtual，按基类指针删除派生类" << std::endl;

    Base* p = new Derived;

    delete p;

}

void test_3() {

    std::cout <<"不声明virtual，按void*删除派生类" << std::endl;

    void* p = new Derived;

    delete p;

}

int main() {

    test_0();

    test_1();

    test_2();

    test_3();

    return 0;

}

```

## 运行及结果

    > g++ constructor_destructor_sequence.cpp

    constructor_destructor_sequence.cpp: In function 'void test_3()':

    constructor_destructor_sequence.cpp:54:9: warning: deleting 'void*' is undefined [enabled by default]

    > a.exe

    子类不声明virtual，按基类指针删除派生类

    VBase()

    VDerived()

    ~VDerived()

    ~VBase()

    不声明virtual，按派生类指针删除派生类

    Base()

    Derived()

    ~Derived()

    ~Base()

    不声明virtual，按基类指针删除派生类

    Base()

    Derived()

    ~Base()

    不声明virtual，按void*删除派生类

    Base()

    Derived()

说明

使用char[]和char*定义变量，并赋值字符串常量，这两者有较大区别。前者定义数组，并将字符串常量拷贝至该数组，变量表示这个新数组的首地址。后者定义指针，指向一个字符常量。前者会产生新的字符串数据，并且拥有读写权限，后者不一定产生新字符串数据，并且只有读权限。

实验代码

/**
 * @file char_array_pointer.cpp
 * @brief 测试字符数组和指针
 * @copyrigh public domain
 */
#include <iostream>
const char* string0() {
const char* str = "string";
return str;
}
const char* string1() {
return "string";
}
const char* string2() {
static const char str[] = "string";
return str;
}
const char* string3() {
    char str[] = "string";
    return str;
}
void function() {
    char a[] = "abc123456";
}
void test_string1() {
    const char* str = string1();
    std::cout << "test_string1: " << str << std::endl;
    function();
    std::cout << "test_string1: " << str << std::endl;
}
void test_string2() {
    const char* str = string2();
    std::cout << "test_string2: " << str << std::endl;
    function();
    std::cout << "test_string2: " << str << std::endl;
}
void test_string3() {
    const char* str = string3();
    std::cout << "test_string3: " << str << std::endl;
    function();
    std::cout << "test_string3: " << str << std::endl;
}
int main() {
std::cout << "string0 == string1 is " << (string0() == string1() ? "true" : "false") << std::endl;
std::cout << "string1 == string2 is " << (string1() == string2() ? "true" : "false") << std::endl;
    test_string1();
    test_string2();
    test_string3();
    return 0;
}

运行及结果

$ g++ char_array_pointer.cpp
char_array_pointer.cpp: In function 'const char* string3()':
char_array_pointer.cpp:24:10: warning: address of local variable 'str' returned [enabled by default]

$ ./a.exe
string0 == string1 is true
string1 == string2 is false
test_string1: string
test_string1: string
test_string2: string
test_string2: string
test_string3: string
test_string3: abc12345YP@

说明

字符串常量会放入程序的静态区，并且是只读数据段。由于是只读数据，编译器会合并相同的字符串常量。

实验代码

/**
 * @file constant_string.cpp
 * @brief 测试常量字符串
 * @copyright public domain
 */
#include <iostream>
int main() {
    char* a = "string";
    const char* b = "string";
    std::cout << "a == b is " << (a==b ? "true" : "false") << std::endl;
    a[1] = 'd'; // ERROR
    return 0;
}

运行及结果

$ g++ constant_string.cpp 
constant_string.cpp: In function ‘int main()’:
constant_string.cpp:10:12: warning: deprecated conversion from string constant to ‘char*’ [-Wwrite-strings]
  char* a = "string";
            ^
$ ./a.out 
a == b is true
段错误 (核心已转储)

• a和b的地址相同。
• 编译器会对char* a = "string"报警告。
• 对字符串常量的修改会引发程序异常。

说明

big endian和little endian表示如何存放多字节数据。前者低位字节排放在内存的高端，后者相反。将unsigned long数据强制转换成unsigned char*数据，则它们在两种模式下的对应关系如下：

big endian：

ul = (uc[0]<< 24) + (uc[1]<<16) + (uc[2]<<8) + uc[3];

little endian:

ul = (uc[3]<<24) + (uc[2]<<16) + (uc[1]<<8) + uc[0];

实验代码

/**
 * @file little_big_endian.cpp
 * @brief 测试大小端字节序
 * @copyright public domain
 */
#include <iostream>
static bool is_little_endian() {
union {
long l;
char cs[4];
} t;
t.l = 1;
return t.cs[0] == 1;
}
int main() {
unsigned long ul = 0x12345678;
unsigned char* uc = (unsigned char*)&ul;
if (is_little_endian()) {
bool r = (uc[0] + (uc[1]<<8) + (uc[2]<<16) + (uc[3]<<24)) == ul;
std::cout << "little: (uc[0] + (uc[1]<<8) + (uc[2]<<16) + (uc[3]<<24)) == ul is " << (r ? "true" : "false") << std::endl;
} else {
bool r = (uc[3] + (uc[2]<<8) + (uc[1]<<16) + (uc[0]<<24)) == ul;
std::cout << "little: (uc[3] + (uc[2]<<8) + (uc[1]<<16) + (uc[0]<<24)) == ul is " << (r ? "true" : "false") << std::endl;
}
return 0;
}

运行及结果

$ g++ little_big_endian.cpp 
$ ./a.out 
little: (uc[0] + (uc[1]<<8) + (uc[2]<<16) + (uc[3]<<24)) == ul is true

常见问题

字节序的问题容易出现在不同电脑交互数据的时候，因此当数据输出时——保存成文件或在网络上传输——就应该考虑字节序。

说明

C++类成员初始化顺序取决于其声明顺序，而非初始化列表的顺序。

测试代码

/**
 * 测试类成员的初始化顺序
 * @file init_oder.cpp
 */
#include <iostream>
class Test {
public:
    Test() : mBb(sIndex++), mAa(sIndex++) { }
public:
    void Dump() {
        std::cout<< "a: " << mAa << ", b: " << mBb << std::endl;
    } 
protected:
    int mAa;
    int mBb;
    static int sIndex;
};
int Test::sIndex = 1;
int main() {
    Test t;
    t.Dump();
    return 0;
}

运行及结果

$ g++ init_order.cpp
$ ./a.out
a: 1, b: 2

风险分析

当类的成员初始化有依赖关系（如某个成员的构造函数的参数是另一个成员）时，较容易出错。这是因为程序员的意图（初始化列表顺序）和程序的行为（成员声明 顺序）是分离的，前者一般位于实现文件，后者位于头文件，编辑前者往往忽略后者。因此少用有依赖的初始化设计，并且在review中加入该检查条目。

• 编译器为不含任何成员的空类分配大小为1的空间，这样空类定义的变量地址不会与其相邻定义的变量地址相同。
• 编译器会在空类的子类中优化掉这多分配的空间。
• 带虚析构函数的空类不是严格意义的空类，它包含虚函数表指针，因此其大小为指针的大小。

实验代码

/**
 * @file empty_size.cpp
 * @brief 测试空类的大小
 * @copyright public domain
 */
#include<iostream>
class Empty { };
class SubEmpty : public Empty
{
protected:
    int mInt; 
};
class VEmpty
{
public:
    virtual ~VEmpty() = 0;
};
int main() 
{
    std::cout << "Empty class: " << sizeof(Empty) << std::endl;
    std::cout << "SubEmpty: " << sizeof(SubEmpty) << std::endl;
    std::cout << "VEmpty: " << sizeof(VEmpty) << std::endl;
    std::cout << "Void*: " << sizeof(void*) << std::endl;
    return 0;
};

运行及结果

> g++ empty_size.cpp
> a.exe
Empty class: 1
SubEmpty: 4
VEmpty: 8
Void*: 8