基于自然邻居邻域图的无参数离群检测算法

数据挖掘领域,基于最近邻居思想的离群检测算法在面对复杂数据时,很难在没有足够先验知识条件下进行适当的参数选择。为了解决这个问题,本文在自然邻居方法的基础上,提出一种利用加权自然邻居邻域图进行离群检测的算法。该算法在整个过程不需要人为设置参数,并且能在不同分布特征的数据中准确找到数据集中的全局离群点和局部离群点。人工数据集和真实数据的离群检测结果均证明,本算法能够取得和有参数的算法中最优参数相近的效果,算法检测结果远好于对参数敏感算法的大部分情况,且更优于对参数不敏感的算法,具有更强的普适性和实用性。     

基于自然最近邻居的社团检测算法

针对传统社团检测算法无法判断网络中特殊节点和SCAN算法对于参数依赖性太大的缺点,提出了一种基于自然最近邻居概念的社团检测算法CD3N.算法利用自然最近邻居无参的特性,首先以结构相似度为基准,计算出网络节点的自然最近邻居,并依此构造小值最近邻域图;然后取邻域图中邻居数最多的节点为核心节点,根据可达关系,构造关于核心节点的社团;重复选取核心节点并构造社团的过程,直到没有可归入社团的节点.将算法应用到空手道俱乐部网络和海豚网络中,并与SCAN算法进行对比.实验结果表明,CD3N算法有效解决了参数敏感性问题,能够很好地进行社团检测.     

一种去除聚类数量和邻域参数设置的自适应聚类算法

传统聚类方法往往无法避免邻域参数和聚类数量的选择问题,而这些参数在不同形状的数据中的最优选择也不尽相同,需要根据大量先验知识确定合适的参数选择范围.针对上述参数选择问题,提出了一种基于自然邻居思想的边界剥离聚类算法NaN-BP,能够在无需设置邻域参数和聚类数量的情况下得到令人满意的聚类结果.算法核心思想是首先根据数据集的分布特征,自适应迭代至对数稳定状态并获取邻域信息,并根据该邻域信息进行边界点的标记与剥离,最终以核心点为数据簇中心进行聚类.在不同规模不同分布的数据集上进行了广泛的对比实验,实验结果表明了NaN-BP的自适应性和有效性,取得了令人满意的实验结果.     

基于自然邻居和最小生成树的原型选择算法

K最近邻居是最流行的有监督分类算法之一。然而,传统的K最近邻居有两个主要的问题:参数K的选择以及在大规模数据集下过高的时间和空间复杂度需求。为了解决这些问题,提出了一种新的原型选择算法,它保留了一些对分类贡献很大的关键原型点,同时移除噪声点和大多数对分类贡献较小的点。不同于其他原型选择算法,该算法使用了自然邻居这个新的邻居概念来做数据预处理,然后基于设定的终止条件构建若干个最小生成树。基于最小生成树,保留边界原型,同时生成一些具有代表性的内部原型。基于UCI基准数据集进行实验,结果表明提出的算法有效地约简了原型的数量,同时保持了与传统KNN相同水平的分类准确率;而且,该算法在分类准确率和原型保留率上优于其他原型选择算法。     

基于扩展自然邻居的无参分类方法

基于k-最近邻（kNN）的分类方法是实现各种高性能模式识别技术的基础,然而这些方法很容易受到邻域参数k的影响,在完全不了解数据集特性的情况下想要得出各种数据集的邻域是比较困难的。基于上述问题,介绍了一种新的监督分类方法：扩展自然邻居（ENaN）方法,并证明了该方法在不人为选择邻域参数的情况下提供了一种更好的分类结果。与原有的基于kNN需要先验k的方法不同,ENaN方法在不同的阶段预测不同的k值。因此,无论是在训练阶段还是在测试阶段,ENaN方法都能从动态邻域信息中学习到更多的信息,从而提供更好的分类结果。在不同类型不同规模的真实数据上的分类检测结果均表明了ENaN方法的有效性。     

分步筛选邻居的协同过滤改进算法

为了解决协同过滤算法用户邻居筛选的优化问题,提高推荐结果的准确性,提出了一种分步筛选邻居的协同过滤改进算法。该算法首先采用改进的 Pearson 系数法计算用户间的相似度,降序排列后,计算用户特征值,大于用户特征阈值的用户进入下一层筛选;然后选择对优先项目集有过评分的用户形成最终的邻居集;最后进行预测评分得到推荐。实验结果表明,该算法能够有效地获取用户最近邻居集,改善准确性,并且稳定性良好。     

基于空间网络数据库的组最近邻居查询

