一种高效的基于初始聚类中心优化的K-means算法

为解决传统K-means算法初始质心的随机选取以及聚类过程中每个数据样本到聚类中心距离的重复计算问题,提出了一种高效的基于初始聚类中心优化的K-means算法,采用最小方差优化初始质心,通过存储每次迭代中所有数据点的簇标志和到最近聚类中心的距离并用于下一次迭代,避免了重复计算数据点到每个中心的距离。在UCI数据库中五个不同的数据集上进行了测试,对各个算法在聚类准则函数,运行时间以及迭代次数上进行实验结果比较,表明在不降低聚类性能的前提下,减少了迭代次数,缩短了聚类时间,证明了改进算法的有效性和高效性。     

两级参考点匹配位置指纹声源定位方法

提出一种两级参考点（RPs）匹配方法来减少位置指纹声源定位（SSL）过程中临近参考点搜索的计算量. 离线采样阶段：通过K均值聚类算法将数据库划分为一定数目的子库,并采用一种距离检测方法对离群点进行剔除. 在线定位阶段：通过第一级临近子库匹配完成对参考点搜索范围的缩减;在临近子库内进行第二级参考点匹配得到临近参考点;完成声源目标（TP）定位. 实验结果表明,采用两级参考点匹配算法可以在保证定位精度的前提下有效提高位置指纹声源定位方法的定位效率.     

基于模拟退火聚类的室内定位算法

针对大型室内场景下现有指纹定位算法运算复杂度高、定位精度低的问题,提出一种基于模拟退火聚类的室内定位算法。该算法采用模拟退火聚类的方法完成对指纹空间的聚类和划分,有效降低了指纹匹配所需的候选指纹数量,并消除了具有一定特征相似性的奇异点,从而降低了运算复杂度,提高了定位精度。实验结果表明,该算法可计算出定位环境下指纹空间的最优聚类数从而确保定位精度,较K 均值聚类定位算法和KNN算法定位精度高,且定位精度不受初始值影响。     

一种高效的全局K-均值算法

针对全局K-均值算法时间复杂度大的问题,提出一种增量选择初始聚类中心的新方法。选择数据集中周围分布最密集的样本作为第一个初始聚类中心,选择最小化目标函数贡献大,并且和已有聚类中心距离远的样本作为下一个初始聚类中心。改进算法减少了增量选取初始聚类中心时的计算量,降低了时间复杂度。实验证明,改进算法与全局K-均值算法、快速全局K-均值算法相比,在不影响聚类效果的基础上,减少了聚类时间,与优化初始聚类中心的算法相比,聚类效果更优。     

基于混沌理论的SCCPM联合迭代解调译码算法

针对DVB-RCS2下行链路物理层中定义的串行级联连续相位调制信号迭代检测中存在的系统复杂度高、低信噪比条件下收敛性较差的问题,从匹配滤波器组和迭代译码两方面对系统进行改进,提出了一种基于混沌理论的联合迭代解调译码算法。该算法利用修正高斯小波结合延迟反馈控制法,有效抑制了迭代译码中暂态混沌对系统性能的影响,改善了系统在低信噪比条件下的收敛性,同时减少了迭代译码的次数;为了进一步解决计算迭代译码中的码字先验信息需要大量匹配滤波器的问题,该算法使用截断小特征值法对匹配滤波器组进行化简,在实际应用中仅使用4个匹配滤波器即可满足要求。仿真结果表明,本文所提算法与传统算法相比,可以有效的降低系统复杂度,同时具有良好的迭代收敛性。     

基于薛定谔方程的K-Means聚类算法

提出一种基于薛定谔方程的K-Means聚类算法,利用量子力学中薛定谔方程的势能函数来确定初始聚类中心。计算每个数据样本所对应的势能函数值,将势能函数值小的数据样本放入初始聚类中心集合,设置一个距离阈值,数据集合中的数据样本和初始聚类中心集合中的数据样本进行相异度计算,将相异度大于阈值的数据样本放入初始聚类中心集合,重复这一操作,直到初始聚类中心集合中的样本数量等于K为止。试验结果表明,采用该方法能很好地筛选出初始聚类中心,得到更高的聚类结果准确率和较少的迭代次数,与其他几种方法相比,聚类结果准确率平均提高约12%,同时迭代次数减少约3次。     

基于室内地图环境信息的多楼层WiFi定位技术研究

针对多楼层环境的室内定位需求,提出了一种基于地图环境先验信息的WiFi指纹定位方法。首先在离线阶段建立地图环境信息模型并对指纹进行仿射传播聚类,然后在线阶段采用RSSI阈值的楼层判别算法确定楼层,并结合地图信息模型和最大后验估计方法计算出终端位置。实验结果表明,相比于传统的指纹定位方法,室内定位技术不仅能提高定位精度,并且降低了在线阶段指纹匹配计算的复杂度。     

