基于时空轨迹数据的异常检测

伴随着智能设备的普及和无线通信技术的发展,用户在使用无线网络满足各种需求时,无线网络也记录下了用户上网留下的大量时空轨迹数据.针对时空轨迹数据的异常检测已经成为数据挖掘领域一个新的研究热点.为了更好地关注学生健康发展,促进校园信息化建设,以真实校园上网数据为例,提出了一种基于多尺度阈值和密度相结合的谱聚类算法(Spectral Clustering Algorithm Based on The Combination of Multi-Scale Threshold And Density,MSTD-SC),使用基于最短时间距离子序列(Shortest Time Distance-Shortest Time Distance Subsequences,STD-STDSS)的亲和距离函数来构造初始相似度矩阵,进一步引入协方差尺度阈值和空间尺度阈值对相似度矩阵进行0-1化处理,以此得到更精确的样本相似度,接着对相似度矩阵进行特征值分解,得到新的特征向量空间,最后采用DBSCAN聚类避免了K-means算法需要人工确定聚类数目的缺陷.利用轮廓系数评估多种算法得到的实验结果,MSTD-SC算法体现出了更好的聚类性能.将其应用于用户个体的异常检测中,异常用户名单被验证是有效可信的.     

基于共享反K近邻的局部离群点检测算法

离群点检测和分析离群模式隐含的特征是离群点挖掘的重要研究内容.现有离群点检测算法存在两个明显的不足:根据离群度检测离群点,难以确定离群点的数量;忽略了与离群点邻接的聚类信息,不能提供解析离群模式的有效证据.为此,提出一种基于共享反K近邻的离群点检测算法,首先定义了一种对密度和维数变化不敏感的共享反K近邻相似度,然后应用聚类方法将数据集划分为聚类簇和包含离群点的离群簇,从而获取数据集中的离群点及解析离群点的聚类结构.仿真结果表明,反K近邻算法比现有方法更能精确地检测数据集中的局部离群点,具有很好的控制性能.     

一种基于离群算法的窃电行为检测的研究

针对窃电行为现场查证具有难以克服的现实困难,提出一种基于离群数据挖掘的窃电行为检测方法。该离群算法基于密度聚类算法,采用基于用电量波动的不同方向识别不同的用电模式,基于用电频率、离群距离以及异常规则关联度的计算挖掘潜在离群数据点,并通过基于评价矩阵确定离群阈值对离群数据点存在窃电行为的可能性进行确定性分析,实现对窃电行为的数据化检测。最后通过仿真测试证明该算法在针对混杂不同用电模式的用电数据的窃电检测方面相对于其他数据挖掘算法具有更好的性能表现。     

融合最近邻矩阵与局部密度的自适应K-means聚类算法

针对传统K-means聚类算法对初始聚类中心和离群孤立点敏感的缺陷,以及现有引入密度概念优化的K-means算法均需要设置密度参数或阈值的缺点,提出一种融合最近邻矩阵与局部密度的自适应K-means聚类算法。受最邻近吸收原则与密度峰值原则启发,通过引入数据对象间的距离差异值构造邻近矩阵,根据邻近矩阵计算局部密度,不需要任何参数设置,采取最近邻矩阵与局部密度融合策略,自适应确定初始聚类中心数目和位置,同时完成非中心点的初分配。人工数据集和UCI数据集的实验测试,以及与传统K-means算法、基于离群点改进的K-means算法、基于密度改进的K-means算法的实验比较表明,提出的自适应K-means算法对人工数据集的孤立点免疫度较高,对UCI数据集具有更准确的聚类结果。     

基于最近邻原则的半监督聚类算法

