Stable initialization scheme for K -means clustering

Though K-means is very popular for general clustering, its performance which generally converges to numerous local minima depends highly on initial cluster centers. In this paper a novel initialization scheme to select initial cluster centers for K-means clustering is proposed. This algorithm is based on reverse nearest neighbor (RNN) search which retrieves all points in a given data set whose nearest neighbor is a given query point. The initial cluster centers computed using this methodology are found to be very close to the desired cluster centers for iterative clustering algorithms. This procedure is applicable to clustering algorithms for continuous data. The application of proposed algorithm to K-means clustering algorithm is demonstrated. Experiment is carried out on several popular datasets and the results show the advantages of the proposed method. Foundation item: Supported by the National Natural Science Foundation of China (60503020, 60503033, 60703086), the Natural Science Foundation of Jiangsu Province (BK2006094), the Opening Foundation of Jiangsu Key Laboratory of Computer Information Processing Technology in Soochow University (KJS0714) and the Research Foundation of Nanjing University of Posts and Telecommunications (NY207052, NY207082)     

改进K-means聚类的自适应加权K近邻指纹定位算法

针对指纹定位精度易受指纹数据K-means聚类预处理效果不佳、加权K近邻算法采用固定K值进行匹配定位精度差等问题,提出一种基于改进K-means聚类的自适应加权K近邻算法.算法在对指纹数据进行聚类计算过程中充分考虑参考点间接收信号强度值与实际物理坐标的双重影响,以避免参考点分类不明确;根据每个测试点的匹配参考点之间实际距离的均值和标准差设置阈值,动态选择K值.实验结果证明,改进K-means聚类的自适应加权K近邻算法相较于传统室内定位算法定位精度提高了44％,可为相关应用提供更精确的定位服务.     

k子凸包分类方法

基于凸包的k局部超平面距离分类方法,通过改进k近邻算法在处理小样本问题时的决策边界而显著提高分类性能.但是,该方法对噪声和类的数目敏感,并且在一类样本"包围"另一类样本时,由于外围类凸包与内部样本的距离为零而导致分类错误.针对上述问题,提出了k子凸包分类方法,该方法融合了k近邻分类和凸包技术的优点,首先寻找测试样本的k近邻,然后在该邻域中计算测试样本到相应类的子凸包的距离,并根据距离大小来确定该测试样本的类别,有效克服了k局部超平面距离分类存在的不足.大量实验表明,文章提出的k子凸包分类方法在分类性能上具有显著的优势.     

无线传感器网络能量平衡的数据汇聚路由算法

传感器的数据在传输过程中按照贪婪算法形成的数据汇聚路径中,有些节点过早地消耗完其能量,造成所谓的热点问题,引起传感器网络能量消耗的不平衡．本研究提出了一种能量平衡的数据汇聚路由算法EBGP协议．该协议依据邻居节点的剩余能量、邻居节点到Sink节点的距离以及邻居节点到源节点的距离来计算概率值,然后选择邻居节点中概率最大的一个作为数据转发节点．仿真显示EBGP协议胜过GPSR、GEAR和D-REECR协议,达到了能量平衡和能量效率的目的．     

基于估计距离的无需测距定位算法

针对无需测距定位算法定位误差大的问题,提出了一种基于估计距离的无需测距定位算法.首先分析了两个邻居节点之间距离和通信范围相交面积之间的关系,得到一个线性函数.线性函数的输出是一个表示两个邻居节点之间距离远近关系的参数,称之为距离参数.然后用距离参数和锚节点之间的距离计算邻居节点之间的估计距离,最后根据估计距离计算未知节点的估计位置.仿真结果表明,该算法在规则区域和不规则区域的定位误差都要低于当前同类型的定位算法.     

基于距离的相似最近邻搜索算法研究

为了提高相似最近邻搜索（ANN）算法的精度,提出了一种在度量空间下基于距离的相似最近邻搜索算法-优化的VP森林（OVF）算法。在传统VP树（VT）算法的基础上,首先采用改进的选择优势点的方法,通过从数据集采样优势点候选集,对其进行评估,选取其中区分度大的点作为优势点;然后提出构建多棵VP树的新方法,改进距离优势点远的子树中最近邻不紧凑问题;接着提出使用优先队列与剪枝搜索方法结合的新搜索方法查找最近邻,减少了很多不必要的距离计算。最后通过实验结果表明,本文方法在数据维度、数据集大小、返回不同邻居个数、不同的距离函数及建树个数方面精度有了很大的提高。     

一种基于局部信息最小二乘法的节点定位算法

针对一些面积较大、节点分布密度过低的实际应用场景中,由于节点间距离测量误差过大而导致定位算法结果精度较低的问题,提出一种根据各邻居节点相关信息划分为若干个局部网络块的节点定位算法.该算法首先将无线传感器网络节点定位技术与机器学习领域中的降维方法相结合;然后根据节点间的距离越近,测量精度越高的规则及在一定通信半径内的各邻居节点相关信息共建网络块;最后将网络块组建成全局坐标系,利用全局构建以及锚节点的具体信息映射出各节点的坐标.仿真实验结果表明,该算法较其他节点定位算法在节点定位精度方面表现更优.     

