自然最近邻居的定义及改进
自然最近邻居的定义
定义 3.1：自然最近邻居（3N 邻居）。对于数据对象 X，若有数据对象 Y 认为X是其近邻，且数据集中最离群的数据对象 Z 都有一个数据对象认为 Z 为其邻居，称数据对象 Y 为数据对象 X 的自然最近邻居。最离群的数据点 Z 就是数据集中最后一个第一次出现在其它点邻域中的点。
定义 3.2：自然特征值（ ）由公式 3.1 自适应得来的 值被称作数据集的自然特征值。值在K-最近邻居的意义下就是K，与K值不同的就是 是通过算法 3.1 自适应得到的。
此算法对没有噪声点的数据集执行效果很好，但若数据集中有噪声点此算法的时间复杂度就会很高，即此算法对噪声数据非常敏感
自然最近邻域图
定义3.3 自然最近邻域图（3NG）。连接数据集中每个数据点的自然最近邻居所形成的一个自适应邻域图， 称为自然最近邻域图（3NG）
定义3.4 对称邻域图。将每个点与其互为自然最近邻局的点相连接形成的邻域图，称为对称邻域图。在对称邻域图中数据点之间的邻居关系是对称的，即图中每条边的两个顶点，都是互相彼此的自然自然最近邻居。
定义3.5 小值最近邻域图（MNG）。将每个点与mini{nb(i),supk}个最近邻居相连接，形成的有向图，即小值最近邻域图中的邻居关系是有向的，若x为y的邻居，y不一定为x的邻居，称为小值最近邻域图。
小值最近邻域图中的变数比自然最近邻域图的要少。这是因为在自然最近邻域图中，和每个点相关的边至少有supk个，即每个点的度大于等于supk，而小值最近邻域图中和每个点相关的边最多为supk个，即每个点的度小于等于supk。 小值邻域图是有向图，自然最近邻域图为无向图。定义3.6：饱和最近邻域图（SNG）：将数据集中的每个点与Max{nb(i)}相连，形成连通性非常好的自适应邻域图，叫做饱和邻域图。
自然最近邻居的改进
定義3.7：自然離群點。經過算法3.1的r+1次循環后nb(i)為零的點的數目與第r次循環后nb(i)為零的點的數目相同，那麼就稱餘下的nb(i)為零的數據點i為自然離群點。
定义 3.8：自然最近邻居（3N 邻居）。对于数据对象 X，若有数据对象 Y 认为 X 为其近邻，且在算法 3.2 中找出了所有自然离群点时，称数据对象 Y 为数据对象 X 的自然最近邻居。改进后的就算自然最近邻居的算法如下所示：
改進后的算法在原算法的基礎上降低了時間複雜度，而且對於實驗效果而言，在沒有離群點的流形或非流形數據集上都和原算法的效果相同，在含有離群點的數據集中很明顯比原算法更優。