基于区间值犹豫模糊形式背景的信息提取方法研究

张嘉德,金子涵

(河北大学 数学与信息科学学院,河北 保定 071000)

0 引言

随着网络上数据获取、数据通信和数据存储技术的迅猛发展,网络中积累了大量的图书信息数据。这些数据中不仅包含着许多有价值的信息,也包含着大量的冗余信息。面对规模日益庞大的数据,如何去粗求精从数据中有效地提取有价值的信息成为一个具有重大现实意义的问题。在这种背景下,机器学习、数据挖掘等技术得到了广泛应用,大量的知识发现方法应运而生。

形式概念分析(Formal Concept Analysis) 由德国数学家R.Wille[1]提出,作为一种针对知识发现的有力工具,已被广泛应用在各个领域,如人工智能、软件工程、信息检索、关联规则挖掘等[2-3]。形式概念(下文简称“概念”)是一个有序对(外延,内涵),其中外延是一些对象的集合,描述了概念所涵盖的对象；内涵是一些属性的集合,描述了概念的所有特征。在所有概念组成的集合上定义了一个泛化—例化的偏序关系,使之成为完备格,称之为概念格。

经典FCA只能处理确定性数据,但是现实世界的数据往往具有不确定性,如何从不精确、不一致、不完备的网络图书数据中获取人们需要的知识,是广大学者一直关注的问题[4]。模糊集理论可以有效地处理不确定性数据,且FCA与模糊集理论具有很强的互补性,将FCA与模糊集理论结合起来研究,得到模糊形式概念分析可以更加有效地表达和处理不确定性知识[4]。

西班牙学者Torra[5]于2009年提出了犹豫模糊集(HFS),它是模糊集的一种推广。犹豫模糊集使用了一些可能的值而不是某一值去刻画隶属度,所以能够反映决策者的犹豫不确定性,因而比其他模糊集理论更实用和更合适。此后,蔡丽娜[6]根据HFSs的性质,将区间值运用到犹豫模糊集,给出了区间值犹豫模糊集(IVHFS)的定义。本文主要以区间值犹豫模糊集(模糊集的一种拓展形式)为主要工具来处理不确定性数据,借助Godin算法[7]讨论概念格的生成,以期为网络图书信息的提取提供一种可行的分类方法。

1 预备知识

1.1 区间值犹豫模糊集

定义1.1.[6]设X为一个非空分明集合,单位闭区间[0,1]上的全体闭区间为[I],则称映射˜A:X→[I],x→˜A(x)为X上的区间值模糊集,X上的全体区间值模糊集记为IF(X)。

定义1.2.[6]设X为一非空集合,则关于X的区间值犹豫模糊集为:

1.2 概念格

定义1.4[1](1)K=(G,M,I)被称为形式背景,其中G表示非空的有限对象集合,M表示非空的有限属性集合,I是从G到M的一个关系,即I⊆G×M, 且∀x∈G,∀a∈M,(x,y)∈I表示“对象x具有属性a”。

(2)对于X⊆G及B⊆M, 定义:

f(X)={m∈M|∀x∈X,(x,m)∈I},g(B)={x∈X|∀b∈B,(x,b)∈I}。

如果X,B满足f(X)=B,g(B)=X, 则称二元组(X,B)是一个概念,X是概念(X,B)的外延,B是概念(X,B)的内涵。由K=(G,M,I)生成的所有概念组成的集合,记为β(G,M,I)。

(3)任取两个概念(X,B)与(Y,C),如果X⊆Y(等价于B⊇C),记为(X,B) ≤ (Y,D), 并称(X,B) 是(Y,C)的子概念,或称 (Y,C)是(X,B)的父概念 。所有概念按着偏序关系“⊆”构造成一个完备的概念格,记为(β(O,P,I), ≤),一般用Hasse 图表示。

2 基于区间值犹豫模糊形式背景的概念格的构造方法

