| 主权项 |
一种支持动态更新的在线属性异常点检测方法，其特征在于该方法的步骤如下：(1)选取符合流数据系统在数据生成、检测方式和用户需求三方面的要求的数据模型维护持续动态更新的流数据；(2)使用在线聚类方法对流数据进行持续动态聚类，实现基于数据属性相关性的聚类划分；(3)动态维护流数据更新下的聚类划分，并持续更新数据点之间的邻居关系和距离信息，在线维护聚类相关信息，随着数据的动态更新保持维护相关概要信息结构；(4)建立数据降载方法，根据流数据系统中实际负载以及对实时性的要求，选取能够达到流数据系统实时性要求的降载方法以及近似技术保证检测方法的实时完成，并能保证最后近似结果的误差可控；(5)根据聚类划分及数据点邻居两方面相关数据信息及属性异常点评价方法，在每个聚类划分中检测异常点作为最终属性异常点结果输出；所述步骤(1)选取符合流数据系统在数据生成、检测方式和用户需求三方面的要求的数据模型维护持续动态更新的流数据，该步骤选取的数据模型需要满足能够快速高效维护数据动态更新，满足在主流应用服务器部署实施，因此采用当前业内主流应用模型滑动窗口模型，对于流数据仅保存并保持更新最近一部分作为滑动窗口，并基于当前最新窗口进行查询处理；所述步骤(2)使用在线聚类方法对流数据进行持续动态聚类，此线聚类方法需要对持续更新的流数据进行动态聚类划分，并且针对流数据内容漂移的特性，在线聚类方法能够始终维护保持反映最新数据内容的聚类划分状态；方法的具体实施包含以下内容：1)在流数据更新之前建立初始化聚类划分，在初始化阶段对当前滑动窗口内数据进行聚类，并利用计算数据点之间几何距离来衡量数据之间的属性相关性，根据数据点间距离聚集相似、相关数据形成初始的聚类划分；2)建立简洁的时间聚类特征数据结构维护聚类划分概要信息，描述每个划分的关键特征，能够根据概要信息还原聚类的中心以及划分范围半径；3)针对动态更新的流数据在线维护聚类划分，流数据系统中每一时刻都有大量新生成数据到达，在线聚类方法需要实时的对这些新数据进行聚类，即时 完成对划分的更新；4)对时间聚类特征切片维护，实现聚类信息的动态更新，在完成对新生成数据的动态聚类后，需要及时更新聚类特征概要信息，由于采用滑动窗口模型，数据不断更新，产生新数据的同时大量陈旧数据需要过期，因此在对新数据聚类的同时还需要消除过期数据的概要信息；5)根据在线聚类划分总数，进行必要的聚类合并操作保持聚类结果的质量以及总数的稳定；由于采用的聚类方法的特点，以及流数据不断生成的大量全新数据点，滑动窗口内将出现大量的微型聚簇，这些微型划分会严重降低最终聚类结果质量，同时将会占用大量内存，消耗系统资源，因此需要进行聚类合并；所述步骤(3)动态维护流数据更新下的聚类划分，并持续更新数据点之间的邻居关系和距离信息，需要在线维护后续异常点检测步骤中所需要的数据相关信息，采用基于距离的度量来计算数据点间的相关性以及检测异常点，因此对于每个数据点需要计算在在其指定距离领域内的邻居数目，当邻居总数低于用户指定阈值时，则说明该数据点异常，另外由于属性异常点的特点实际检测过程发生在每个独立的聚类划分中，所以在数据相关信息的维护过程中对每个聚类仅需维护更新其内部数据点相关信息；所述步骤(3)在线维护聚类相关信息，随着数据的动态更新保持维护相关概要信息结构，在线维护过程中还需要针对动态更新的流数据对链表进行动态维护更新操作，具体步骤包括：1)对于刚进入聚类的新数据点，生成对应节点加入链表尾部，接下来对链表进行反向遍历，计算各个前序节点与新节点的距离及邻居关系；2)随着滑动窗口的滑动，将过期数据对应节点由链表中移除，保证之后检测过程中在其后序邻居的前向邻居数组中节点号为无效；3)在发生聚类合并操作后，同时需要合并两个聚类的链表及更新节点信息；所述步骤(4)保证最后近似结果的误差可控，鉴于要保证对最终结果影响最小的降载原则，需要把当前滑动窗口内每个聚类中的安全点作为丢弃数据的候选集，所谓安全点是指其后序邻居数目超过用户指定的异常点判定阈值的数据点；所述步骤(4)选取能够达到流数据系统实时性要求的降载方法以及近似技术保证检测方法的实时完成，并能保证最后近似结果的误差可控，降载方法的具体实施方式如下： 1)根据流数据系统应用实际负载压力确定降载方法的丢弃数据比例，保证应用服务器及检测方法能够支撑对剩余数据进行实时监测；2)当滑动窗口内涌入的流数据超过系统额定负载能力时，开始在符合条件的聚类对象中进行降载，在该聚类内所有安全点中随机选取一部分进行丢弃降载，操作在达到指定降载比例上限后停止；3)由于需要丢弃部分数据点，聚类内部原有链表节点结构需要进行相应调整；在降载过程中对每个链表节点使用新的属性信息结构代替前序邻居数组来计算每个节点的有效前序邻居总数，该属性信息结构记录节点在刚进入链表时其前序安全点邻居总数与当时聚类内安全点总数的比值，根据比值即可近似计算出其前序邻居总数；所述步骤(5)根据聚类划分及数据点邻居两方面相关数据信息及属性异常点评价方法，在每个聚类划分中检测异常点作为最终属性异常点结果输出，通过判断每个数据点的邻居数目是否超过用户指定的异常点判定阈值来确定异常点，并根据在线维护过程中实际发生的降载操作，在计算每个数据点的前序邻居总数时决定是否使用比值近似估算，应用相关评价方法及数据信息在每个聚类划分内检测属性异常点并实时输出。 |
