基于核密度估计的K-CFSFDP聚类算法

快速搜索和发现密度峰值的聚类算法(Clustering by Fast Search and Find of Density Peaks,CFSFDP)是一种新的基于密度的聚类算法,它通过发现密度峰值来有效地识别类簇中心,具有聚类速度快、实现简单等优点。针对CFSFDP算法的准确性依赖于数据集的密度估计和截断距离(dc)的人为选择问题,提出一种基于核密度估计的K-CFSFDP算法。该算法利用无参的核密度估计分析数据点的分布特征并自适应地选取dc,从而搜索和发现数据点的密度峰值,并以峰值点数据作为初始聚类中心。基于4个典型数据集的仿真结果表明,K-CFSFDP算法比CFSFDP,K-means和DBSCAN算法具有更高的准确度和更强的鲁棒性。     

基于非参数核密度估计的密度峰值聚类算法*

针对密度峰值聚类算法CFSFDP(Clustering by fast search and find of density peaks)计算密度时人为判断截断距离和人工截取簇类中心的缺陷,提出了一种基于非参数核密度估计的密度峰值的聚类算法。首先,应用非参数核密度估计方法计算数据点的局部密度;其次,根据排序图采用簇中心点自动选择策略确定潜在簇类中心点,将其余数据点归并到相应的簇类中心;最后,依据簇类间的合并准则,对邻近相似子簇进行合并,并根据边界密度识别噪声点,得到聚类结果。在人工测试数据集和UCI真实数据集上的实验表明,新算法较之原CFSFDP算法,不仅有效避免了人为判断截断距离和截取簇类中心的主观因素,而且可以取得更高的准确度。     

核密度估计及其在聚类算法构造中的应用

经典数理统计学中的核密度估计理论是构造基于数据集密度函数聚类算法的理论基础,采用分箱近似的快速核密度函数估计方法同样为构造高效的聚类算法提供了依据．通过对核密度估计理论及其快速分箱核近似方法的讨论,给出分箱近似密度估计相对于核密度估计的均方误差界,提出基于网格数据重心的分箱核近似方法．在不改变计算复杂度的条件下,基于网格数据重心的分箱核近似密度函数计算可以有效地降低近似误差,这一思想方法对于构造高效大规模数据聚类分析算法具有指导意义．揭示了基于网格上密度函数近似的聚类算法与核密度估计理论之间的关系．     

弹性核子空间聚类*

现有子空间聚类算法通常假设数据来自多个线性子空间,无法处理时间序列聚类中存在的非线性和时间轴弯曲问题.为了克服这些局限,通过引入核技巧和弹性距离,提出弹性核低秩表示子空间聚类和弹性核最小二乘回归子空间聚类,统称为弹性核子空间聚类,并从理论上证明弹性核最小二乘回归子空间算法的组效应和弹性核低秩表示子空间聚类算法的收敛性.在5个UCR时间序列数据集上的实验表明本文算法的有效性.     

类属型数据核子空间聚类算法

现有的类属型数据子空间聚类方法大多基于特征间相互独立假设,未考虑属性间存在的线性或非线性相关性.提出一种类属型数据核子空间聚类方法.首先引入原作用于连续型数据的核函数将类属型数据投影到核空间,定义了核空间中特征加权的类属型数据相似性度量.其次,基于该度量推导了类属型数据核子空间聚类目标函数,并提出一种高效求解该目标函数的优化方法.最后,定义了一种类属型数据核子空间聚类算法.该算法不仅在非线性空间中考虑了属性间的关系,而且在聚类过程中赋予每个属性衡量其与簇类相关程度的特征权重,实现了类属型属性的嵌入式特征选择.还定义了一个聚类有效性指标,以评价类属型数据聚类结果的质量.在合成数据和实际数据集上的实验结果表明,与现有子空间聚类算法相比,核子空间聚类算法可以发掘类属型属性间的非线性关系,并有效提高了聚类结果的质量.     

基于成对约束的交叉熵半监督聚类算法*

