基于反向K近邻和密度峰值初始化的加权Kmeans聚类入侵检测算法

传统Kmeans聚类算法的性能易受初始类簇中心随机性和类簇中心计算的迭代过程中边缘点和离群点反复计入的影响,为了避免这些影响,该文提出一种基于反向K近邻和密度峰值初始化的加权Kmeans聚类算法。通过样本的近邻信息计算每个样本的反向K近邻,针对不同规模、不同密度分布数据集,可以自适应地搜索密度峰值点作为初始类簇中心;自适应设定相对簇半径,并通过样本加权进行类簇中心迭代,在不同数据分布下可以有效降低边缘点和离群点对聚类结果的影响。试验结果证明,该算法在聚类性能提升的同时迭代次数大幅降低,随着入侵行为类型和数据规模的增加,该文聚类算法仍体现出较好的性能,且在发现未知攻击类型上效果显著。

路网中连续反向k近邻查询处理

现存的反向k近邻查询方案中,比较高效地研究大多集中在欧式空间,对于路网中的反向k近邻查询的研究相对较少。针对这一问题,考虑路网中移动查询点和移动数据对象的移动性,选用PMR四叉树来索引路网,基于安全区的概念提出一种反向k近邻(RkNN)查询算法,通过监控查询点和移动对象的安全区来处理路网更新。基于"初始化-维护更新"框架,采用Dijkstra搜索策略,设置验证监控区域来判定候选对象解的真假性。为了减少网络搜寻的工作量,提出了一系列剪枝规则来削减搜索空间。实验结果表明,该算法适用于路网中k值不固定的连续RkNN查询。

基于反向K近邻的孤立点检测算法

提出了基于反向K近邻(RKNN)的孤立点检测算法ODRKNN。ODRKNN算法用每个数据点的反向K近邻个数来衡量该数据点的偏离程度,在综合数据集和真实数据集上的实验结果表明,该算法能有效地检测出孤立点,且算法的效率高于算法LOF和LSC的效率。

路网中双色反向k近邻查询处理

目前,路网中反向最近邻查询引起了广泛关注,有很多算法被提出.在实际路网中,由于移动数据对象的种类多种多样,单色反向最近邻查询有时并不能完全满足要求.因此,研究路网双色反向最近邻查询具有重要的实际意义.考虑到这种情况,提出一种路网中双色反向最近邻查询算法.通过PMR四叉树索引路网,采用Dijkstra算法遍历路网.为了保证连续监控,为查询点和对象分别设置安全区.为了验证候选对象,为其设置验证监控区.由于双色查询中,对象的种类不同,因此分别采用两个集合来保存这两类对象.通过实验对比,证明该算法具有较好的有效性和稳定性.

一种快速的反向k近邻查找算法及其改进

提出一种快速的反向k近邻查找算法,该方法利用现代计算机具有外存便宜、运行速度快的特点,预先计算数据之间的距离,并组织为数据索引块存储于外存,由计算机在空闲时自动进行维护.在进行反向最近邻查询时,只需读入相应的索引块,就可进行直接查询,其时间复杂度为O(N),而且不受k的影响.为减少索引块的读取时间,提出一种改进方法来有效地压缩索引块,仅用必要的二进制位来存储对象之间的距离,并将冗余减少到最低水平,提高了算法的效率.最后通过实验分析评估算法的有效性和效率.

外包空间数据库中反向k近邻查询验证

在外包空间数据库模式下,数据持有者委托第三方数据发布者代替它来管理数据并且执行查询.当发布者受到攻击或者由于自身的不安全性,它可能返回不正确的查询结果给用户.基于已有的反向k近邻(Reverse k Nearest Neighbor,RkNN)查询方法,采用将反向k近邻查询验证转化成k近邻查询验证和范围查询验证的思想,提出一种反向k近邻查询验证的方法,并且设计了相应的算法,用于验证返回给客户端结果的正确性(没有结果点被篡改),有效性(结果点都满足用户的查询要求)和完整性(没有遗漏符合查询要求的结果点).实验验证了算法的有效性和实用性.

一种基于反向K近邻的孤立点检测改进算法