基于最近邻原则的半监督聚类算法是以基于最近邻的聚类中心求解算法为基础的。在基于最近邻的聚类中心求解算法中,用相似度矩阵记录数据点间的相似程度,由目标函数最小值求得聚类的类中心点。在基于最近邻原则的半监督聚类算法中,根据约束信息来调整相似度矩阵G,数据点间相似度的变化引起了数据点间加权欧式距离的变化,由此更新加权欧式距离矩阵M,最后执行聚类中心求解算法完成聚类。大量实验结果表明,该算法能获得较好的聚类结果。     

加权的自适应相似度度量

聚类分析是数据挖掘中一种非常重要的技术.聚类算法中的关键问题是相异度或相似度的度量,聚类结果直接依赖于相异度或相似度度量,尤其对于谱聚类方法更是如此.谱聚类算法是近期兴起的一种基于相似度矩阵的聚类算法.相比于传统的划分型聚类算法,谱聚类算法不受限于球状聚类簇,能够发现不规则形状的聚类簇.在已有的谱聚类算法中,高斯核相似度是最常用的相似度度量准则.基于高斯核相似度度量及其扩展形式,提出了一种加权的自适应的相似度度量,此相似度可以用于谱聚类以及其他基于相似度矩阵的聚类算法.新的相似度度量不仅能够描述多密度聚类簇中数据点间的相似度,而且可以降低离群点(噪声点)与其他数据点间的相似度.实验结果显示新的相似度度量可以更好地描述不同类型的数据集中数据点间的相似度,进而得到更好的聚类结果.     

基于共享最近邻的离群检测算法

为识别混合属性数据集中的离群点,提出了一种基于共享最近邻的离群检测算法,通过计算增量聚类结果簇间的共享最近邻相似度,不但能够发现任意形状的簇,还可以检测到变密度数据集中的全局离群点。算法时间复杂度关于数据集的大小和属性个数呈近似线性。在人工数据集和真实数据集上的实验结果显示,提出的算法能有效检测到数据集中的离群点。     

基于混合式聚类算法的离群点挖掘在异常检测中的应用研究

为了提高异常检测系统的检测率,降低误警率,解决现有异常检测所存在的问题,将离群点挖掘技术应用到异常检测中,提出了一种基于混合式聚类算法的异常检测方法(NADHC)。该方法将基于距离的聚类算法与基于密度的聚类算法相结合从而形成新的混合聚类算法,通过k-中心点算法找出簇中心,进而去除隐蔽性较高的少量攻击行为样本,再将重复增加样本的方法结合基于密度的聚类算法计算出异常度,从而判断出异常行为。最后在KDD CUP 99数据集上进行实验仿真,验证了所提算法的可行性和有效性。     

基于相对密度和流形上k近邻的聚类算法

针对传统的基于欧氏距离的相似性度量不能完全反映复杂结构的数据分布特性的问题,提出了一种基于相对密度和流形上k近邻的聚类算法。基于能描述全局一致性信息的流形距离,及可体现局部相似性和紧密度的k近邻概念,通过流形上k近邻相似度度量数据对象间的相似性,采用k近邻的相对紧密度发现不同密度下的类簇,设计近邻点对约束规则搜寻k近邻点对构成的近邻链,归类数据对象及识别离群点。与标准k-means算法、流形距离改进的k-means算法进行了性能比较,在人工数据集和UCI数据集上的仿真实验结果均表明,该算法能有效地处理复杂结构的数据聚类问题,且聚类效果更好。     

基于中心移动的轨迹离群点检测

AIS数据是指通过AIS系统获取的船舶运动轨迹信息, 对其进行挖掘可以获得船舶的运动模式、航行路线、停靠地点等信息. 但其在采集过程中产生的离群点会对聚类等任务造成负面影响, 因此对AIS数据挖掘之前需要进行离群点检测. 然而, 当AIS轨迹数据中存在大量离群点时, 会导致大多数离群点检测算法的准确率显著下降. 为了解决这个问题, 本文提出了一种基于中心移动的轨迹离群点检测算法(center shift outlier detection, CSOD). 通过迫使数据点向其K近邻集合的中心移动, 使每个数据点更加接近典型数据, 从而有效地消除了离群点对聚类的影响. 为了验证本文算法的有效性, 使用浙江海域AIS渔船轨迹数据集, 将本文提出的CSOD算法与一些经典的离群点检测算法进行了对比实验. 实验结果表明, CSOD算法整体上性能更加优越.     

