Outlier Detection Based on Fuzzy Rough Granules in Mixed Attribute Data

Abstract

离群点检测是数据挖掘的重要研究方向之一。然而，目前的研究大多集中在分类或数值属性数据的离群点检测上。关于混合属性数据离群点检测的研究很少。在本文中，我们引入模糊粗糙集（FRS）来处理混合属性数据中的离群点检测问题。由于经典粗糙集的离群点检测模型仅适用于分类属性数据，因此我们使用FRS对离群点检测模型进行了推广，构建了基于模糊粗糙粒的广义离群点检测模型。首先，定义颗粒离群度（GOD），利用模糊逼近精度表征模糊粗糙颗粒的离群度。然后，通过将GOD和相应的权重相结合，构造基于模糊粗糙粒子的离群因子来表征对象的离群程度。此外，还设计了相应的基于模糊粗糙粒子的离群点检测（FRGOD）算法。通过对16个真实数据集的实验，评估了FRGOD算法的有效性。实验结果表明，该算法对异常值的检测更加灵活，适用于数值、分类和混合属性数据。

关键词—近似精度、模糊粗糙集（FRSs）、粒度计算（GrC）、混合属性、离群点检测。

I. INTRODUCTION

离群点检测是数据挖掘领域最重要的研究方向之一。其目的是找出行为与预期对象不同的对象。通常，异常值可分为三类：
1） 全局异常值；
2） 上下文（或条件）异常值；
3） 集体异常值[1]。
它在入侵检测、信用卡欺诈判断和医疗诊断等许多应用中发挥着重要作用[2]。最近，离群点检测已应用于无线传感器网络定位、时间序列和过程监控[3]-[5]。

近年来，越来越多的研究者开始重视离群点检测，并提出了许多离群点检测方法。根据离群点检测方法所采用的具体理论或技术路线，离群点检测方法大致可分为：
1） 统计方法[6]；
2） 基于聚类的方法[7]；
3） 基于深度的方法[8]；
4） 基于距离的方法[9]；
5） 基于密度的方法[10]。

统计方法大多针对单个属性，但许多数据通常涉及多个属性，这使得它们不适用于多维数据集。基于深度的方法对二维或三维空间的数据更有效，对高维混合属性数据的检测效率较低。

为了避免统计和基于深度的方法出现问题，Knorr和Ng提出了一种基于距离的方法[9]，该方法使用任意两个对象之间的距离作为离群度的度量。远离大多数其他对象的对象被视为异常值。基于距离的方法由于易于操作而被广泛使用。然而，对于高维数据，稀疏问题很难解决。由于它使用两个参数，因此对参数的选择非常敏感。

现有的离群点检测工作将离群点视为二进制属性。然而，在现实生活中，为每个对象指定一个异常度更有意义。因此，基于密度的方法首先由Breunig et al.于2000年[10]提出，其基本思想是离群点周围的密度与其最近邻点周围的密度大不相同。在此基础上，为每个对象分配一个局部离群因子（LOF），以指示其离群程度。对象的LOF值越大，其成为异常值的可能性越大。 基于密度的方法仍然存在对参数选择敏感的问题。此外，大多数基于距离和基于密度的方法都是使用欧几里德距离设计的。因此，在实际应用中，基于距离和基于密度的方法可能不是检测分类（标称）或混合（混合或异构）属性数据的异常值的最佳方法。

近年来，新的理论和范式被用于数据挖掘。作为一种重要的知识获取工具，粒计算（GrC）是一种新的理论，用于在解决大规模复杂问题时模拟人类思维的自然模型[11]，[12]。它为研究数据挖掘和模式识别中的许多问题提供了一个概念框架。GrC模型大致可分为两类：一类是以处理不确定性为主要目标；二是以多粒子计算为目标。

粗糙集理论是GrC的一种实现方法，它在一定程度上强调了粒度概念的重要性。因此，它已成为一种流行的GrC数学框架，应用于许多领域，如特征选择、模式识别和数据挖掘[13]–[17]。为了弥补基于距离和基于密度的方法不能有效处理分类属性数据的不足，提出了基于粗糙集或GrC的离群点检测算法。例如，Nguyen在RST[18]中提出了一种使用多级近似推理方案检测和评估异常值的方法。Chen等人[19]介绍了一种基于GrC的异常值检测方法。薛和刘[20]提出了一种基于粗糙集的半监督离群点检测方法。Albanese等人[21]使用一种新的粗糙集方法将异常检测扩展到时空数据。此外，Jiang等人[22]利用RST中的属性序列建立了一种异常值检测方法。Jiang等人[23]提出了一种基于信息熵和RST的离群点检测方法。在RST的基础上，Jiang和Chen[24]引入了一种新的利用经典近似精度的离群点检测方法。Maciá-Pérez等人[25]扩展了基于RST的离群点检测基本理论的数学框架，并设计了一种有效的算法来检测大量信息中的离群点。最近，在RST框架下，在[26]中构造了一种基于经典近似精度和熵的离群点检测算法。