基于反向k近邻的孤立点检测算法能够从全局角度较好地检测孤立点,但是在初始阶段求数据点的k近邻时,基本算法需要O(KN2)次数据点间的距离计算,不适合大数据集。同时参数k值的选取对数据集中孤立点的确定产生很大的影响。为此采用自适应的方法确定参数k值,然后提出一种利用度量空间的三角不等式的快速挖掘算法提前剪枝,减少孤立点检测时数据点之间距离计算的次数。理论分析和实验结果证明了算法的可行性和高效性。

基于反向k近邻过滤异常的群数据异常检测

针对无数据标签的群数据异常检测问题,提出在无监督模式下利用k最近邻(kNN)算法检测群数据异常.为减少由于异常值与正常值之间相互干扰而产生的漏报和误报,提出用反向k近邻(RkNN)算法对异常群数据进行反向过滤.反向k近邻算法首先将统计距离作为不同群数据间的相似性度量,再用kNN算法求得每个集群的异常得分,并获得初始异常,最后使用RkNN算法对初始异常进行过滤.实验结果证明,所提算法能有效减少漏报和误报,且具有较高的异常检测率和良好的稳定性.

时间依赖路网中反向k近邻查询

在现存的反向k近邻查询方案中,比较高效的研究大多集中在欧氏空间或者静态路网,对时间依赖路网中的反向k近邻查询的研究相对较少。已有算法在兴趣点密度稀疏或者k值较大时,查询效率较低。对此,提出了基于子网划分的反向k近邻查询算法mTD-SubG。首先,将整个路网划分为大小相同的子网,通过子网的边界节点向其他子网进行扩展,加快对路网中兴趣点的查找速度;其次,利用剪枝技术缩小路网的扩展范围;最后,利用已有时间依赖路网下的近邻查询算法,判定查找到的兴趣点是否为反向k近邻结果。实验中将mTD-SubG算法与已有算法mTD-Eager进行对比,结果表明mTD-SubG算法的响应时间比mTD-Eager算法减少了85.05%,遍历节点个数比mTD-Eager算法减少了51.40%。

基于边界剥离思想的全局中心聚类算法

全局中心聚类算法如k-means、谱聚类在类簇分布出现重叠粘连现象时往往容易陷入局部最优且参数难以设定,极大地限制了全局中心聚类算法在实际应用中的效果。为解决此问题,提出了一种基于边界剥离思想的全局中心聚类算法。首先,设计了一步边界剥离法,根据样本点间的反向k近邻关系定义了一种局部距离加权密度,并利用密度经验分布函数一阶差分最大处的密度值作为阈值将数据集分为边界集与核心集。其次,嵌入传统的全局中心聚类算法对核心集进行聚类,得益于核心集的簇间重叠问题已明显改善,嵌入算法将更容易收敛到真实的簇中心。最后,提出一种边界吸引算法,从已被归类的核心集样本点出发,借助已有的反向k近邻关系迭代融合边界集中的样本点以完成对整个数据集的聚类。相较于目前以迭代方式进行的边界剥离算法,所提算法在计算效率上具有明显优势,不需要额外设定复杂的终止条件而直接通过阈值进行边界划分,并且全局性方法在数据局部密度存在差异的情形下具备更强的鲁棒性。在实验阶段,采用3个合成数据集以及6个真实数据集从算法性能、参数敏感性、时间消耗多个方面进行评估,实验结果进一步验证了此算法的有效性与实用性。

基于混合密度和微簇聚合的密度峰值聚类算法

密度峰值聚类算法是一种简单高效聚类新算法,但该算法在处理密度分布不均匀数据集时,很难找到正确的类簇中心,并且在样本分配过程中容易出现错误连带现象,导致聚类效果不佳。针对上述问题,提出一种基于混合密度和微簇聚合的密度峰值聚类算法(HMDPC)。HMDPC算法首先根据反向K近邻和样本间的归属关系定义样本的混合密度;其次,将数据划分为多个微簇,定义微簇之间的相似度,基于此相似度对多个微簇进行聚合,从而获得最终的聚类结果。在人工数据集和UCI数据集上进行实验,并将HMDPC算法与其它6种聚类算法比较,实验结果表明HMDPC算法聚类效果较好。

基于加权边界度的稀有类检测算法