基于轨迹信息熵分布的异常轨迹检测方法

针对异常轨迹检测多特征检测和检测单元造成的检测效率低等问题。提出一种基于轨迹信息熵分布的异常轨迹检测方法。该算法根据轨迹偏转角与速度将轨迹分割成若干轨迹段,计算轨迹段间加权多特征距离判断轨迹间相似度,进而完成轨迹聚类并计算出每类代表性轨迹,然后对待检测轨迹进行分割,利用代表性轨迹计算每个轨迹段的信息熵,通过比较轨迹信息熵大小及其分布特点实现异常轨迹检测。大西洋飓风数据仿真实验结果表明该方法提高了聚类效果,克服以整条轨迹检测效率低的缺点,提升了异常轨迹检测算法的有效性。     

基于R-Tree的高效异常轨迹检测算法

提出了异常轨迹检测算法,通过检测轨迹的局部异常程度来判断两条轨迹是否全局匹配,进而检测异常轨迹.算法要点如下:(1) 为了有效地表示轨迹的局部特征,以k个连续轨迹点作为基本比较单元,提出一种计算两个基本比较单元间不匹配程度的距离函数,并在此基础上定义了局部匹配、全局匹配和异常轨迹的概念;(2) 针对异常轨迹检测算法普遍存在计算代价高的不足,提出了一种基于R-Tree的异常轨迹检测算法,其优势在于利用R-Tree和轨迹间的距离特征矩阵找出所有可能匹配的基本比较单元对,然后再通过计算距离确定其是否局部匹配,从而消除大量不必要的距离计算.实验结果表明,该算法不仅具有很好的效率,而且检测出来的异常轨迹也具有实际意义.     

基于连边距离矩阵的重叠社区发现

现有重叠社团发现算法大多直接从相邻连边的相似性出发,不能有效利用网络的多层连边信息。基于此,本文提出了一种基于连边距离矩阵的重叠社区发现算法LDM。首先结合连边-节点-连边随机游走模型,以实现多级连边信息的有效利用,其次借助模糊聚类方法,处理连边距离矩阵以获取连边社区,最后根据扩展模块度调整和优化重叠社区结构。在人工网络和真实网络上的实验结果表明,所提算法能够有效提高重叠社区发现算法的准确度。     

改进DBSCAN算法在校园轨迹数据相似性的应用

针对如何更准确地分析校园无线网络数据中隐藏的社交关系亲密度, 本文提出了改进DBSCAN时空聚类算法. 首先, 通过采集校园无线网络数据, 在根据学生连接WiFi的地点, 时间等信息形成时空轨迹. 运用改进的算法对时空轨迹聚类. 其次, 对聚类结果进行特征轨迹提取, 运用LCSS算法进行相似性对比, 轨迹间相似度越高说明关系比较亲密; 相似度越低, 可能是较孤僻的学生, 老师需要进一步排查和引导教育. 最后, 运用FinBI对轨迹聚类结果可视化展示. 实验结果表明, 该算法提高了聚类结果的准确性和有效性, 为解决其他相似性问题提供思路.     

基于层次聚类识别数据集前n个全局孤立点

孤立数据的存在使数据挖掘结果不准确,甚至错误。现有的孤立点检测算法在通用性、有效性、用户友好性及处理高维大数据集的性能还不完善,为此,提出一种有效的全局孤立点检测方法,该方法进行凝聚层次聚类,根据聚类树和距离矩阵来可视化判断数据孤立程度,确定孤立点数目。从聚类树自顶向下,无监督地去除离群数据点。在多个数据集上的仿真实验结果表明,该方法能有效识别孤立程度最大的前n个全局孤立点,适用于不同形状的数据集,算法效率高,用户友好,且适用于大型高维数据集的孤立点检测。     