一种快速全局中心模糊聚类方法

针对模糊C均值算法对初始中心敏感、容易陷入局部最优解,且算法迭代速度慢等问题,依据模糊聚类的全局中心理论,建立了一种快速全局中心模糊聚类系统模型,并给出了相关理论分析和算法流程。该模型通过DKC值方案对各数据成员进行密集度分析来确定初始质心,并结合AM度量提出自定义寻优函数,依据该函数在算法运行的每一个阶段来逐一动态增加聚类中心,直至算法收敛。通过实验对比和验证,该过程降低了随机选取聚类中心对聚类结果的影响,跳出局部最优解,减少计算量,具有更高的聚类精度和更快的收敛速度。     

一种改进的快速FCM图像分割算法

FCM算法对图像的模糊特征具有较强的鲁棒性,在图像分割方面得到了广泛应用。但FCM算法采用随机初始化聚类中心的方法,使算法在迭代次数上有一定的不确定性。为提高FCM算法的运算效率,提出一种基于确定初始聚类中心的快速FCM图像分割算法。用最大类间方差法多次划分图像的灰度区间,根据区间中像素点的灰度值来初始化聚类中心,以使其尽可能的接近最终分割的聚类中心,减少算法的迭代次数。实验结果表明,与传统的FCM算法相比较,改进后的算法可以通过较少的迭代次数及运算时间分割图像。且该算法可以应用于诸多采取随机初始化聚类中心的FCM相关的算法中,以提高算法的运算效率。     

一种改进的室内指纹定位算法

针对指纹定位算法在建立离线指纹库时需要部署较多参考节点(RP)的问题,提出一种分区拟合近似算法(PFAM)。为减少指纹定位算法在离线阶段的工作量,对整个目标环境进行分区,并在每个分区内重新部署虚拟RP;采用三阶多项式对数距离路径损耗模型拟合得到每个分区的环境系数,并建立每个分区的误差向量;利用拟合模型和误差向量逆推得到虚拟RP的信号强度,并采用C均值聚类算法对离线指纹库聚类来减少在线阶段的计算量;在在线阶段采用加权K近邻算法(WKNN)对目标进行定位。实验结果表明,在RP部署较少的条件下,PFAM算法依然能达到较高的定位精度,平均定位误差约为1.2 m。累积分布函数(CDF)分析结果表明,有86%的定位误差分布在2 m以内。     

FCM聚类算法的改进

模糊C均值（FCM）算法广泛地应用于模式识别、图像分割等领域。根据FCM算法存在对初始解敏感且迭代过程中计算量大的问题,本文提出了一种改进的算法：先通过精简数据集,减少算法迭代的时间;再使用密度函数法得到FCM算法的初始聚类中心,以减少FCM算法收敛所需的迭代次数。实验结果表明,改进后的算法较好地解决了类中心的初值化问题,提高了算法的收敛速度和运行效率。     

一个基于特征点匹配的联机指纹鉴别系统

描述了一个基于特征点匹配的联机指纹验证系统设计思想和实现方法，专用的CCD指纹采集设备通过自动跟踪二值化电路，可向处理软件提供高质量的二值图像。专门设计的一种两遍扫描串行迭代细化算法可以获得高质量的指纹的骨架。设计了一种新方法在细化后的点线图上计算指纹的中心点。特征点匹配算法通过动态建立极坐标系和弹性配对特征点来实现。预先计算出的中心点可使搜索范围大大减少，确保了本算法满足联机自动指纹验证系统的实时性要求。     

一种查找算法的改进方法

折半查找算法是数据结构中有序序列查找中的一个重要算法,此算法在含有n个元素的有序序列中查找某一个元素时,最大循环比较次数为「log2n」 1.但是在很多情况下,查找之前有序序列分布的很多信息为已知,如当知道了有序序列中每相邻2个元素之差最大值的一个上界,就可以有比折半法更加有效的查找算法.以此改进的折半法查找性能明显优于原算法的查找.受序列分布的影响,其在最坏情况下查找一个元素的最大比较次数在1和「log2n」 1之间,明显优于折半查找.此方法在实际应用中可极大提高查找效率.     

一种基于MapReduce的改进k-means聚类算法研究

传统k-means算法的聚类中心需要经过多次迭代运算才能最终稳定,而MapReduce计算框架下的k-means聚类算法在处理迭代运算时效率并不理想.针对上述问题,提出一种新的基于MapReduce的k-means聚类算法.该算法对传统k-means算法进行了改进,通过将k-means聚类问题转化为Map和Reduce两阶段的k-means++算法聚类问题,并将权值概念和单通道技术引入到传统k-means++算法中,提升了算法在MapReduce框架中的执行效率.实验分析表明,该方法较之传统方法具有更好的加速比和可扩展性.     