上述方法证明了RST方法在离群点检测中的有效性。然而，值得注意的是，这些方法基于等价关系和等价类建立数学模型，它们的检测模型仅适用于类别属性，而不适用于数值（数值）属性数据。这些检测模型在处理数值属性数据时需要离散化，从而增加了数据处理的时间，并伴随着显著的信息损失，最终影响检测的准确性。为此，Chen等人[27]提出了一种邻域离群点检测算法。以邻域粗糙集为基本框架，Yuan等人[28]、[30]和Yuan and Feng[29]提出了一些适用于混合属性的离群点检测方法。

由于经典的RST仅适用于处理分类或名义数据，Dubois和Prade提出了模糊粗糙集（FRS）模型[31]。由于FRS使用模糊二元关系来描述对象之间的相似性，因此它可以直接处理数值或连续属性数据而无需离散化，从而保留更多关于数值或连续值的信息。受此启发，FRS[32]–[34]上引入了一系列扩展。例如，为了探索更复杂的每秒关系和对象之间的结构，Yaung等人[34]建立了基于t-范数和t-锥的广义FRS模型。此外，如何有效地将FRS模型应用于数据挖掘也引起了广泛的关注。FRS已成功应用于数值或混合特征选择、分类、聚类等[35]–[40]。然而，FRS模型下混合属性离群点检测的研究尚未见报道。

在此基础上，提出了一种新的基于模糊粗糙粒子的全局离群点定义。首先，给出了模糊逼近精度的定义。其次，基于模糊逼近精度，定义了颗粒离群度（GOD）来表征模糊粗糙颗粒的离群度。第三，通过综合GODs和相应的权重来表征对象的离群程度，构造了基于模糊粗糙颗粒的离群因子（FRGOF）。最后，设计了具体的基于模糊粗糙颗粒的离群点检测（FRGOD）算法。具体来说，我们在本文中的主要贡献如下。

1） 通过定义混合模糊相似关系，构造了一种新的FRS模型。
2） 定义模糊逼近精度来构造GOD和离群因子。
3） 提出了一种基于模糊粗糙粒子的广义离群点检测模型。
4） 实验结果表明，该模型对数值、分类和混合属性数据具有较好的有效性和适应性。

本文的其余部分组织如下。在下一节中，我们将介绍有关FRS的初步知识。在第三节中，我们构建了一个广义的离群点检测模型，分析了具体的离群点检测模型，并提出了相应的离群点检测算法。第四节报告了我们的实验结果。最后，第五节总结了本文。

II. PRELIMINARIES

本节将回顾后续章节[34]、[41]、[42]中使用的一些定义和符号。

A. Granular Computing 粒度计算

GrC是一种新的理论，用于模拟人类在解决大规模复杂问题时的自然思维模式，为研究数据挖掘和模式识别中的许多问题提供了一个概念框架。GrC模型大致可分为两类：一类是以处理不确定性为主要目标，如基于模糊集理论的单词计算模型；另一种是以多颗粒计算为目标，如商空间理论、RST、云模型等。除了上述主要的GrC模型外，随着GrC研究的深入，一些扩展的GrC模糊模型相继被提出，如模糊RST、邻域RST和云粗糙集模型[11]，[12]。

B. Fuzzy Rough Set 模糊粗糙集

FRS是GrC的重要模型，是处理数值或混合数据不确定性信息的有力工具。在FRS模型中，信息存储在表中，其中每一行表示一个对象（实例）。数据表也称为模糊信息系统（FIS），其形式定义如下。

FRS是一个四元组，其中是一组非空的有限对象，称为全集；是一组非空的有限属性；V是属性域，意味着，，其中是属性a的域；且是一个信息函数，满足并且，那么. 当且，FIS称为模糊决策系统（FDS），其中C表示条件属性，D表示决策属性。

定义1： 设，如果是到的映射，即，则称为上的模糊集。

对于,被称为的成员函数，或的的成员函数。上的整个模糊集被记录为。显然，，其中是的功率集。模糊集可以表示为或者

。对于，模糊集的一些运算定义如下。
1） ，.
2） .
3）

定义2： 设和，定义了从到的模糊关系为模糊集.