一种基于网格的最近邻SVM新算法

支持向量机(SVM)算法往往由于分类面过分复杂或过学习而导致其泛化能力降低,现有的最近邻（NNSVM)或K近邻（KNNSVM）方法解决了这类样本问题,但算法时间复杂度高,处理海量样本的能力有限。在NNSVM算法的基础上引入了网格概念,提出了GNNSVM算法,该算法先对空间进行分块,然后在空间块内计算样本距离,找出最近邻,并结合分块序列最小优化算法(SMO)进行了算法实现。实验表明,该方法降低了计算复杂度,它在保持分类精度的同时,提高了训练和分类的速度,并具有较强的泛化能力,从而提高了原NNSVM算法的海量数据处理能力。     

嵌入数据结构信息的单类支持向量机及其线性规划算法

 针对现有基于超平面的单类分类器未同时考虑目标数据全局与局部信息的不足,通过在单类支持向量机One-Class SVM（OCSVM）算法中加入类内散度以反应目标数据的全局信息,提出了结构化单类支持向量机Structured OCSVM（SOCSVM）,不仅使之具有全局与局部化学习的特点,同时也为诸多的SVM算法嵌入数据内在结构这类先验信息提供了统一框架。为进一步提高运算效率,在SOCSVM二次规划求解基础上,通过最小化目标数据均值到超平面的函数距离,提出了线性规划算法,同时也避免了SOCSVM必须以原点作为负类代表的不足。人工和真实数据集上的实验结果验证了嵌入目标数据结构信息的SOCSVM及其线性规划算法的有效性。     

一种改进的毫米波雷达聚类算法

针对毫米波雷达数据均匀性差,数据量小,噪点多等问题,提出一种基于DBSCAN (density-based spatial clustering of applications with noise)的雷达自适应聚类算法.改进算法能够根据K近邻距离和目标反射截面自适应调整聚类半径.首先给出一种聚类半径根据K近邻距离动态调整的机制:目标第K个近邻的距离与阈值相比较,以确定阈值半径取值.再提取雷达提供的目标反射截面,基于该值计算目标假象半径作为聚类半径的补充量.实现根据目标反射截面与数据稀疏程度自适应聚类的效果.将改进算法与不同参数的DBSCAN聚类算法在真实雷达点云数据进行实验对比.相较于选取合适参数的DBSCAN算法,改进算法能够更好适应毫米波雷达点云特征,对行人目标识别准确率提高4.18％,对车辆目标识别准确率提高5.63％.     

并行MapReduce模型下的一种改进型KNN分类算法

大数据时代带来数据处理模式的变革,依托Hadoop分布式编程框架处理大数据问题是当前该领域的研究热点之一。为解决海量数据挖掘中的分类问题,提出基于一种双度量中心索引KNN分类算法。该算法在针对存在类别域的交叉或重叠较多的大数据,先对训练集进行中心点的确定,通过计算分类集与训练集中心点的欧式距离,确定最相似的3个类别,然后以余弦距离为度量,通过索引选择找出K个近邻点,经过MapReduce编程框架对KNN并行计算加以实现。最后在UCI数据库进行比较验证,结果表明提出的并行化改进算法在准确率略有提高的基础上,运算效率得到了极大提高。     

空间调制系统中一种低复杂度比特映射算法

空间调制(spatial modulation,SM)通过激活发射天线的索引在空间域中传输信息比特,将比特到符号映射技术引入到SM系统中,可以提高SM系统的性能.一般而言,在判决准确率一定的情况下,采用相邻SM符号汉明距离较小的映射方式将获得较优的系统性能.提出一种低复杂度的比特到符号映射算法,称为符号最近法(symbol nearest method,SNM).该算法从具有最小距离的符号对开始对SM符号进行排序,寻找下一个最近的SM符号,直到所有SM符号排序结束为止,将格雷编码的比特映射分配给排序后的SM符号.分析和仿真结果表明,SNM算法在发射端使用全信道状态信息(channel state information,CSI)时,其系统性能接近于SM和空间移位键控(space shift keying,SSK)误码率(bit error rate,BER)性能的下界,并且所提出的算法复杂度为O(K2),其复杂度也较低.     

基于权重搜索树改进K近邻的高维分类算法