动态分数选择的多视角非接触指纹识别融合

与传统的二维指纹采集方式相比,非接触的指纹采集方式可以提供更丰富的特征,并能克服二维采集方式某些不足．基于多视角非接触指纹识别融合问题,提出了基于聚类的动态分数选择(CDSS)算法．首先,通过聚类将匹配分数分为两类,分别计算两类中匹配分数的个数以及其他统计量,然后通过参数的判断选择相应的统计量作为整个系统最终用于决策的匹配分数．实验表明:相比单视角非接触二维指纹识别,基于CDSS的多视角非接触指纹识别的识别性能有显著提高．与sum、max、SVM和Fisher线性判别算法等的实验比较也验证了CDSS在多视角非接触指纹识别融合方面的优越性．     

ISODATA聚类在指纹图像分割中的应用

针对指纹图像的特点,研究了传统的指纹分割方法和形态学图像处理方法,将迭代自组织分析算法（ISODATA聚类）应用到指纹图像分割中.首先根据指纹图像块灰度均值、块标准偏差、块灰度对比度和块方向一致性,使用聚类方法划出图像的部分背景块;然后将背景块灰度用背景处灰度平均值代替,使用形态学图像处理方法实现指纹图像的分割.对FVC（国际指纹识别竞赛）指纹库中不同质量的指纹图像进行了测试.结果表明,此算法比传统算法更有效.     

改进的AP聚类算法研究

AP聚类算法是Frey和Dueck在2007年提出的一个先进的聚类方法.该算法具有较传统聚类算法更好的聚类性能,已被成功地应用于计算机科学的研究领域.为了获得高质量的聚类集,原始AP算法的迭代是在全部数据点之间交流信息,直到收敛.由于这种算法在计算数据时需要占用二次CPU时间,不适用于大规模的数据集,因此,本文在AP算法的基础上提出了一种有效的聚类算法.该算法在迭代时可修剪不必要的信息,且在计算消息收敛的同时确定迭代集群,并对算法进行了实验,证明算法是有效的.     

量子k-means算法

为提高经典k-means算法的计算效率,引入量子计算理论得到量子k-means算法。先将聚类数据和k个聚类中心制备成量子态,并行计算其相似度,接着利用相位估计算法将相似度信息保存到量子比特中,然后利用最小值查找量子算法查找最相似的聚类中心点。对比两种算法的复杂度可知,在一定条件下,相对经典算法而言,量子k-means算法的时间复杂度降低,空间复杂度得到指数级降低。     

离散度WKNN位置指纹Wi-Fi定位算法

为改善加权K近邻位置指纹定位算法在室内环境复杂时的定位性能,提出一种以位置指纹离散度作为权值参考的改进加权K近邻位置指纹定位算法.算法在离线位置指纹数据库建立阶段采用K-means聚类算法对位置指纹进行聚类,来降低搜索位置指纹库的计算量.从离线位置指纹库中选取K个与在线实测Wi-Fi信号强度信息最相似的位置指纹,比较其离散程度,将离散程度小的位置指纹赋予较高的加权系数,以减小原加权K近邻算法在室内复杂环境信号强度随距离变化较大情况下带来的位置估算误差.对离散度加权K近邻算法时间复杂度的分析表明,其计算量小于原加权K近邻算法;实际环境实验结果表明,离散度加权K近邻算法具有更高的定位精度,且定位误差波动较小.     

低消耗免查找表CORDIC算法

为减少传统流水线型CORDIC(Coordinate Rotation Digital Computer)算法的硬件资源消耗和输出时延,在包含查找表的三阶段CORDIC算法实现基础上,提出一种免去查找表环节的CORDIC算法实现方法.提出的改进算法直接使用四次移位相加的迭代运算替换查找表结构从而显著降低寄存器消耗,同时通过合并迭代降低迭代次数进而有效减少最大输出时延,并综合运用角度二极化重编码(Binary To Bipolar Recoding,BBR)方法和角度区间折叠技术保证了输出精度.使用Verilog HDL语言在ISE14.2软件平台上对三种算法进行具体实现,利用XST工具对其进行综合,并通过MATLAB建模计算得到算法的正余弦值输出误差.仿真实验结果表明:在输出位宽均设置为16位的情况下,免查找表CORDIC算法能够有效地输出正余弦值;与传统流水线型算法相比,免查找表算法的寄存器资源消耗减少大约74.42%,计算所需的时钟周期降低68.75%,其输出精度也有明显改善;与三阶段算法相比,免查找表算法的寄存器消耗减少大约43.3%.本文提出的免查找表CORDIC算法具有实时性强、输出精度高、硬件资源消耗少等优势,更适用于高速实时的现代数字通信系统应用.