极大熵聚类(MEC)目标函数中缺乏成对约束的有效信息表达,在拥有少量成对约束的情况下,可能导致有效监督信息的浪费.在MEC的基础上,文中提出基于成对约束的交叉熵半监督聚类算法.利用样本交叉熵表达成对约束信息,并作为惩罚项引入至MEC的目标函数中,通过拉格朗日最优化处理目标函数,得出聚类中心与隶属度的迭代公式.实验表明,文中算法能有效利用少量的成对约束监督信息提高聚类性能,在实际数据应用中性能较好     

类属数据的贝叶斯聚类算法

针对类属型数据聚类中对象间距离函数定义的困难问题,提出一种基于贝叶斯概率估计的类属数据聚类算法。首先,提出一种属性加权的概率模型,在这个模型中每个类属属性被赋予一个反映其重要性的权重;其次,经过贝叶斯公式的变换,定义了基于最大似然估计的聚类优化目标函数,并提出了一种基于划分的聚类算法,该算法不再依赖于对象间的距离,而是根据对象与数据集划分间的加权似然进行聚类;第三,推导了计算属性权重的表达式,得出了类属型属性权重与其符号分布的信息熵成反比的结论。在实际数据和合成数据集上进行了实验,结果表明,与基于距离的现有聚类算法相比,所提算法提高了聚类精度,特别是在生物信息学数据上取得了5%~48%的提升幅度,并可以获得有实际意义的属性加权结果。     

快速核密度估计定理和大规模图论松弛聚类方法

首先证明了快速核密度估计 (Fast kernel density estimate, FKDE) 定理: 基于抽样子集的高斯核密度估计(KDE)与原数据集的KDE间的误差与抽样容量和核参数相关, 而与总样本容量无关. 接着本文揭示了基于高斯核形式的图论松弛聚类(Graph-based relaxed clustering, GRC)算法的目标表达式可分解成“Parzen窗加权和 + 平方熵”的形式, 即此时GRC可视作一个核密度估计问题, 这样基于KDE近似策略, 本文提出了大规模图论松弛聚类方法(Scaling up GRC by KDE approximation, SUGRC-KDEA). 较之先前的工作, 这一方法的优势在于为GRC作用于大规模数据集提供了更简单和易于实现的方案.     

基于概率模型的重叠子空间聚类算法*

针对现有子空间聚类方法处理类簇间存在重叠时聚类准确率较低的问题,文中提出基于概率模型的重叠子空间聚类算法.首先采用混合范数的子空间表示方法将高维数据分割为若干个子空间.然后使用服从指数族分布的概率模型判断子空间内数据的重叠部分,并将数据分配到正确的子空间内,进而得到聚类结果,在参数估计时利用交替最大化方法确定函数最优解.在人造数据集和UCI数据集上的测试实验表明,文中算法具有良好的聚类性能,适用于较大规模的数据集.     

基于空间结构的符号数据仿射传播算法*

由于符号型数据缺乏清晰的空间结构,很难构造一种合理的相似性度量,从而使诸多数值型聚类算法难以推广至符号型数据聚类.基于此种情况,文中引入一种空间结构表示方法,把符号型数据转化为数值型数据,能够在保持原符号型数据的结构特征的基础上重新构造样本之间的相似度.基于此方法,将仿射传播(AP)聚类算法迁移至符号数据聚类中,提出基于空间结构的符号数据AP算法(SBAP).在UCI数据集中若干符号型数据集上的实验表明,SBAP可以使AP算法有效处理符号型数据聚类问题,并且可以提升算法性能.     

核密度估计在立体匹配中的应用

提出了一种基于核密度估计相似性测度的立体匹配方法。将匹配基元中对应像素点的颜色差值在差值特征空间中进行核密度估计,并以此作为相似性测度。在此基础上建立全局能量函数,并采用改进的置信度传播算法进行视差图的求解。实验结果证明该相似性测度较传统方法有明显的改进。     

基于核密度估计的活动轮廓模型

基于核密度估计的活动轮廓模型如果没有适当的扰动机制,往往不能在弧度突变的边缘上获得较好的收敛结果,且在大噪声环境下鲁棒性较差。针对该问题,提出一个新的代价函数。该函数通过融合边缘映射的曲率信息,改善原算法在突变边缘的收敛效果,降低算法对初始轮廓的依赖。     