信息采集技术日益发展导致的高维、大规模数据,给数据挖掘带来了巨大挑战,针对K近邻分类算法在高维数据分类中存在效率低、时间成本高的问题,提出基于权重搜索树改进K近邻(K-nearest neighbor algorithm based on weight search tree,KNN-WST)的高维分类算法,该算法根据特征属性权重的大小,选取部分属性作为结点构建搜索树,通过搜索树将数据集划分为不同的矩阵区域,未知样本需查找搜索树获得最"相似"矩阵区域,仅与矩阵区域中的数据距离度量,从而降低数据规模,以减少时间复杂度.并研究和讨论最适合高维数据距离度量的闵式距离.6个标准高维数据仿真实验表明,KNN-WST算法对比K近邻分类算法、决策树和支持向量机(support vector machine,SVM)算法,分类时间显著减少,同时分类准确率也优于其他算法,具有更好的性能,有望为解决高维数据相关问题提供一定参考.     

用于动态心电图波形分类改进的K近邻算法研究

针对动态心电图波形数据量大且具有明显个体差异性的特点,提出了一种改进的K近邻分类算法,用于动态心电图波形分类.该算法首先将实例间的度量改为曼哈顿距离（City Block Distance）,然后引入高斯核函数,将K近邻算法改进为非线性分类算法,以达到分类动态心电图波形的目的.实验结果表明,该算法在对动态心电图波形进行分类时,分类精度在90%以上.     

一种新的相似度标准及其相关的聚类算法

分析了CHAMELEON聚类算法的不足,定义一种基于k最临近集和共享k最临近集的相似度函数,在此基础上提出了一种结合分类算法的新聚类算法,经过对模拟的复杂数据组和KDD Cup'99网络非法入侵数据的实验,证明该算法能有效的对由大量噪音和不同形状、大小及密度的类组成的高维数据进行聚类.     

基于连接的频繁集聚类算法

针对大型事务数据库中频繁集的多属性聚类问题,提出一种高效的频繁集聚类算法.以往聚类算法采用基于距离的计算方法,由于受到属性数据的制约,在频繁集挖掘中具有一定的限制.在属性聚类基础上,基于连接对频繁集进行聚类.在算法中先找出数据点的邻居和计算相似度,构造邻居矩阵;然后计算连接数目,确定邻居数目矩阵;最后通过设置判定函数和阈值确定聚类数.通过实验证明,算法能够不仅能有效地完成频繁集的多属性聚类问题,而且还可以进一步发现频繁集在某一层次的相关性.     

改进的K-近邻算法及其在学习预警中的应用

随着大数据在教育中的作用日益凸显,大量的数据被应用到教学研究、教学评估和行为预测.学生的成绩、行为记录、与老师的互动记录等教育数据,都已经开始发挥价值.为了解决课程的低通过率问题,将改进的K-近邻算法应用到学习预警中,首先利用网格搜索和交叉验证相结合的方法对模型参数进行优选,其次在构建决策树过程中,利用基尼增益确定特征的权重系数并且根据权重系数进行特征选择,在计算距离时引入权重系数,使每个特征收到权重系数的约束.实验表明,在一个公开的数据集和一个真实的数据集上,改进后的K-近邻算法显著优于传统的K-NN.     

基于RGB空间的非经典K最近邻算法应用研究

为迅速、准确、无过多人工干预的进行图像分割,提出了一种K最近邻算聚类方法并将其应用于图像处理。与经典K最近邻算法在样本库中寻找最近邻点不同,该算法在待分割图像的RGB空间中寻找每一个像素点的K个最近邻点,参考所有像素点同最近邻点之间的平均距离,引入聚类阈值并对像素点的归属进行判断。对火焰图像的分割实验结果表明,在分割精度相接近的情况下,该算法的分割速度要快于其它几种常见算法。     

Neighborhood topological effect on grain topology-size relationship in three-dimensional polycrystalline microstructures

A new grain topology-size relationship in three-dimensional(3D)polycrystalline microstructures has recently been established by considering the effects of non-random first nearest neighbor grains.In this contribution,a generalized form for this relationship is presented by considering the interactions of kth(k=1,2,3…)nearest neighbor grains,and large scale Monte Carlo-Potts model simulation is used to investigate the general neighborhood topological effect on the topology-size relationship.The results show that,unlike their first nearest neighbors(k=1),the topological correlations of 3D grains with their kth layers(k 2)of nearest-neighbors may have trivial effect on the topology-size relationship.     

山区小流域洪水预报实时校正研究

为了解决现有实时校正方法对山区小流域洪水进行校正能力不足的问题,引入K最近邻算法用于洪水预报实时校正。以安徽省沙埠流域为试验流域,构建基于K最近邻算法的实时校正模型,同时采用BP神经网络实时校正法和传统的误差自回归方法,以洪峰相对误差和确定性系数为评价指标,分析各校正模型的校正结果。结果表明:基于K最近邻的实时校正法对确定性系数改善最优,BP神经网络实时校正法对洪峰误差校正更精确;将历史洪水资料纳入学习样本后,基于K最近邻的实时校正法的校正能力将进一步提升。基于K最近邻的实时校正法能够有效避免误差自回归方法对洪峰误差控制较差的缺陷,适应性强,反应灵敏,精确度高,可作为山区小流域洪水预报实时校正的有效工具。