组最近邻居查询是空间数据库在最近邻居查询上的新问题.目前,对组最近邻居查询的研究局限于欧氏空间,考察的只是对象间的相对位置关系,无法处理现实生活中对象间的连通性问题.鉴于此,本文基于空间网络数据库提出以网络距离为度量标准的组最近邻居查询概念,进而提出作为其算法基础的增量最近邻居查询算法INNN,最后构造出算法NMQM.
实验证明,NMQM是一种有效的组最近邻居查询算法.     

一种移动对象增量组最近邻居查询方法

基于移动对象增量最近邻居查询(INCNN),提出一种移动对象增量组最近邻居查询方法(INCGNN)。该方法以较小的代价求出每次更新时刻的组最近邻居。针对组最近邻居查询的特点,给出了k+1组最近邻居查询改进算法,椭圆剪枝和延迟更新3种优化查询的策略。实验结果表明,INCGNN明显优于REEGNN,3种优化策略能较好地提高查询性能。     

改进邻居集合的个性化推荐算法

协同过滤算法是目前个性化推荐系统中应用最成功的推荐算法之一,但传统的算法没有考虑在不同时间段内寻找最近邻居问题,导致寻找的邻居集合可能不是最近邻居集合。针对此问题,提出一种改进邻居集合的个性化推荐算法。该算法赋予每项评分一个按时间逐步递减的权重,利用加权后的评分寻找目标用户的最近邻居。实验表明,改进的算法提高了推荐系统的推荐质量。     

空间划分虚拟网格的RFID室内定位算法

首先分析了最近邻居算法的基本原理,针对把所有参考标签作为最近邻居的选择,出现大量不必要计算,室内环境干扰较大,距离阅读器较远的标签的信号强度值阅读不准确的问题,提出了一种划分虚拟网格,动态选取最近邻居来进行定位的RFID室内定位算法.仿真结果表明,在不增加参考标签的前提下,改进的算法较最近邻居算法定位精度更高,稳定性更好.     

路网中双色数据集上连续反向k近邻查询处理的研究

近年来,反向最近邻查询(RNN)算法研究得到了普遍的关注,成为了数据库领域的一个研究热点。欧氏空 间中提出了较多的高效算法,而路网中的反向最近邻处理方面所做的工作不够,有关这方面的成果较少。路网中查询 点和数据对象之间以及不同数据对象之间的距离受到路网连通性的影响,欧氏空间中的反向最近部方法在路网中不 适用。反向最近部查询有两种类型:单色反向最近部查询(Monochromatic RNN, MRNN)和双色反向最近部查询(13i- chromatic RNN,13RNN)。到目前为止,仍然没有有效的算法来处理路网中双色数据集上的连续反向k近部查询。因 此,研究路网中双色数据集上连续反向k近部查询是很有意义的。     

基于近邻密度和半监督KNN的集成自训练方法

针对集成自训练算法随机初始化有标记样本容易在迭代中局部过拟合,不能很好地泛化到样本原始空间结构和集成自训练算法用WKNN分类器做数据剪辑时没有考虑到无标记样本对待测样本类别判定有影响的问题,提出结合近邻密度和半监督KNN的集成自训练算法。该算法用近邻密度方法选取初始化的已标注样本,避免已标注样本周围[k]个近邻样本成为已标注候选集。这样使初始化的已标注样本间的距离尽量分散,以更好地反应样本原始空间结构。同时在已标注样本候选集中选取密度最大的样本作为已标注样本。为了提高数据剪辑的性能,用半监督KNN代替WKNN,弥补WKNN做数据剪辑的时候只考虑到了有标记样本对待测样本类别的影响,而没有利用待测样本周围的无标记样本的问题,在UCI数据集上的对比实验验证了提出算法的有效性。     

基于FLANN改进的KNN医疗分类算法

本文通过研究KNN（K-最近邻）算法在疾病预测领域的使用与分析,总结出KNN的2点不足,针对不足进行相应改进并提出F_KNN（循环最近邻搜索）算法：1）针对KNN计算量大、效率低下的缺点,本文采用FLANN（快速最近邻搜索）循环搜索与待测样本距离最近的点,记录若干个最近邻点作为最近邻点子集,利用此子集取代全集对待测样本进行计算,可以降低计算量,极大地提高了KNN算法效率;2）针对KNN难以对高维数据集分类的缺点,本文采用AHP（层次分析法）对样本的特征属性进行相关性研究,使用合适的参数分配权重,提高了KNN算法准确率。本文采用一组脑中风数据集对优化后的算法进行实验,实验结果表明,F_KNN准确率达96.2%。与传统KNN相比,F_KNN提高了分类性能且极大地提高了算法效率。在处理高维且较大的数据集时,F_KNN算法优势明显,具有较好的应用前景。     

动态环境中连续K近邻查询的边界线方法