下面主要定义区间值犹豫模糊形式背景,并给出相关算法。

定义2.1.K=(G,M,V,)被称为区间值犹豫模糊形式背景,当且仅当G为有限对象组成的非空集合,M表示有限属性组成的非空集合,V表示所有犹豫模糊元可能取值的区间值集合,模糊关系是从G×M到V的一个映射,即

事实上,这里所讨论的概念格的构造方法是建立在区间值犹豫模糊集和概念格的基础之上的。具体如下,我们首先将区间值犹豫模糊背景转化为经典形式背景,进而通过经典概念格的构造方法,得到全部概念信息。算法框架如图1所示。

图1 算法框架

算法步骤具体如下:

Step1. 对于区间值犹豫模糊形式背景所对应的表格中的每一个单元格里的区间集合(即区间值犹豫模糊元),计算每个区间值的左右端点值的平均值,由此将区间值犹豫模糊形式背景转化为犹豫模糊形式背景。

Step2. 将犹豫模糊背景所对应的每一个单元格的值,计算平均值,从而可将犹豫模糊形式背景可转换为模糊形式背景。

Step3.对应于每一属性,设置信度阈值。对于每一个对象g所在行的单元格的值,将低于相应置信度阈值的值设置为零,表示该对象不具有相应属性；否则,设置为1,表示该对象具有此属性。执行完此步骤,可得到一个经典实形式背景。

Step4. 简化经典实形式背景。相同的行(或列)认为是等价的,即将等价的行和列删除,得到净化的经典形式背景。

Step5. 对于经典形式背景,采用经典概念格的Godin增量算法,生成所有概念节点,得到初始的概念格。

Step6. 将删除的对象和属性添加到概念格中,并绘制Hasse图。

3 算法在图书信息提取中的应用

下面将新给出的概念格构造方法应用于图书信息提取,试验结果证明这种方法是行之有效的。

现从一个网络图书网站,搜集了与5本书(g1,g2,g3,g4,g5)相关的、来自于21位读者的评分信息。对于这21位读者,其中25岁(含25岁)以下7人,25岁至35岁(含35岁)7人,35岁至55岁7人。已知这个图书网站有自己的一套评分系统,评分范围为5个评分等级:五星,四星,三星,二星,一星,分别记作m1,m2,m3,m4,m5。注意:这里分别对这3类人的评分信息进行统计,评分值以3个区间值形式呈现。

事实上,所得数据(见表1)实为一区间值犹豫模糊形式背景K=(G,M,V,),其中

表1 区间值犹豫模糊形式背景

运行我们所提出的算法,可得全部概念如下:

第0层:D0: ({g1,g2,g3},{})；

第1层:D1: ({g1,g2},{m1,m5}),D2: ({g1,g3},{m3})；

第2层: D3: ({g1},{m1,m3,m5}),D4: ({g2},{m1,m4,m5}), D5:( {g3},{m2,m3})

第3层:D6: ({},{m1,m2,m3,m4,m5})；

所构造的概念格如图2所示:

图2 应用所提算法生成的概念格

分析所得概念格信息,可为网站和读者提供有价值的信息。例如,通过概念D2:( {g1,g3},{m3})

我们可知,对于g1,g3这两本书,读者评分可能均为三星。对于概念D3: ({g1},{m1,m3,m5}), 可知读者对g1这本书,评分可能是五星、三星或一星3种情形。注意:阈值选择不同,得到的概念格可能不同,即阈值对概念格有关键作用。因而,在实际应用中,为了反映更真实的概念格,应该谨慎选择阈值。

4 结语

本文提供了一种基于区间值犹豫模糊形式背景的概念格提取方法,并将之应用于网络图书信息的提取,实例证明该方法是可行的,并能为读者提供有价值的建议。下一步工作可提供一种不依赖于Godin算法的、生成的概念是区间值犹豫模糊概念的、有效的信息提取方法。