基于加权聚类集成的标签传播算法

标签传播算法（LPA）是一种高效地处理大规模网络的社区发现算法,由于其近乎线性的时间复杂度而受到广泛关注。然而,该算法每个节点的标签依赖于其邻居节点,其迭代速度和聚类有效性对标签信息的更新顺序非常敏感,影响了社区发现结果的准确性和稳定性。基于该问题,提出了一种基于加权聚类集成的标签传播算法。该算法利用多次标签传播算法的结果作为基聚类集,并用模块度评估每个基聚类的重要性,使其作为节点相似性度量的权值形成加权相似性矩阵,最后通过层次聚类得出最终的社区划分结果。在实验分析中,该算法和其他5个具有代表性的标签传播算法的改进算法在真实数据集上进行了比较,展示了新算法能有效地提高标签传播算法的社区发现精度。     

基于核主成分分析的异常轨迹检测方法

针对现有算法不能有效应用于多因素轨迹异常检测的问题,提出基于核主成分分析(KPCA)的异常轨迹检测方法。首先,为了改善轨迹特征提取的效果,采用KPCA对轨迹数据进行空间转换,将非线性空间转换到高维线性空间;其次,为了提高异常检测的准确率,采用一类支持向量机对轨迹特征数据进行无监督学习和预测;最终检测出具有异常行为的轨迹。采用大西洋飓风数据对算法进行测试,实验结果表明,该算法能够有效提取出轨迹特征,并且与同类算法相比,该算法在多因素轨迹异常检测方面具有更好的检测效果。     

基于轨迹稀疏聚类的高速公路车辆检测

针对高速公路中车辆的实时检测问题,提出了一种基于轨迹稀疏谱聚类的高速公路车辆检测方法。使用ORB算法检测特征点并利用基于金字塔LK光流算法进行跟踪得出特征点轨迹,将轨迹逆投影至三维世界坐标系,利用轨迹三维信息构建轨迹间的相似矩阵并对其进行稀疏化处理,采用谱聚类方法对特征点轨迹进行初步聚类,对谱聚类结果进行类间合并得出车辆检测结果。实验结果表明,方法花费了更少的时间代价,有效地解决了车辆遮挡问题,车辆实时检测精度提高至93%,具有一定的有效性和价值。     

基于改进Hausdorff距离的轨迹聚类算法

以整条轨迹为目标的聚类方法存在轨迹较长的问题。为此,提出一种以轨迹子段为聚类目标的聚类算法CTIHD。给出一种新的轨迹子段距离度量方法,用以消除轨迹子段之间的公共偏差。利用特征点概念将轨迹划分成轨迹子段集,计算轨迹子段之间的相似度,由此实现聚类。实验结果表明,该算法相比同类算法具有更好的轨迹聚类效果。     

基于密度聚类的出租车异常轨迹检测

出租车GPS装备的普及使用产生了大量轨迹数据。出租车异常轨迹的检测和分析，可为惩罚具有欺诈行为的出租车司机提供有益支撑。针对出租车稀疏轨迹，基于轨迹相对相似度检测异常轨迹，由于其具有不对称性，类似于DBSCAN的传统密度聚类方法无法适应此种情况，本文提出基于密度RDBSCAN算法用于出租车异常轨迹聚类检测。对于聚类得出的候选异常轨迹，结合轨迹密度异常值和轨迹长度异常值的概念，利用证据理论综合前述2个因素来判别轨迹的异常程度，进而得到异常程度最高的TOP-N异常轨迹。使用旧金山真实的出租车数据，通过提取相同起点和终点（Origin-Destination, OD）的轨迹集进行实验，实验结果表明本文提出的方法能够有效地检测到异常轨迹，并成功给出异常程度最高的TOP-N异常轨迹。