通过观察可以发现连续七近邻查询中KNN发生改变的必要条件是第k个邻居发生变化,因此不需要监测所有k近邻,只需要监测第k个邻居即可.该方法采用边界线来监测第k个邻居的变化,不过这需要将原始空间转变为时间-距离(TD)空间后进行操作.在TD空间中每一个对象用一个时间函数来表示,通过监测当前第七个邻居的前视矩形区域来构造边界线.实验结果表明,边界线算法在七非常大的时候是最有效的.     

Finsler度量在KNN算法中的应用研究

为了克服传统K近邻(Knearest neighbor,KNN)算法在距离定义上的不足,提出了一种基于Finsler度量的KNN算法(Finsler metric KNN,FMKNN)。该算法将样本点间的距离定义为Finsler度量,保留了样本属性对样本间距离度量的影响,使得样本点间的距离度量更具一般性。在手写体数据集上的实验表明,FMKNN算法的分类准确率高于传统KNN算法。     

融合用户自然最近邻的协同过滤推荐算法

现有的基于近邻的协同过滤推荐方法如基于KNN、基于K-means的协同过滤推荐常用来预测用户评分,但该方法确定邻居个数K非常困难且推荐准确率不高,难以达到理想推荐效果。从选择邻居用户这一角度出发,提出一种融合用户自然最近邻的协同过滤推荐算法（Collaborative Filtering recommendation integrating user-centric Natural Nearest Neighbor,CF3N）,该算法首先自适应地寻找目标用户的自然最近邻居集,再融合目标用户的自然最近邻居集与活动近邻用户集,使用融合后得到的邻居集合预测目标用户评分。实验使用了MovieLens数据集,以RMSE和MAE为评测标准,比较CF3N、CF-KNN与INS-CF算法,结果显示在电影领域该算法的推荐准确率有显著提高。     

Efficient processing of probabilistic reverse nearest neighbor queries over uncertain data

Reverse nearest neighbor (RNN) search is very crucial in many real applications. In particular, given a database and a query object, an RNN query retrieves all the data objects in the database that have the query object as their nearest neighbors. Often, due to limitation of measurement devices, environmental disturbance, or characteristics of applications (for example, monitoring moving objects), data obtained from the real world are uncertain (imprecise). Therefore, previous approaches proposed for answering an RNN query over exact (precise) database cannot be directly applied to the uncertain scenario. In this paper, we re-define the RNN query in the context of uncertain databases, namely probabilistic reverse nearest neighbor (PRNN) query, which obtains data objects with probabilities of being RNNs greater than or equal to a user-specified threshold. Since the retrieval of a PRNN query requires accessing all the objects in the database, which is quite costly, we also propose an effective pruning method, called geometric pruning (GP), that significantly reduces the PRNN search space yet without introducing any false dismissals. Furthermore, we present an efficient PRNN query procedure that seamlessly integrates our pruning method. Extensive experiments have demonstrated the efficiency and effectiveness of our proposed GP-based PRNN query processing approach, under various experimental settings.     

路网中基于Voronoi图的反向最近邻查询方法

针对已有的在路网中的反向最近邻(Reverse Nearest Neighbor,RNN)查询方法存在的不足,提出了利用网络Voronoi图(Network Voronoi Diagram,NVD)的NVD-RNN算法,该算法具有较好的效果,它把路网划分成小的Voronoi区域,并且采用了两个过程:过滤过程和精炼过程。过滤过程主要是提前存储可能的查询结果。精炼过程主要是从可能的结果集合中找到查询结果。并且进一步给出了处理新增加点的ADDNVD-RNN算法和处理删除点的DENVD-RNN算法。实验表明,该算法在处理路网中的反向最近邻问题时有明显的优势。     

基于kNN-DBSCAN的缺失数据填补优化算法

针对传统的kNN(k-NearestNeighbor)近邻填补算法对缺失数据的填补效果会因为k最近邻数据存在噪声受到较大干扰的问题,提出一种基于kNN-DBSCAN(k-NearestNeighbor Density-based Spatial Clustering of Applications with Noise)的缺失数据填补优化算法。将基于密度的DBSCAN聚类算法运用到kNN近邻填补算法中,先用kNN算法得到目标填补数据的原始k最近邻数据集,运用DBSCAN聚类算法对原始k最近邻数据集进行噪声检测并消除噪声数据,得到当前k最近邻数据集,最后并入kNN计算,填补目标缺失数据;同时,针对DBSCAN聚类算法参数设置敏感的问题,通过分析数据集的统计特性来确定参数,避免人为经验判断。最后利用真实数据对算法进行验证,结果显示该算法对目标缺失数据的填补准确度要优于传统的kNN算法。