对于，隶属度表示与之间存在关系的程度。特别是，从到的模糊关系称为上的模糊关系。

从到的模糊关系可以用模糊关系矩阵表示，即，其中，每个行向量表示一个模糊集。从到的所有模糊关系的集合表示为。

定义3： 设是上的模糊关系，即。对于， 我们有：
1） 是自反的 ；
2） 是对称的 ；
3） 是传递的

若满足自反对称，则称为上的模糊相似关系；若满足自反、对称和传递，则称为上的模糊等价关系。

将模糊集的并、交、补运算推广到一般三角范数（范数）、三角锥（范数或残差范数）和否定算子。

定义4： 让函数，如果，它满足以下条件。
1） 交换性：
2） 结合性：
3） 单调性：
4） 边界条件：
然后，称为上的三角模.

如果二元算子满足上述交换性、结合性、单调性和边界条件，则二元算子称为上的三角形圆锥。

定义5： 求反算子是上的降序映射→满足边界条件和的。通常，称为标准的求反运算符。如果，则称为回旋的。

表一显示了模糊推理中常用的一些三角范数和圆锥。

目前，FRS指的是Dubois和Prade首先提出的概念[31]，定义如下。

定义6： 给定，设是上的模糊等价关系，的下近似和上近似是上的一对模糊集，其隶属函数分别为

为了探索每秒之间更复杂的关系和对象之间的结构，Yeung等人建立了基于和的广义FRS模型[34]。

定义7： 设为上的模糊相似关系，的下近似和上近似是上的一对模糊集，其隶属函数分别为

我们可以发现，当使用不同的和时，可以得到不同的FRS模型。在实践中，我们可以根据需要选择不同的和。显然，当和，定义的FRS模型与定义6中的相同。

C. Some Definitions of Outlier 离群点的一些定义

根据霍金斯对离群值的定义[2]，离群值的形式定义如下。

定义8： 设和分别为对象的值集，由两种机制和生成，是一种可以表示异常值特征的度量。对于和，如果，那么在中称为离群值。

此外，Knorr和Ng引入了基于距离的离群值的正式定义[9]。

定义9： 设是给定的距离阈值，是给定的分数阈值，并且是给定的距离度量。对于，如果

那么称为基于距离的异常值，其中表示经典集合的基数。

鉴于在现有的离群点检测工作（如上述基于距离的方法）中将离群点视为二元属性，Breunig等人提出了一种基于密度的方法[10]。在该方法中，为每个数据对象分配一个LOF，以指示其异常程度。数据对象的LOF值越大，其成为异常值的可能性就越大。最近，Jiang和Chen[24]定义了一个基于GrC和粗糙集的离群值因子来检测离群值。根据他们的想法，本文定义了FRGOF来检测异常值。

III. OUTLIER DETECTION BASED ON FUZZY ROUGH GRANULES IN MIXED ATTRIBUTE DATA 根据混合数据中的模糊规则进行的检查

在这一部分中，我们首先介绍了一个广义离群点检测模型，然后基于一个特定的检测模型对其进行了分析。最后，我们设计了一个具体的算法。

A. Generalized Outlier Detection Model 广义离群点检测模型

设和。对于，设，可以导出与上的有关的模糊相似关系. 表示上的模糊相似关系矩阵，其中.

通常，隶属度rb（xi，xj）由以下方法定义[43]：1）定量乘积法；2） 角余弦法；3） 相关系数法；4） 封闭法；5） 距离法 和6）连接法。其中，大部分文献[36]、[39]、[42]、[44]都采用了连接法，计算公式如下：. 本文采用连接法。

模糊相似关系导致一般的模糊划分。

定义10： 给定和由模糊相似关系导出的的一般模糊划分定义为:

其中，被称为由模糊相似关系生成的模糊粗糙粒子.

显然，是上的模糊集。我们有.如果，那么意味着肯定属于.如果，那么意味着肯定不属于.模糊粗糙粒子的基数由以下公式计算：.我们可以确定.

定义11： 对于，其中. 对于，的下近似和上近似关于是上的一对模糊集，其隶属函数分别为

如上所述，对于和模糊相似关系，我们可以得到模糊粗颗粒。在计算的离群因子之前，首先计算的离群度，然后根据的离群度定义的离群因子。一般来说，对象的异常值因子越大，越有可能成为异常值。

为了计算给定模糊粗糙粒子的离群度，定义了FRS的近似精度。近似精度是RST[45]中的一个重要概念，用于从粗糙边界的角度分析集合的粗糙度。在此基础上，基于FRSs的近似精度定义如下。