基于核密度估计的可变码率视频流量预测算法

为解决实时可变码率(VBR)视频在传输中难以准确预测流量的问题,提出一种变带宽核密度估计算法。该算法以核密度估计算法为基础,针对VBR视频的场景切换特性动态改变各样本点的带宽,加快算法收敛速度。仿真结果表明,与变步长归一化最小均方法相比,该算法能够减少10%左右的预测误差,保证流量预测具有较高的预测精度。     

基于小波密度估计的数据流离群点检测

为能及时发现数据流上的局部离群点,分析数据流已有的离群点挖掘算法,提出基于小波密度估计的离群点检测算法。利用小波密度估计多尺度和多粒度的特点,通过小波概率阈值判断数据流中当前滑动窗口内的数据点是否为离群点,并对数据流中离群点检测过程进行讨论。仿真结果表明,与核密度估计算法相比,该算法的检测效率与精度较高。     

基于密度峰值和网格的自动选定聚类中心算法

针对快速搜索和发现密度峰值的聚类算法(DPC)中数据点之间计算复杂,最终聚类的中心个数需要通过决策图手动选取等问题,提出基于密度峰值和网格的自动选定聚类中心的改进算法GADPC。首先结合Clique网格聚类算法的思想,不再针对点对象进行操作,而是将点映射到网格,并将网格作为聚类对象,从而减少了DPC算法中对数据点之间的距离计算和聚类次数;其次通过改进后的聚类中心个数判定准则更精确地自动选定聚类中心个数;最后对网格边缘点和噪声点,采用网格内点对象和相邻网格间的相似度进行了处理。实验通过采用UEF(University of Eastern Finland)提供的数据挖掘使用的人工合成数据集和UCI自然数据集进行对比,其聚类评价指标(Rand Index)表明,改进的算法在计算大数据集时聚类质量不低于DPC和K-means算法,而且提高了DPC算法的处理效率。     

聚类差分图像核密度估计前景目标检测

针对非参数核密度估计学习阶段信息冗余与重复计算,估计阶段的估计错误噪声和计算量大的问题,提出了一种基于聚类分析的差分图像核密度估计前景目标检测算法.该方法在非参数核密度估计的学习阶段基于最大最小聚类原理从原采样全样本中提取那些具有较高频度和多样件的小样本来包含尽可能多的关键样本信息,在估计阶段采用基于自适应阈值的图像差分滤去非典型的运动像素,再利用高斯核密度估计进行运动像素分类.实验结果表明该方法限制了非典型运动像素估计错误产生的噪声,并减少了核密度估计计算量,提高了算法的实时性.     

自适应核密度估计运动检测方法

提出了一种自适应的核密度估计(Kernel density estimation, KDE)运动检测算法. 算法首先提出一种自适应前景、背景阈值的双阈值选择方法, 用于像素分类. 该方法用双阈值克服了单阈值分类存在的不足, 阈值的选择能自适应进行, 且能适应不同的场景. 在此基础上, 本文提出了基于概率的背景更新模型, 按照像素的概率来更新背景, 并利用帧间差分背景模型和KDE分类结果解决背景更新中的死锁问题, 同时检测背景的突然变化. 实验证明了所提出方法的适应性和可靠性.     

基于密度聚类的医学图像分割DCMIS*

为了克服聚类算法对灰度不均匀和有噪声的医学图像分割存在鲁棒性较差等缺点,提出一种基于核密度估计的密度聚类方法分割医学图像.在分析DENCLUE密度聚类算法的思想及爬山策略存在的三个问题的基础上,改进了此密度聚类的爬山策略,并设计了适合于人体组织器官图像分割的DCMIS(Density Clustering based Medical Image Segmentation)算法.该算法先用核密度估计数学模型描述医学图像,然后用改进的爬山算法识别聚类,最后根据聚类分割医学图像.该算法有容忍大量噪声数据等特性.实验结果中的欠分割率、过分割率和错误分割率表明DCMIS比DENCLUE和FCM算法有更好的性能和较好的医学图像分割效能.