㈠ OPTICS聚类算法的matlab实现
OPTICS聚类算法代码，从http://www.pudn.com/downloads238/sourcecode/math/detail1113278.html
该处下载。
% -------------------------------------------------------------------------
% Function:
% [RD,CD,order]=optics(x,k)
% -------------------------------------------------------------------------
% Aim:
% Ordering objects of a data set to obtain the clustering structure
% -------------------------------------------------------------------------
% Input:
% x - data set (m,n); m-objects, n-variables
% k - number of objects in a neighborhood of the selected object
% (minimal number of objects considered as a cluster)
% -------------------------------------------------------------------------
% Output:
% RD - vector with reachability distances (m,1)
% CD - vector with core distances (m,1)
% order - vector specifying the order of objects (1,m)
% -------------------------------------------------------------------------
% Example of use:
% x=[randn(30,2)*.4;randn(40,2)*.5+ones(40,1)*[4 4]];
% [RD,CD,order]=optics(x,4)
% -------------------------------------------------------------------------
%
function [RD,CD,order]=optics(x,k)
[m,n]=size(x);
CD=zeros(1,m);
RD=ones(1,m)*10^10;
% Calculate Core Distances
for i=1:m
D=sort(dist(x(i,:),x));
CD(i)=D(k+1);
end
order=[];
seeds=[1:m];
ind=1;
while ~isempty(seeds)
ob=seeds(ind);
seeds(ind)=[];
order=[order ob];
mm=max([ones(1,length(seeds))*CD(ob);dist(x(ob,:),x(seeds,:))]);
ii=(RD(seeds))>mm;
RD(seeds(ii))=mm(ii);
[i1 ind]=min(RD(seeds));
end
RD(1)=max(RD(2:m))+.1*max(RD(2:m));
function [D]=dist(i,x)
% function: [D]=dist(i,x)
%
% Aim:
% Calculates the Euclidean distances between the i-th object and all objects in x
% Input:
% i - an object (1,n)
% x - data matrix (m,n); m-objects, n-variables
%
% Output:
% D - Euclidean distance (m,1)
[m,n]=size(x);
D=(sum((((ones(m,1)*i)-x).^2)'));
if n==1
D=abs((ones(m,1)*i-x))';
end
㈡ 加密解密字符串的算法原理
我们经常需要一种措施来保护我们的数据，防止被一些怀有不良用心的人所看到或者破坏。在信息时代，信息可以帮助团体或个人，使他们受益，同样，信息也可以用来对他们构成威胁，造成破坏。在竞争激烈的大公司中，工业间谍经常会获取对方的情报。因此，在客观上就需要一种强有力的安全措施来保护机密数据不被窃取或篡改。数据加密与解密从宏观上讲是非常简单的，很容易理解。加密与解密的一些方法是非常直接的，很容易掌握，可以很方便的对机密数据进行加密和解密。
一：数据加密方法
在传统上，我们有几种方法来加密数据流。所有这些方法都可以用软件很容易的实现，但是当我们只知道密文的时候，是不容易破译这些加密算法的（当同时有原文和密文时，破译加密算法虽然也不是很容易，但已经是可能的了）。最好的加密算法对系统性能几乎没有影响，并且还可以带来其他内在的优点。例如，大家都知道的pkzip，它既压缩数据又加密数据。又如，dbms的一些软件包总是包含一些加密方法以使复制文件这一功能对一些敏感数据是无效的，或者需要用户的密码。所有这些加密算法都要有高效的加密和解密能力。
幸运的是，在所有的加密算法中最简单的一种就是“置换表”算法，这种算法也能很好达到加密的需要。每一个数据段（总是一个字节）对应着“置换表”中的一个偏移量，偏移量所对应的值就输出成为加密后的文件。加密程序和解密程序都需要一个这样的“置换表”。事实上，80x86 cpu系列就有一个指令‘xlat’在硬件级来完成这样的工作。这种加密算法比较简单，加密解密速度都很快，但是一旦这个“置换表”被对方获得，那这个加密方案就完全被识破了。更进一步讲，这种加密算法对于黑客破译来讲是相当直接的，只要找到一个“置换表”就可以了。这种方法在计算机出现之前就已经被广泛的使用。
对这种“置换表”方式的一个改进就是使用2个或者更多的“置换表”，这些表都是基于数据流中字节的位置的，或者基于数据流本身。这时，破译变的更加困难，因为黑客必须正确的做几次变换。通过使用更多的“置换表”，并且按伪随机的方式使用每个表，这种改进的加密方法已经变的很难破译。比如，我们可以对所有的偶数位置的数据使用a表，对所有的奇数位置使用b表，即使黑客获得了明文和密文，他想破译这个加密方案也是非常困难的，除非黑客确切的知道用了两张表。
与使用“置换表”相类似，“变换数据位置”也在计算机加密中使用。但是，这需要更多的执行时间。从输入中读入明文放到一个buffer中，再在buffer中对他们重排序，然后按这个顺序再输出。解密程序按相反的顺序还原数据。这种方法总是和一些别的加密算法混合使用，这就使得破译变的特别的困难，几乎有些不可能了。例如，有这样一个词，变换起字母的顺序，slient 可以变为listen，但所有的字母都没有变化，没有增加也没有减少，但是字母之间的顺序已经变化了。
但是，还有一种更好的加密算法，只有计算机可以做，就是字/字节循环移位和xor操作。如果我们把一个字或字节在一个数据流内做循环移位，使用多个或变化的方向（左移或右移），就可以迅速的产生一个加密的数据流。这种方法是很好的，破译它就更加困难！而且，更进一步的是，如果再使用xor操作，按位做异或操作，就就使破译密码更加困难了。如果再使用伪随机的方法，这涉及到要产生一系列的数字，我们可以使用fibbonaci数列。对数列所产生的数做模运算（例如模3），得到一个结果，然后循环移位这个结果的次数，将使破译次密码变的几乎不可能！但是，使用fibbonaci数列这种伪随机的方式所产生的密码对我们的解密程序来讲是非常容易的。
在一些情况下，我们想能够知道数据是否已经被篡改了或被破坏了，这时就需要产生一些校验码，并且把这些校验码插入到数据流中。这样做对数据的防伪与程序本身都是有好处的。但是感染计算机程序的病毒才不会在意这些数据或程序是否加过密，是否有数字签名。所以，加密程序在每次load到内存要开始执行时，都要检查一下本身是否被病毒感染，对与需要加、解密的文件都要做这种检查！很自然，这样一种方法体制应该保密的，因为病毒程序的编写者将会利用这些来破坏别人的程序或数据。因此，在一些反病毒或杀病毒软件中一定要使用加密技术。
循环冗余校验是一种典型的校验数据的方法。对于每一个数据块，它使用位循环移位和xor操作来产生一个16位或32位的校验和 ，这使得丢失一位或两个位的错误一定会导致校验和出错。这种方式很久以来就应用于文件的传输，例如 xmodem-crc。 这是方法已经成为标准，而且有详细的文档。但是，基于标准crc算法的一种修改算法对于发现加密数据块中的错误和文件是否被病毒感染是很有效的。
二．基于公钥的加密算法
一个好的加密算法的重要特点之一是具有这种能力：可以指定一个密码或密钥，并用它来加密明文，不同的密码或密钥产生不同的密文。这又分为两种方式：对称密钥算法和非对称密钥算法。所谓对称密钥算法就是加密解密都使用相同的密钥，非对称密钥算法就是加密解密使用不同的密钥。非常着名的pgp公钥加密以及rsa加密方法都是非对称加密算法。加密密钥，即公钥，与解密密钥，即私钥，是非常的不同的。从数学理论上讲，几乎没有真正不可逆的算法存在。例如，对于一个输入‘a’执行一个操作得到结果‘b’,那么我们可以基于‘b’，做一个相对应的操作，导出输入‘a’。在一些情况下，对于每一种操作，我们可以得到一个确定的值，或者该操作没有定义（比如，除数为0）。对于一个没有定义的操作来讲，基于加密算法，可以成功地防止把一个公钥变换成为私钥。因此，要想破译非对称加密算法，找到那个唯一的密钥，唯一的方法只能是反复的试验，而这需要大量的处理时间。
rsa加密算法使用了两个非常大的素数来产生公钥和私钥。即使从一个公钥中通过因数分解可以得到私钥，但这个运算所包含的计算量是非常巨大的，以至于在现实上是不可行的。加密算法本身也是很慢的，这使得使用rsa算法加密大量的数据变的有些不可行。这就使得一些现实中加密算法都基于rsa加密算法。pgp算法(以及大多数基于rsa算法的加密方法)使用公钥来加密一个对称加密算法的密钥，然后再利用一个快速的对称加密算法来加密数据。这个对称算法的密钥是随机产生的，是保密的，因此，得到这个密钥的唯一方法就是使用私钥来解密。
我们举一个例子：假定现在要加密一些数据使用密钥‘12345’。利用rsa公钥，使用rsa算法加密这个密钥‘12345’，并把它放在要加密的数据的前面（可能后面跟着一个分割符或文件长度，以区分数据和密钥），然后，使用对称加密算法加密正文，使用的密钥就是‘12345’。当对方收到时，解密程序找到加密过的密钥，并利用rsa私钥解密出来，然后再确定出数据的开始位置，利用密钥‘12345’来解密数据。这样就使得一个可靠的经过高效加密的数据安全地传输和解密。
一些简单的基于rsa算法的加密算法可在下面的站点找到：
ftp://ftp.funet.fi/pub/crypt/cryptography/asymmetric/rsa
三．一个崭新的多步加密算法
现在又出现了一种新的加密算法，据说是几乎不可能被破译的。这个算法在1998年6月1日才正式公布的。下面详细的介绍这个算法:
使用一系列的数字（比如说128位密钥），来产生一个可重复的但高度随机化的伪随机的数字的序列。一次使用256个表项，使用随机数序列来产生密码转表，如下所示：
把256个随机数放在一个距阵中，然后对他们进行排序，使用这样一种方式（我们要记住最初的位置）使用最初的位置来产生一个表，随意排序的表，表中的数字在0到255之间。如果不是很明白如何来做，就可以不管它。但是，下面也提供了一些原码（在下面）是我们明白是如何来做的。现在，产生了一个具体的256字节的表。让这个随机数产生器接着来产生这个表中的其余的数，以至于每个表是不同的。下一步，使用"shotgun technique"技术来产生解码表。基本上说，如果 a映射到b，那么b一定可以映射到a，所以b[a[n]] = n.（n是一个在0到255之间的数）。在一个循环中赋值，使用一个256字节的解码表它对应于我们刚才在上一步产生的256字节的加密表。
使用这个方法，已经可以产生这样的一个表，表的顺序是随机，所以产生这256个字节的随机数使用的是二次伪随机,使用了两个额外的16位的密码.现在，已经有了两张转换表，基本的加密解密是如下这样工作的。前一个字节密文是这个256字节的表的索引。或者，为了提高加密效果，可以使用多余8位的值，甚至使用校验和或者crc算法来产生索引字节。假定这个表是256*256的数组,将会是下面的样子:
crypto1 = a[crypto0][value]
变量'crypto1'是加密后的数据，'crypto0'是前一个加密数据（或着是前面几个加密数据的一个函数值）。很自然的，第一个数据需要一个“种子”，这个“种子” 是我们必须记住的。如果使用256*256的表，这样做将会增加密文的长度。或者，可以使用你产生出随机数序列所用的密码，也可能是它的crc校验和。顺便提及的是曾作过这样一个测试: 使用16个字节来产生表的索引,以128位的密钥作为这16个字节的初始的"种子"。然后，在产生出这些随机数的表之后，就可以用来加密数据，速度达到每秒钟100k个字节。一定要保证在加密与解密时都使用加密的值作为表的索引，而且这两次一定要匹配。
加密时所产生的伪随机序列是很随意的，可以设计成想要的任何序列。没有关于这个随机序列的详细的信息，解密密文是不现实的。例如：一些ascii码的序列，如“eeeeeeee"可能被转化成一些随机的没有任何意义的乱码，每一个字节都依赖于其前一个字节的密文，而不是实际的值。对于任一个单个的字符的这种变换来说，隐藏了加密数据的有效的真正的长度。
如果确实不理解如何来产生一个随机数序列，就考虑fibbonacci数列，使用2个双字（64位）的数作为产生随机数的种子，再加上第三个双字来做xor操作。 这个算法产生了一系列的随机数。算法如下：
unsigned long dw1, dw2, dw3, dwmask;
int i1;
unsigned long arandom[256];
dw1 = {seed #1};
dw2 = {seed #2};
dwmask = {seed #3};
// this gives you 3 32-bit "seeds", or 96 bits total
for(i1=0; i1 < 256; i1++)
{
dw3 = (dw1 + dw2) ^ dwmask;
arandom[i1] = dw3;
dw1 = dw2;
dw2 = dw3;
}
如果想产生一系列的随机数字，比如说，在0和列表中所有的随机数之间的一些数，就可以使用下面的方法：
int __cdecl mysortproc(void *p1, void *p2)
{
unsigned long **pp1 = (unsigned long **)p1;
unsigned long **pp2 = (unsigned long **)p2;
if(**pp1 < **pp2)
return(-1);
else if(**pp1 > *pp2)
return(1);
return(0);
}
...
int i1;
unsigned long *aprandom[256];
unsigned long arandom[256]; // same array as before, in this case
int aresult[256]; // results go here
for(i1=0; i1 < 256; i1++)
{
aprandom[i1] = arandom + i1;
}
// now sort it
qsort(aprandom, 256, sizeof(*aprandom), mysortproc);
// final step - offsets for pointers are placed into output array
for(i1=0; i1 < 256; i1++)
{
aresult[i1] = (int)(aprandom[i1] - arandom);
}
...
变量'aresult'中的值应该是一个排过序的唯一的一系列的整数的数组，整数的值的范围均在0到255之间。这样一个数组是非常有用的，例如：对一个字节对字节的转换表，就可以很容易并且非常可靠的来产生一个短的密钥（经常作为一些随机数的种子）。这样一个表还有其他的用处，比如说：来产生一个随机的字符，计算机游戏中一个物体的随机的位置等等。上面的例子就其本身而言并没有构成一个加密算法，只是加密算法一个组成部分。
作为一个测试，开发了一个应用程序来测试上面所描述的加密算法。程序本身都经过了几次的优化和修改，来提高随机数的真正的随机性和防止会产生一些短的可重复的用于加密的随机数。用这个程序来加密一个文件，破解这个文件可能会需要非常巨大的时间以至于在现实上是不可能的。
四．结论：
由于在现实生活中，我们要确保一些敏感的数据只能被有相应权限的人看到，要确保信息在传输的过程中不会被篡改，截取，这就需要很多的安全系统大量的应用于政府、大公司以及个人系统。数据加密是肯定可以被破解的，但我们所想要的是一个特定时期的安全，也就是说，密文的破解应该是足够的困难，在现实上是不可能的，尤其是短时间内。
㈢ KNN算法常见问题总结
给定测试实例，基于某种距离度量找出训练集中与其最靠近的k个实例点，然后基于这k个最近邻的信息来进行预测。
通常，在分类任务中可使用“投票法”，即选择这k个实例中出现最多的标记类别作为预测结果；在回归任务中可使用“平均法”，即将这k个实例的实值输出标记的平均值作为预测结果；还可基于距离远近进行加权平均或加权投票，距离越近的实例权重越大。
k近邻法不具有显式的学习过程，事实上，它是懒惰学习（lazy learning）的着名代表，此类学习技术在训练阶段仅仅是把样本保存起来，训练时间开销为零，待收到测试样本后再进行处理。
KNN一般采用欧氏距离，也可采用其他距离度量，一般的Lp距离：
KNN中的K值选取对K近邻算法的结果会产生重大影响。如果选择较小的K值，就相当于用较小的领域中的训练实例进行预测，“学习”近似误差（近似误差：可以理解为对现有训练集的训练误差）会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是“学习”的估计误差会增大，换句话说，K值的减小就意味着整体模型变得复杂，容易发生过拟合；
如果选择较大的K值，就相当于用较大领域中的训练实例进行预测，其优点是可以减少学习的估计误差，但缺点是学习的近似误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误，且K值的增大就意味着整体的模型变得简单。
在实际应用中，K值一般取一个比较小的数值，例如采用交叉验证法来选择最优的K值。经验规则：k一般低于训练样本数的平方根
1、计算测试对象到训练集中每个对象的距离
2、按照距离的远近排序
3、选取与当前测试对象最近的k的训练对象，作为该测试对象的邻居
4、统计这k个邻居的类别频率
5、k个邻居里频率最高的类别，即为测试对象的类别
输入X可以采用BallTree或KDTree两种数据结构，优化计算效率，可以在实例化KNeighborsClassifier的时候指定。
KDTree
基本思想是，若A点距离B点非常远，B点距离C点非常近， 可知A点与C点很遥远，不需要明确计算它们的距离。 通过这样的方式，近邻搜索的计算成本可以降低为O[DNlog(N)]或更低。 这是对于暴力搜索在大样本数N中表现的显着改善。KD 树的构造非常快，对于低维度 (D<20) 近邻搜索也非常快, 当D增长到很大时，效率变低： 这就是所谓的 “维度灾难” 的一种体现。
KD 树是一个二叉树结构，它沿着数据轴递归地划分参数空间，将其划分为嵌入数据点的嵌套的各向异性区域。 KD 树的构造非常快：因为只需沿数据轴执行分区, 无需计算D-dimensional 距离。 一旦构建完成, 查询点的最近邻距离计算复杂度仅为O[log(N)]。 虽然 KD 树的方法对于低维度 (D<20) 近邻搜索非常快, 当D增长到很大时, 效率变低。
KD树的特性适合使用欧氏距离。
BallTree
BallTree解决了KDTree在高维上效率低下的问题，这种方法构建的树要比 KD 树消耗更多的时间，但是这种数据结构对于高结构化的数据是非常有效的， 即使在高维度上也是一样。
KD树是依次对K维坐标轴，以中值切分构造的树；ball tree 是以质心C和半径r分割样本空间，每一个节点是一个超球体。换句简单的话来说，对于目标空间(q, r)，所有被该超球体截断的子超球体内的所有子空间都将被遍历搜索。
BallTree通过使用三角不等式减少近邻搜索的候选点数:|x+y|<=|x|+|y|通过这种设置, 测试点和质心之间的单一距离计算足以确定距节点内所有点的距离的下限和上限. 由于 ball 树节点的球形几何, 它在高维度上的性能超出 KD-tree, 尽管实际的性能高度依赖于训练数据的结构。
BallTree适用于更一般的距离。
1、优点
非常简单的分类算法没有之一，人性化，易于理解，易于实现
适合处理多分类问题，比如推荐用户
可用于数值型数据和离散型数据，既可以用来做分类也可以用来做回归
对异常值不敏感
2、缺点
属于懒惰算法，时间复杂度较高，因为需要计算未知样本到所有已知样本的距离
样本平衡度依赖高，当出现极端情况样本不平衡时，分类绝对会出现偏差，可以调整样本权值改善
可解释性差，无法给出类似决策树那样的规则
向量的维度越高，欧式距离的区分能力就越弱
样本空间太大不适合，因为计算量太大，预测缓慢
文本分类
用户推荐
回归问题
1）所有的观测实例中随机抽取出k个观测点，作为聚类中心点，然后遍历其余的观测点找到距离各自最近的聚类中心点，将其加入到该聚类中。这样，我们就有了一个初始的聚类结果，这是一次迭代的过程。
2）我们每个聚类中心都至少有一个观测实例，这样，我们可以求出每个聚类的中心点（means），作为新的聚类中心，然后再遍历所有的观测点，找到距离其最近的中心点，加入到该聚类中。然后继续运行2）。
3）如此往复2），直到前后两次迭代得到的聚类中心点一模一样。
本算法的时间复杂度：O(tkmn)，其中，t为迭代次数，k为簇的数目，m为记录数，n为维数；
空间复杂度：O((m+k)n)，其中，k为簇的数目，m为记录数，n为维数。
适用范围：
K-menas算法试图找到使平凡误差准则函数最小的簇。当潜在的簇形状是凸面的，簇与簇之间区别较明显，且簇大小相近时，其聚类结果较理想。前面提到，该算法时间复杂度为O(tkmn)，与样本数量线性相关，所以，对于处理大数据集合，该算法非常高效，且伸缩性较好。但该算法除了要事先确定簇数K和对初始聚类中心敏感外，经常以局部最优结束，同时对“噪声”和孤立点敏感，并且该方法不适于发现非凸面形状的簇或大小差别很大的簇。
1）首先，算法只能找到局部最优的聚类，而不是全局最优的聚类。而且算法的结果非常依赖于初始随机选择的聚类中心的位置。我们通过多次运行算法，使用不同的随机生成的聚类中心点运行算法，然后对各自结果C通过evaluate(C)函数进行评估，选择多次结果中evaluate(C)值最小的那一个。k-means++算法选择初始seeds的基本思想就是：初始的聚类中心之间的相互距离要尽可能的远
2）关于初始k值选择的问题。首先的想法是，从一个起始值开始，到一个最大值，每一个值运行k-means算法聚类，通过一个评价函数计算出最好的一次聚类结果，这个k就是最优的k。我们首先想到了上面用到的evaluate(C)。然而，k越大，聚类中心越多，显然每个观测点距离其中心的距离的平方和会越小，这在实践中也得到了验证。第四节中的实验结果分析中将详细讨论这个问题。
3）关于性能问题。原始的算法，每一次迭代都要计算每一个观测点与所有聚类中心的距离。有没有方法能够提高效率呢？是有的，可以使用k-d tree或者ball tree这种数据结构来提高算法的效率。特定条件下，对于一定区域内的观测点，无需遍历每一个观测点，就可以把这个区域内所有的点放到距离最近的一个聚类中去。这将在第三节中详细地介绍。
相似点：都包含这样的过程，给定一个点，在数据集中找离它最近的点。即二者都用到了NN(Nears Neighbor)算法，一般用KD树来实现NN。
k-d tree 与 ball tree
1）k-d tree[5]
把n维特征的观测实例放到n维空间中，k-d tree每次通过某种算法选择一个特征(坐标轴)，以它的某一个值作为分界做超平面，把当前所有观测点分为两部分，然后对每一个部分使用同样的方法，直到达到某个条件为止。
上面的表述中，有几个地方下面将会详细说明：（1）选择特征（坐标轴）的方法 （2）以该特征的哪一个为界 （3）达到什么条件算法结束。
(1)选择特征的方法
计算当前观测点集合中每个特征的方差，选择方差最大的一个特征，然后画一个垂直于这个特征的超平面将所有观测点分为两个集合。
（2)以该特征的哪一个值为界 即垂直选择坐标轴的超平面的具体位置。
第一种是以各个点的方差的中值（median）为界。这样会使建好的树非常地平衡，会均匀地分开一个集合。这样做的问题是，如果点的分布非常不好地偏斜的，选择中值会造成连续相同方向的分割，形成细长的超矩形(hyperrectangles)。
替代的方法是计算这些点该坐标轴的平均值，选择距离这个平均值最近的点作为超平面与这个坐标轴的交点。这样这个树不会完美地平衡，但区域会倾向于正方地被划分，连续的分割更有可能在不同方向上发生。
（3）达到什么条件算法结束
实际中，不用指导叶子结点只包含两个点时才结束算法。你可以设定一个预先设定的最小值，当这个最小值达到时结束算法。
图6中，星号标注的是目标点，我们在k-d tree中找到这个点所处的区域后，依次计算此区域包含的点的距离，找出最近的一个点（黑色点），如果在其他region中还包含更近的点则一定在以这两个点为半径的圆中。假设这个圆如图中所示包含其他区域。先看这个区域兄弟结点对应区域，与圆不重叠；再看其双亲结点的兄弟结点对应区域。从它的子结点对应区域中寻找（图中确实与这个双亲结点的兄弟结点的子结点对应区域重叠了）。在其中找是否有更近的结点。
k-d tree的优势是可以递增更新。新的观测点可以不断地加入进来。找到新观测点应该在的区域，如果它是空的，就把它添加进去，否则，沿着最长的边分割这个区域来保持接近正方形的性质。这样会破坏树的平衡性，同时让区域不利于找最近邻。我们可以当树的深度到达一定值时重建这棵树。
然而，k-d tree也有问题。矩形并不是用到这里最好的方式。偏斜的数据集会造成我们想要保持树的平衡与保持区域的正方形特性的冲突。另外，矩形甚至是正方形并不是用在这里最完美的形状，由于它的角。如果图6中的圆再大一些，即黑点距离目标点点再远一些，圆就会与左上角的矩形相交，需要多检查一个区域的点，而且那个区域是当前区域双亲结点的兄弟结点的子结点。
为了解决上面的问题，我们引入了ball tree。
2）ball tree[4]
解决上面问题的方案就是使用超球面而不是超矩形划分区域。使用球面可能会造成球面间的重叠，但却没有关系。ball tree就是一个k维超球面来覆盖这些观测点，把它们放到树里面。图7（a)显示了一个2维平面包含16个观测实例的图,图7（b）是其对应的ball tree，其中结点中的数字表示包含的观测点数。
不同层次的圆被用不同的风格画出。树中的每个结点对应一个圆，结点的数字表示该区域保含的观测点数，但不一定就是图中该区域囊括的点数，因为有重叠的情况，并且一个观测点只能属于一个区域。实际的ball tree的结点保存圆心和半径。叶子结点保存它包含的观测点。
使用ball tree时，先自上而下找到包含target的叶子结点，从此结点中找到离它最近的观测点。这个距离就是最近邻的距离的上界。检查它的兄弟结点中是否包含比这个上界更小的观测点。方法是：如果目标点距离兄弟结点的圆心的距离大于这个圆的圆心加上前面的上界的值，则这个兄弟结点不可能包含所要的观测点。（如图8）否则，检查这个兄弟结点是否包含符合条件的观测点。
那么，ball tree的分割算法是什么呢？
选择一个距离当前圆心最远的观测点i1，和距离i1最远的观测点 i2，将圆中所有离这两个点最近的观测点都赋给这两个簇的中心，然后计算每一个簇的中心点和包含所有其所属观测点的最小半径。对包含n个观测点的超圆进行分割，只需要线性的时间。
与k-d tree一样，如果结点包含的观测点到达了预先设定的最小值，这个顶点就可以不再分割了。
㈣ Matlab超像素图像分割【源码 详细解析】
超像素图像分割是一种将像素级图像抽象为区域级图像的技术。它通过将位置相邻且具有相似颜色、亮度、纹理等特征的像素点组成的小区域进行聚合，形成更具有代表性的大元素。这种新元素将作为图像处理算法的基本单位，有助于降低图像处理的复杂度并剔除异常像素点。理论上，任何过度分割算法都能生成超像素。在图像分割中，超像素是指具有相似纹理、颜色、亮度特征的相邻相似构成的不规则像素块。它通过利用像素之间的特征相似性将像素分组，用较少的超像素代替大量像素，有效地表达图像特征。
超像素的判别条件包括Undersegmentation Error、Boundary Recall和Compactness score。Undersegmentation Error评估超像素区域的覆盖程度，Boundary Recall衡量超像素边界对图像物体边界的覆盖能力，而Compactness score则衡量超像素是否紧密。
超像素的初始化方法主要有种子像素初始化和矩形区域初始化。SLIC算法是简单线性迭代聚类算法，采用CIELAB颜色空间和XY坐标下的5维特征向量，通过局部聚类过程生成紧凑且均匀的超像素。SEEDS算法则将图像平均分割为矩形区域作为初始超像素。
SLIC算法具有生成紧凑、整齐的超像素、适用于彩色和灰度图像、参数设置少等优点。算法步骤包括初始化种子点、重新选择种子点、为每个像素点分配类别标签以及计算距离度量。其中，距离度量包括颜色距离和空间距离。
超像素图像分割技术在图像处理中扮演着重要角色，通过降低维度并保持物体边界信息，提高了图像处理的效率和准确性。SLIC算法因其在运行速度、生成超像素的紧凑度、轮廓保持方面的优秀表现而广受认可。通过合理设置参数，SLIC算法能够生成满足人们期望的分割效果，成为图像分割领域的有力工具。