推荐星级:
- 1
- 2
- 3
- 4
- 5
三支概念的构建算法
资料介绍
新发展出的三支概念分析理论目前还没有具体的三支概念构建算法.针对此问题,提出了一种构建三支概念的算法CbO3C.CbO3C借鉴形式概念分析中构建形式概念的CbO算法的思想,并通过使用基于部分闭包的正则检测和失效正则检测进行剪枝,使用约简条件排除非核心的三支概念,使用位操作实现集合运算等技术来提高效率,降低内存开销.文中对UCI数据和随机数据进行了实验.实验结果表明,算法可以准确、有效地计算出给定形式背景的所有核心三支概念.
部分文件列表
文件名 | 大小 |
三支概念的构建算法.pdf | 1M |
部分页面预览
(完整内容请下载后查看)(
)
西安电子科技大学学报 自然科学版
年
月
2017 2
Feb.2017
第
卷
第
期
1
44
Vol.44 No.1
JOURNAL OF XIDIAN UNIVERSITY
doiꢁ10ꢂ3969ꢃꢂissnꢂ1001-2400ꢂ2017ꢂ01ꢂ013
j
三支概念的构建算法
,
汪 文 威 祁 建 军
(
,
)
710071
西安电子科技大学 计算机学院 陕西 西安
:
,
摘要 新发展出的三支概念分析理论目前还没有具体的三支概念构建算法 针对此问题 提出了一种构建
.
,
算法的思想 并通过使用基于
CbO
三支概念的算法
借鉴形式概念分析中构建形式概念的
CbO3C.CbO3C
,
,
部分闭包的正则检测和失效正则检测进行剪枝 使用约简条件排除非核心的三支概念 使用位操作实现集
,
,
合运算等技术来提高效率 降低内存开销 文中对
数据和随机数据进行了实验 实验结果表明 算法可
.
UCI
.
、
以准确 有效地计算出给定形式背景的所有核心三支概念
.
:
;
;
;
关键词 三支概念分析 形式概念分析 形式背景 算法
:
TP18
:
A
: ( )
文章编号
1001-2400201701-0071-06
中图分类号
文献标识码
Alorithmforconstructin three-wa concets
g
g
y
p
WANG WenweiꢀQIJianun
j
SchoolofComuterScienceandTechnolo ꢅXidianUnivꢂꢅXi'an 710071ꢅChina
gy
ꢆ
ꢄ
p
Abstract: Thetheorofthreewaconcetanalsisisnewldeveloedꢅbutsofarthereisnoconcrete
y p y y p
y
-
alorithmforconstructin threewa concetsꢂInordertosolvethis roblemꢅathreewa concet
y p y p
g
g
p
-
-
constructionalorithmnamedCbO3Cisfirstl roosedinthisaerꢂTheCbO3Cadotstheideaofthe
ypp pp
g
p
constructionalorithmCbOofformalconcetsinformalconcetanalsisꢂAtthesametimeꢅinorderto
p y
g
p
imrovetheefficiencandlowerthememoroverheadꢅtheCbO3Cemlostheartialclosurecanonicit
py p y
p
y
y
testandinheritedfailuretesttoreducethereeatedcomutationsofthreewa concetsꢅaliesthe
y p pp
p
p
-
reductionconditiontofilterthenoncorethreewaconcetsꢅandimlementssetoerationsonthebasisof
y p
p
p
-
-
bitsꢂTheexerimentswithUCIandrandomdatasetsshowthattheCbO3Ccancorrectlandefficientl
y
p
y
calculateallcorethreewaconcetsofaformalcontextꢂ
y p
-
Ke Words: threewaconcetanalsisꢇformalconcetanalsisꢇformalcontextsꢇalorithms
y p y p y
g
y
-
[]
提出的形式概念分析
1
(
, )
主要研究内容是形式背景及以形式背景
文献
FormalConcetAnalsisFCA
p y
,
作为数据分析的一种重要方法 以形式背景中属性和对象的二元关
为基础形成的形式概念和概念格
.FCA
,
,
、
、
在数据挖掘 知识管理
Web
系为基础建立形式概念 并分析其隐含信息 建立概念格
服务等众多领域
.FCA
[ ]
2-4
再经多人研究与实践 形式概念的构建算法[ ]已比较成熟
,
.
5-6
有着广泛的应用
.
,
,
支持二支决策即考虑接受和拒绝两种选择 此时不接受就等同于拒绝 不拒绝就等同于接受 然而
FCA
.
,
、
,
、
实际应用中却非如此 例如日常生活中的投票可以选择赞成 反对或弃权 而在医疗诊断中则是治疗 不治疗
,
或进一步诊断 与之对应的理论即三支决策
.
[]
为具有三个选项的决策问题提出的一个与学科无关的统一框架 作为二支决策
三支决策理论是文献
7
.
[]
7
,
、 、
,
近些年已有许多
理论的一个推广 三支决策理论根据某个评判准则将决策分为接受 拒绝 不承诺 大类
3
[ ]
8-10
与其相关的研究及应用
.
:
:
2016-05-23
收稿日期
网络出版时间
2015-12-16
:
(
,
);
陕西省自然科学基础研究计划资助项目
(
)
基金项目 国家自然科学基金资助项目
1137101411071281
2014JM8306
:
(
1991ꢀ
), ,
男 西安电子科技大学硕士研究生
, :
E-mailwwwanxd@163.com.
g
作者简介 汪文威
:
(
1970ꢀ
), ,
男 副教授
,
:
通信作者 祁建军
E-maili@mail.xidian.edu.cn.
qjj
: ://
/ / /
网络出版地址
htt www.cnki.netkcmsdetail61.1076.TN.20160523.1727.026.html
p
(
)
西安电子科技大学学报 自然科学版
第
卷
44
72
, [ ]
结合三 支 决 策 的 思 想 文 献
(
,
ThreeWa ConcetAnalsis
y p y
将
拓 广 为 三 支 概 念 分 析
11-12 FCA
-
[
13-15
]
),
目前
,
提出两种新的概念构 建 形 式 即 由 属 性 导 出
已得到有关学者的关注
的三支概念及由对象导出
TWCA TWCA
.TWCA
(
, )
(
, )
的三支概念 三支概念与形式概念一
AttributeExortAE
ObectExortOE
j p
.
p
,
((,),) (,)
的外延 是
X Y A
样具有内涵和外延 但三支概念的内涵或外延本身也由两部分组成
概念
.AE
X Y
,
两个来自对象论域的对象子集组成的二元组 内涵 是一个来自属性论域的属性子集
概念可以同时表
A
.AE
(,(,))
示共同具有内涵 的对象子集 和共同不具有内涵 的对象子集
Y.OE
概念
的外延 是一个
A
X
A
X
A B
X
, (,)
来自对象论域的对象子集 内涵
是两个来自属性论域的属性子集组成的二元组
概念可以同时表
.OE
A B
示外延 共同具有的属性子集 和共同不具有的属性子集
B.
X
A
,
,
“
” “
”
. TWCA
相比形式概念 三支概念包含更多的信息 可以同时表示 共同具有 和 共同不具有 但由于
[ ]
5-6
,
,
是刚刚提出的新理论 目前还没有具体的三支概念构建算法 笔者借鉴形式概念构建算法
的思想
[]失效正则检测的基础上进
FCbO
.
CbO
[]部分闭包正则检测和算法
5
6
,
按字典序生成所有属性子集 在算法
InClose
-
,
,
行改进用以剪枝 使用约简条件排除非核心三支概念 最终提出三支概念的构建算法
考虑到三支概
CbO3C.
,
念的实际应用 算法
仅考虑给定形式背景的所有核心三支概念
.
CbO3C
三支概念分析简介
1
先给出形式概念的相关定义
.
(,,)
包括两个集合
U V R
,
以及二者之间的关系
定义
形式背景
和
中的每一个元素称为对
R.U
1
U
V
[ ]
16
,
,
, “ ”
读作 对象 具有属性
a .
象
子
中的每一个元素称为属性 对象 与属性 有关系
记为
V
.
x
a
R
xRa
x
,
,
针对给定的形式背景 为求某些对象共同具有的属性 给出算子的定义
.
(,,)
U V R
,
定义一对算
定义
设
是一个形式背景 对于任意的对象子集
和属性子集
2
.
X
U
A
V
⊆
⊆
[ ]
16
*
,:() () *:() (),
和
具体为
PU
PV
PV
PU
→
→
X*
v
v Rv
V X
( ) {
V ∀x X xRv
} ,
{
}
= ∈ | ∈
= ∈ | ⊆
*
A
{
( ) {
U ∀a A uRa
} ,
u
u U A uR
= ∈ | ⊆
{
}
= ∈ | ∈
,()
其中
表示幂集
·
P
.
,
以此为基础 给出形式概念的定义
.
[ ]
*
*, (,)
称 是
A X A
=
3
.
X A
16X
A
=
(,,)
U V R
(,)
定义
设
是一个形式背景 如果一个二元组
满足
且
X
,
,
称为概念的内涵
A
一个形式概念 简称概念 其中 称为概念的外延
.
X
.
[ ]
将定义 给出的
,
中传统的算子称为正算子 相应地 负算子定义如下
. .
文献
11
2
FCA
(,,)
,
定义一对负算
定义
设
是一个形式背景 对于任意的对象子集
和属性子集
4
U V R
.
X
U
A
V
⊆
⊆
[ ]
11
*
,:() () *:() (),
子
和
具体为
PU
PV
PV
PU
→
→
c
X*
v
V ∀x
X
v
V
X
(( )) {
xRv
} ,
Rv
{
}
= ∈ | ∈
= ∈ | ⊆
*
A
c} ,
u uR
= ∈ | ⊆
{
(( )) {
u
U ∀a
A
uRa
U A
{
}
= ∈ | ∈
[ ]
11
其中 c 是 的补关系 类似地 负算子也可定义概念 若
为
概念
为了区
.
*
*
,
R
,
, , (,)
则称
R
.
. X
A X A
X A N
=
=
,
别三支概念 形式概念和 概念都被称为二支概念
N
.
,
在正负算子的基础上 可以定义三支算子
.
(,,)
是一个形式背景 对任意对象子集
,
X Y
,
定义一对
V
定义
·
设
和属性子集
算
AE
5
U V R
.
U
A
⊆
⊆
<
>
,:() () ·: () (),
[ ]
11
子
和
具体为
PV
DPU
DPU
PV
→
→
<
A·
A
A
(*,*) ,
=
>
·
V v X*
v
Y*
X* Y*
= ∩
.
{
(,)
X Y
v
{
}
<
·
= ⊆ | ∈ ∧ ∈
>
, ,
A B
,:() () ·: () (),
对 任意对象子集
具体为
和属性子集
定义一对
算子
和
DPV
X
U
V
⊆
OE
PU
DPV
PU
→
⊆
→
://
http www.xdxb.net
全部评论(0)