定义12： 对于，其中，设.对于且，KaTeX parse error: Double subscript at position 8: [x_i]_R_̲B相对于的近似精度定义为

在此，我们使用近似精度来定义模糊粗糙粒子的离群度。对于给定的，我们计算了相对于一组模糊相似关系的逼近精度。如果这些关系的逼近精度总是很低，那么我们可以考虑作为异常对象，因此的离群度会很高。

对于，目前大多数离群点检测方法只给出的一个二进制属性，也就是说，是或不是异常值[10]，[24]。在许多情况下，为指定异常值因子更有意义。在下一节中，与上述想法类似，我们将介绍两个概念：1）GOD；2）FRGOF. GOD用于量化给定模糊粗糙粒子的离群度，FRGOF用于表示给定对象的离群度。

定义13： 设.对于，的定义为

在定义13中，我们使用来度量模糊粗颗粒[xi]rb的离群度。由于可以用来测量的不确定度，我们用它来计算。给定上的一组模糊相似关系，如果这些关系的近似精度总是很低，那么我们认为的行为不正常，将很高。

为了计算各种模糊相似关系的近似精度，我们不应尝试检查的所有子集，因为的每个子集确定上的模糊相似关系，因此我们将获得模糊相似关系。计算这些关系的所有近似精度是不切实际的，因为时间复杂度将与成指数关系。因此，我们只计算和的近似精度.

定义14： 对于，的可以定义为

每个可以确定一个，然后我们可以在它上面得到一个GOD，所以有个GOD。计算所有GOD的离群因子也是不切实际的，因为时间复杂度与成指数关系。因此，在定义14中，我们只使用由决定的个GOD去计算。

定义14中的权重函数符合离群点检测始终涉及数据集中少量对象的观点，并且这些对象更可能是离群点。从定义14可以看出，的权重越高，的越大，因此少数对象的权重应高于大多数对象。对于，如果的基数小于其他模糊粗糙粒子的基数，则我们将视为中的少数对象，并赋予更高的权重。

方程式（10）和（11）源自霍金斯的离群值观点，即，如果相对于中的其他对象具有一些异常特征，那么我们可以将视为中的异常值。在（10）和（11）中，不确定性被视为异常特征。如果始终保持很高，那么我们可能会认为没有正确地执行，并且的离群度会相当高。因此，在（11）中，的异常度与成正比。

定义15： 设为给定阈值，例如，如果，那么我们称为基于模糊粗糙颗粒的离群值。

到目前为止，我们已经建立了一个称为FRGOD的广义离群点检测模型。构建模型的路径包括五个部分：1）FRS模型；2） 近似精度；3） GOD；4） FRGOF；离群点检测。FRGOD模型具有很强的泛化能力，因为不同的和可以得到不同的FRS模型，所以可以得到不同的FRGOD模型。随后，将分析具体的FRGOD方法。

对象的描述通常在大小和尺寸上有所不同。为了获得准确的数据处理结果并避免不同数据的影响，我们必须首先规范化原始数值属性值[30]，本文使用最小-最大规范化。其计算公式如下：

其中和是属性的最大值和最小值。标准化后，这些属性的属性值在范围内。

为了有效地处理标称，数值和混合属性数据，对象和之间关于属性的混合模糊相似度计算如下：

式中，是可调整模糊相似度的半径，计算公式为，其中是属性值的标准偏差，默认参数用于调整模糊相似度半径。显然，这里，并且，所以是一个模糊相似关系矩阵。

我们设置和。当对象之间的关系为清晰等价关系，待逼近对象子集为模糊集时，模型退化为粗糙模糊集模型；如果待逼近对象子集清晰，对象之间的关系为模糊相似关系，则该模型为FRS模型；此外，当两者都是清晰的等价关系时，它是一个RS模型。这些特性将使FRGOD模型适用于混合属性数据中的离群点检测。

B. Specific Algorithm 具体算法

在这一部分中，我们设计了一个具体的FRGOD算法并分析了其复杂性。

算法1通过四个“ for ”循环获得OS。第一个for循环计算单个属性的模糊关系矩阵。第二到第四个嵌套for循环计算GODs和相应的权重，并基于模糊粗糙粒子进一步计算离群因子。因此，步骤2-4的循环数为，步骤3的循环数为。同样，步骤5-22的循环数为，步骤6-17的循环数为，步骤11-14的循环数为. 因此，算法1的循环总数为. 因此，在最坏情况下，算法1的时间复杂度为，空间复杂度为。为了更清楚地解释算法1的处理，在图1中描绘了其流程图。

IV. EXPERIMENTS AND COMPARATIVE ANALYSES 实验与比较分析