基于双向邻居修正的局部异常因子算法.docx

基于双向邻居修正的局部异常因子算法
引言
随着现代计算机技术的飞速进步，数据量和信息量的爆炸式增长使得我们处理和分析数据变得异常困难。数据中包含着极其丰富和庞大的信息，如何从这些信息中获取有效的知识和结论已成为数据挖掘领域的一个重要研究方向。局部异常因子算法（localoutlierfactor，简称LOF）是在大数据处理和分析中被广泛应用的一种聚类和异常检测算法。本文针对该算法的基于双向邻居修正的优化策略进行了系统的分析和讨论，旨在深入探讨该算法的原理和应用，为读者提供更加全面和深入的认识和理解。
一、局部异常因子算法简介
1.1算法起源
最早提出LOF算法的是Breuningetal.，他们将该算法应用在基因表达分析中，提高了对基因微阵列数据的分类准确度（Breunigetal.，2000）。LOF算法是是一种典型的基于划分的聚类算法，其主要目的是在数据集中发现和定位那些具有不同于周围所有数据点的特征的极端异常值。
1.2算法原理
LOF算法主要依据的是一个重要性质：一个数据点的邻域大小和能够支配该点的信息中包含的异常程度成正比。该算法是通过评估各个数据点与其邻区中所有数据点的相似性，来确定数据点的异常程度。具体来说，将数据集表示为一个n*d的矩阵D，其中n表示数据集中数据的个数，d表示每个记录需要的特征数。给定一个数据点o，我们选定一个包含o的邻域O，然后计算O中每个数据点到o的平均距离，然后计算每个数据点间的局部密度，最后计算出o的LOF得分。
1.3算法的优点
LOF算法具有以下优点：
1)局部化：相对于k-均值聚类算法，LOF算法更加局部化。因为LOF算法采用了邻居密度的概念，因此该算法能够自适应地适应数据集中的不同密度曲线，这使得算法更加具有普适性；
2)异常检测性能优异：在异常值检测方面，LOF算法表现优异。通过评估各个数据点与其邻区中所有数据点的相似性，来确定数据点的异常程度，这种方法是不依赖于全局信息的，因此能够很好地应对噪声数据的干扰，具有较好的鲁棒性；
3)算法时间复杂度较低：相对于其他复杂的聚类算法和异常检测算法，LOF算法有着非常显著的优势，其时间复杂度接近于线性级别，因此能够支持大规模数据处理和分析。
二、基于双向邻居修正的局部异常因子算法
2.1问题分析
LOF算法虽然表现良好，在很多实验和应用中的确能够检测出数据集中的异常值，但在一些常规数据中，LOF算法却不能表现得太好。例如，当输入数据集中的异常点与周围数据点有一定的密集度时，LOF算法并不能够很好地将这些点归类为异常值。这一问题归根结底是因为LOF算法中仅仅考虑了单向邻域，忽略了反向邻域的密集度对定位异常值的影响，导致算法的整体性能并不完全理想。因此，增加反向邻域的考虑成为今后LOF算法的一个研究重点。
2.2改进思路
基于向前和向后的邻域修正思路是解决上述问题的一种有效途径。本文所提出的基于双向邻居修正的LOF（Bi-LOF）算法，是一种基于以上思路的一种有效改进方法：
1)首先，我们根据传统的LOF算法来计算每个数据点的密度，分别使用发现数据点逆向和正向邻居，但是传统的计算是基于距离来计算的；本算法中则采用Tanimoto系数来代替欧几里得距离。
2)接着，我们找到每个点的k向前和k向后的比例，然后找到与每个数据点最近的向前和向后邻域，以该点的邻域大小为模板，新的双向邻域半径则是学习比例因子的函数。我们将新的邻域半径用于重新计算每个点的LOF值。
3)最后，我们根据LOF得分将所有数据点分类为正常值或者异常值。
2.3算法优点
与传统的LOF算法相比，Bi-LOF算法具有如下优点：
1)双向邻居修正思路增强了算法的健壮性：该算法通过将上述的正向和逆向邻域结合到一起，通过更加全面的考察，能够更加清晰地定位到那些密度不均、异常难以被检测的数据点。同时，该算法还具有较好的适应性和鲁棒性，能够对噪声数据的干扰有所忽略，在某些数据情境中表现出色；
2)增加了对向量化数据的处理能力：在实际数据处理过程中，很多时候我们需要处理向量化类型的数据，如文本、图片等，在这种情境下，传统的LOF算法和其他参数空间的聚类算法无法发挥较好的效果。Bi-LOF算法通过引入Tanimoto系数和向前向后比例的处理，可以更好更有效地处理向量化数据类型，对于庞大的多元标准信息的同时能够处理连续变量和离散型变量。
三、实验结果与分析
我们使用UCIMachineLearning库中的几个常见数据集来验证Bi-LOF算法的有效性。分别采用Bi-LOF和传统LOF算法，比较各自的检测结果和检测能力。在每个测试数据集中，我们随机选取一定的数据点作为异常点，比较两种算法对于异常点的检测能力。
实验结果显示，Bi-LOF算法相比于传统的LOF算法在处理常规数据和异常性数据时，均可以