提出了一种快速的稀有类检测算法——CATION(rare category detection algorithm based on weightedboundary degree).通过使用加权边界度(weighted boundary degree,简称WBD)这一新的稀有类检测标准,该算法可利用反向k近邻的特性来寻找稀有类的边界点,并选取加权边界度最高的边界点询问其类别标签.实验结果表明,与现有方法相比,该算法避免了现有方法的局限性,大幅度地提高了发现数据集中各个类的效率,并有效地缩短了算法运行所需要的运行时间.

计算机辅助乳腺癌诊断中的非平衡学习技术

针对计算机辅助诊断(CAD)中学习算法处理非平衡数据时,分类器预测具有大类样本的分类误差小,而稀有类样本的分类误差大的倾向性分类问题,提出基于反向k近邻的欠采样新方法.通过去除大类样本集中的噪声及冗余样本、保留具有类别代表性且可靠的样本作为有效样本以此平衡训练样本集,解决了欠采样引起的类别信息的丢失问题.基于UCI Breast-cancer数据集的仿真实验结果表明,该方法解决了非平衡学习问题的有效性,进一步的横向评测对比显示该算法性能显著优于其他同类算法.

基于标准欧氏距离的燃油流量缺失数据填补算法

为减小数据缺失对飞机油耗统计推断精度带来的负面影响,针对基于传统欧氏距离、马氏距离以及精简关联度的最近邻填补算法的不足,提出了一种基于标准欧氏距离的填补算法来估计QAR(Quick Access Recorder)数据中部分燃油流量数值的缺失。该算法通过QAR数据样本之间的标准欧氏距离选择最近邻样本,并利用熵值赋权法计算最近邻的加权系数,基于最近邻样本中燃油流量的加权平均即可得到缺失燃油流量的估计值。实验结果表明,标准欧氏距离能够有效度量样本相似性,所提出的算法优于常规填补算法,是处理飞机油耗数据缺失的一种有效方法。

基于局部密度的快速离群点检测算法

已有的密度离群点检测算法LOF不能适应数据分布异常情况离群点检测,INFLO算法虽引入反向k近邻点集有效地解决了数据分布异常情况的离群点检测问题,但存在需要对所有数据点不加区分地分析其k近邻和反向k近邻点集导致的效率降低问题。针对该问题,提出局部密度离群点检测算法——LDBO,引入强k近邻点和弱k近邻点概念,通过分析邻近数据点的离群相关性,对数据点区别对待;并提出数据点离群性预判断策略,尽可能避免不必要的反向k近邻分析,有效提高数据分布异常情况离群点检测算法的效率。理论分析和实验结果表明,LDBO算法效率优于INFLO,算法是有效可行的。

基于多模态信息融合的新闻图像人脸标注

针对传统新闻图像中人脸标注方法主要依赖人脸相似度信息,分辨噪声和非噪声人脸能力以及非噪声人脸标注能力较差的问题,提出一种基于多模态信息融合的新闻图像人脸标注方法。首先根据人脸和姓名的共现关系,利用改进的K近邻算法,获得基于人脸相似度信息的人脸姓名匹配度;然后,分别从图像中提取人脸大小和位置的信息对人脸重要程度进行表征,从文本中提取姓名位置信息对姓名重要程度进行表征;最后,使用反向传播神经网络来融合上述信息完成人脸标签的推理,并提出一个标签修正策略来进一步改善标注结果。在Label Yahoo!News数据集上的测试效果表明,所提方法的标注准确率、精度和召回率分别达到了77.11%、73.58%和78.75%,与仅基于人脸相似度的算法相比,具有较好的分辨噪声和非噪声人脸能力以及非噪声人脸标注能力。

基于核心点虚拟标签传播的密度聚类算法

针对数据聚类问题提出了一种改进的密度聚类算法。该算法将数据点分为核心点和边界点两大类,并根据核心点之间的连通性,将核心点合并为多个核心区域,每个核心区域分配一个独有的虚拟标签。以数据点间的距离为基础,构建拉普拉斯矩阵,在此基础上将核心点上的虚拟标签传播到边界点,拥有同种标签的数据点属于同一类簇。在合成数据集和真实数据集上的测试结果表明,改进的新算法相较于经典聚类算法在聚类效果上有明显提高。