形式概念分析是一种处理数据的手段[1]，其显著特点是用Hasse图以可视化方式展示概念含义，这一特点使概念格应用于数据处理[2-4]、疾病防控[5-7]、机器学习[8-11]及其他领域[12-15]．形式概念分析之目的是挖掘以形式背景表述的数据，其知识表示的内容为概念，知识提取的平台是形式背景下所有概念组成的格结构，即概念格．所以形式概念分析在处理数据的过程中重要的一步是将以形式背景表述的数据转换为以概念形式表述的知识．因此，许多学者提出不同的算法[16-18]，用于挖掘形式背景中蕴含的概念．在实际应用过程中，不仅须要挖掘形式背景所蕴含的概念，而且须要对概念格中每个层面的概念所蕴含的知识进行挖掘，用于对同一知识层面单独加以研究．例如在学校中，须要通过德、智、体、美、劳各项指标的成绩对不同水平的学生进行因材施教，这样才能最大限度地提高学生的综合能力．若将学生视为对象，德、智、体、美、劳分别视为不同的属性，则可建立形式背景用以记录学生的不同指标成绩，进一步地，可用此形式背景生成的概念格，得到学生能力总体分布情况．另外，若想针对性地对学生进行教育，则须要对于不同水平的学生采取不同的措施，即对于概念格中不同层次的学生进行研究，处于同一层次的学生采用同一手段．这些实际案例说明在客观现实中须要既能从宏观角度将形式背景转换为概念格，又能从具体方面输出不同知识层面及每个知识层面中所包含概念的方法．而已有的生成概念格的方法[16-18]只能输出概念格，然后由用户从格结构中找到所有的知识层面，不能将宏观的概念格与具体的知识层面同时输出．从而导致用户若想得到概念格的知识层面，须要将宏观的概念格结构“重新”生成一遍，增大了用户找到所需知识层面的时间，降低用户提取知识层面的兴趣体验．为解决这一问题，本研究提出一个知识分层(KL)算法，不仅从宏观角度将形式背景生成概念格的Hasse图，而且将概念格的不同知识层面及层面中的知识一并输出，并通过与一些经典著名的生成概念格算法对比，结果表明该算法更具优势．1 概念与符号首先给出本研究所需形式概念分析中的概念及所需符号，更多关于形式概念分析的概念见文献[19]．1.1　形式概念分析的概念以下内容a～d来自文献[19]．a．一个形式背景(O,T,R)由集合O与集合A及二元关系R组成，且R⊆O×T．O与T中的元素分别称为对象与属性．b．设(O,T,R)是一个形式背景，对于集合A⊆O与集合B⊆T，定义：A'={m∈T|(∀g∈A)gRm}；B'={g∈O|(∀m∈B)gRm}．若A'=B，A=B'，则称(A,B)是一个概念，全体概念用β(O,T,R)表示．c．设(O,T,R)为一个形式背景．对于概念(A1,B1)，(A2,B2)，若A1⊆A2（B2⊆B1），则记为(A1,B1)≤(A2,B2)．d．令(P,≤)为一个偏序集，其中P为一个集合，且x,y∈P．若x≤y，则称x被y覆盖，且记为x≺y．注：(β(O,T,R),≤)为一个偏序集，且为一个格，称为概念格．每个概念格可用其Hasse图表示．1.2　所需符号下面给出本研究需要符号与表示．a．对集合xi，记集合Xi={xi}'．b．任意集合T，对xi,xl∈T，若有Xi⊆Xl，则记xi≤xl．c．任意集合T，且xl∈T，若对∀xi∈T，都有xi≤xl，则称xl为集合T中的最大元．d．定义圆Cik(o,t)表示o与t这两个集合，Qk为由圆组成的集合，其中：k为圆Cik(o,t)属于集合Qk（k∈Z+）；i为圆为集合Qk中的第i个元素．圆Cik(o,t)可以以几何的形式表达，其中：o位于圆内，t位于圆右下侧，详见图1．10.13245/j.hust.241105.F001图1圆C11(o1,t1)，C12(o2,t2)，C13(o3,t3)e．若存在一段或多段直线不经过集合Qk与Qf中的圆连接圆Cim(o1,t1)与圆Cjn(o2,t2) (d≥m,n;f≤m,n)，则将连接圆Cim(o1,t1)与圆Cjn(o2,t2)的所有直线称为圆Cim(o1,t1)到圆Cjn(o2,t2)的路线．圆Cim(o1,t1)到圆Cjn(o2,t2)的路线中的每段直线称为路径，详见图1．连接圆Cim(o1,t1)与圆Cjn(o2,t2)路径最少的路线称为最短路线．f．若存在圆Cim(o1,t1)∈Qm到圆Cjn(o2,t2)∈Qn(mn)的路线，且路线中经过的圆皆为集合Csp(o3,t3)∈Qp(mpn)中的圆，则称圆Cim(o1,t1)能到达圆Cjn(o2,t2)，记为Cim(o1,t1)→Cjn(o2,t2)．g．在概念格β(O,T,R)的Hasse图中，若将每个概念中的两个集合用1.2节d中所定义的圆来表示，则将到达概念(O,∅)∈β(O,T,R)最短路线的路径数相同的概念称为同一知识层面的概念．从图1可得：a．存在一条经过圆C12(o2,t2)的路线连接圆C11(o1,t1)与圆C13(o3,t3)；b．C11(o1,t1)∈Q1，C12(o2,t2)∈Q2，C13(o3,t3)∈Q3；c．C11(o1,t1)→C12(o2,t2)→C13(o3,t3)．2 KL算法的步骤对于任一形式背景(O,T,R)，给出如何寻找其概念格β(O,T,R)和β(O,T,R)的每一知识层面，及知识层面中所有的概念知识的算法——KL算法，具体如下．输入 (O,T,R)#yj∈O,xi∈T输出 β(O,T,R)的Hasse图H及β(O,T,R)的知识层面Qk#k为第k层知识层面步骤1 建立初始表．a．建立一个有两列的表格，其中第一列中的元素为xi∈T(属性列)，第二列中的元素为Xi(外延列)，并将表格命名为初始表．集合Ek为初始表外延列第k行单元格所含的元素，Ak为初始表属性列第k行单元格所含的元素．令A1=∅，E1=O，Ak=∅，Ek=∅，k≥2．b．令k=2．c．令集合m=∅．d．设xi为集合T中的最大元，令m=m+xi．e．令Ak=m，Ek=Ek+{Xi | xi∈m}．f．∀xi1，xi2∈Ak，Ek+1={X | X=Xi1⋂Xi2}．g．k=k+1．h．T=T-m．i．若T=∅，则停止并进入步骤1的j；否则回到步骤1的c．j．Mk={X | ∀X1，X2∈Ek-1，X=X1⋂X2}，Ek=Ek+Mk．k．若∀X1，X2∈Ek，有X1⋂X2=∅，则进入步骤1的o，否则进入步骤1的l．l．k=k+1．m．Ek={X | ∀X1 ， X2∈Ek-1， X=X1 ⋂ X2} ，Ak=∅．n．返回步骤1的l．o．取V=k，进入步骤2．步骤2 描出Hasse图的节点#集合o=t=∅．a．任取X∈Ek，Qk=∅，i=1．b．将o=X，o∈Cik(o,t)，若有x∈T，x'=X，则t=t⋃x，t∈Cik(o,t)，否则t=∅．Qk=Qk+Cik(o,t)．c．Ek=Ek-X．d．i=i+1．e．若Ek=∅，则进入步骤2的f，否则回到步骤2的a．f． k=k+1．g．若k0，则回到步骤2的a，否则进入步骤3．步骤3 连接所描的点#为方便下面说明，记集合Q=Q1⋃Q2⋃…⋃QV，其中V为步骤1中出现的V(即初始表有V行)．a．∀Ci1k1(o1,t1)，Ci2k2(o2,t2)∈Q．b．若集合t1⊆t2，则连接两个圆，否则不连．c．若集合Q中任意圆都已两两相互判断，则进入步骤4，否则重回步骤3的a．步骤4 删除多余的连线．a．k=1，i=1．b．∀Cik(o,t)∈Qk，Cjm(o,t)∈Q-Qk．c．若Cjm(o,t)此前被选中过，则返回步骤4中的b，否则进入步骤4中的d．d．若圆Cik(o,t)→Cjm(o,t)，则进入步骤4中的e，否则返回步骤4中的b．e．若圆Cik(o,t)有多条路线能到达Cjm(o,t)，且存在一条仅一段路径将圆Cik(o,t)与Cjm(o,t)相连的路线，则删除此只有一段路径的路线，否则保留圆Cik(o,t)到圆Cjm(o,t)的所有路线．f．i=i+1．g．若Qk中仍有圆未判断，则返回步骤4中的b，否则进入步骤4中的h．h．k=k+1．i．若k≤V则返回步骤4中的b，否则进入步骤5．步骤5 标注属性．a．k=1．b．i=1，j=1．c．若Qk中的圆Cik(o1,t1)能到达Qk+1中的圆Cjk(o2,t2)，则o2=o2+o1．d．j=j+1．e．若Qk+1中所有圆被判断，则进入步骤5中的f，否则回到步骤5中的c．f．i=i+1．g．若Qk中所有圆被判断，则进入步骤5中的h，否则回到步骤5中的c．h．k=k+1．i．若k≤V-1则返回步骤5中的c，否则输出图H及Qk．第k层知识层面所对应的概念即为集合Qk中的元素．以下对KL算法的正确性及算法复杂度进行分析，并且将KL算法与一些经典的、优秀的算法进行对比．3 KL算法的分析首先对算法的正确性进行分析，其次对其时间算法复杂度进行分析，最后将其与Nextclosure[18]等著名的生成概念格的算法进行对比，来说明KL算法在输出概念格及知识层面的优势．3.1　KL算法的正确性定理1 ∀Cjm(o,t)∈Q，(o,t)为概念．证明 用数学归纳法证明．∀Ci1(o,t)∈Q1，由KL算法步骤1中的d步可知o'=t，t'=o，所以根据1.1节中a给出的概念的定义可知(o,t)是个概念．不妨设∀Cik-1(o2,t2)，Clk-1(o3,t3)∈Qk-1，(o2,t)2，(o3,t3)是概念．对于∀Cjk(o1,t1)∈Qk，由KL算法可知o1=o2⋂o3，t1=t2+t3．(o2⋂o3)=o2'⋃o3'=t2+t3=t1．再根据1.1节中b可知(t2+t3)'=o2⋂o3，有o1'=t1，t1'=o1，所以根据1.1节中a给出的概念的定义可知(o1,t1)是概念．由于k的任意性，得∀Cjm(o,t)∈Q，因此(o,t)是概念．定理2 概念格β(O,T,R)中的所有概念均在集合Q中．证明 用反证法来证明．不妨设存在概念(o,t)，满足C(o,t)∉Q，在此作如下假设．a．若不存在概念(o1,t1)，满足C(o,t)→C(o1,t1)→C(O,∅)，则xi∈t为t的最大元，则由KL算法步骤1中的d和e可知o∈Ek，再由KL算法步骤2中的c和1.1节中的b可得C(o,t)∈Q，与假设矛盾．b．若存在概念(o1,t1)，满足C(o,t)→C(o1,t1)→C(O,∅)，则由1.1节中的b可知，存在C(o2,t2)C(o3,t3)…C(on,tn)，满足：(o2,t2)(o3,t3) … (on,tn)是概念；o2⋃o3⋃… ⋃on = O及t2⋃t3⋃  … ⋃tn = A ；圆C(o2，t2)C(o3,t3)…C(on,tn)到达圆C(O,∅)最短路线包含的路径数为1．由定理2的a可知C(o2,t2)C(o3,t3)…C(on,tn)∈Q，又根据KL算法步骤1中f及定理2的b可知o2⋃o3⋃…⋃on=O，再由KL算法的步骤2中c及1.1节中的b可得C(o,t)∈Q，与假设矛盾．综合上述定理2的a与b可得假设不成立，即(O,T,R)经KL算法处理后，(O,T,R)下的所有概念均在集合Q中．集合(Q,≤)为概念格，则图H为(Q,≤)的Hasse图．3.2　算法的时间复杂度分析为方便说明，设算法输入端的形式背景(O,T,R)中|O|=m，|T|=n．KL算法的复杂度分析如下．a．KL算法的步骤1是找出T中的最大的xi，因为|T|=n，所以步骤1中寻找最大的xi最多须要循环n次，找到xi后还须找到Xi，因为|O|=m，从而找出一个Xi须要判断m次．随后将Xi两两相交，由于共有n个Xi，最多须要相交(n-1)/2次，因此完成步骤1最多须要循环m×n2×(n-1)/2次．b．KL算法的步骤2是描出初始表中外延列中的元素，由于这些元素是步骤1中Xi两两相交而来，且|T|=n，外延列中最多有(n-1)/2个元素，因此步骤2最多循环(n-1)/2次．c．KL算法的步骤3是对圆进行连线，若存在圆Cia(o1,t1)与圆Cjb(o2,t2)满足集合t1与t2为包含关系，则连接圆Cia(o1,t1)与圆Cjb(o2,t2)，否则不连接这两个圆，由步骤2可知最多有(n-1)/2个圆，因此至多须要连接[(n-1)/2]2次，所以步骤3最多循环[n×(n-1)/2]2次．d．KL算法的步骤4是须要删除多余的路径，这须要每个圆与Q中的其他圆进行对比，因为Q有(n-1)/2个圆，最多须要判断[n×(n-1)/2]2次，所以步骤4最多循环[n×(n-1)/2]2次．e．步骤5是须要对圆Cia(o1,t1)中的集合o1赋值．若存在两个圆有路线连接则赋值，否则不赋值，因为最多有(n-1)/2个圆，所以步骤5最多须要循环[n×(n-1)/2]2次．综上所述，KL算法最多须循环T(n)= [n×(n-1)/2]2×3+(n-1)/2+m×n2×(n-1)/2次，又因为lim(m,n)→(∞,∞)m×n4/T(n)=1/4，所以T(n)∈O(m×n4)，故KL算法的时间算法复杂度为O(m×n4)．3.3　与其他算法的对比为方便说明，本研究将文献[16]第67页给出的经典的算法简记为算法F，将文献[17]中给出的近期生成概念格的新算法简记为算法I，将Nextclosure[18]算法简记为算法N．下面将KL算法与算法F、算法I和算法N进行对比，结果见表1．10.13245/j.hust.241105.T001表1KL算法与算法F、算法I和算法N对比算法算法复杂度是否有Hasse图是否输出知识层面KLO(m×n4)是是FO(m2×n)否否IO(m×n5)否否NO(m2×n3)否否通过表1，可以得到如下结论．a．KL算法与算法N相比，KL算法的复杂度为O(m×n4)，而算法N为O(m2×n3)，当研究对象较大时，m≪m2．但是当形式背景中研究属性不是很大时，n4与n3区别不是很大，说明KL算法当处理数据的对象较大而所属性不大时，处理数据的速度快于算法N．b．KL算法与算法F相比，算法F的复杂度为O(m2×n)，同样当研究对象较大时，m≪m2．但是当形式背景中研究属性不是很大时，n4与n区别不是很大，说明KL算法当对象较大而所属性不大时，处理数据的速度快于算法F．c．KL算法与算法I相比，算法I的复杂度为O(m×n5)，当研究属性较大时，n4≪n5．而由于m=m，因此属性的规模对KL算法与算法I有相同效果的影响，说明KL算法当处理数据的对象较大时，处理数据的速度快于算法I．d．另外，KL算法可以同时输出Hasse图与每个知识层面及每个知识层面拥有的所有概念知识，而算法F、算法I及算法N都不具备此优点．4 应用案例以某学校须要针对学生的的德、智、体、美、劳等成绩进行因材施教为背景，利用KL算法输出学生成绩的总体分布情况及从知识层面上对学生进行分层．给出记录学生各项成绩信息的形式背景，见表2．10.13245/j.hust.241105.T002表2学生各项成绩表学生abcdefg111111112000011031010000410001115101110160111110注：为使生成的Hasse图更简洁，将语文用a，数学用b，英语用c，体育用d，音乐用e，劳动用f，科学用g，学生i用数字i(i∈{1,2,3,4,5,6})替代．由于学生1的每科成绩都合格，因此一定是基础最好的学生类别，则在对学生进行分层的过程中可以暂时排除．下面给出形式背景表2经KL算法所生成的初始表及经KL算法生成的表2的Hasse图．初始表见表3．10.13245/j.hust.241105.T003表3初始表属性外延属性外延∅{2，3，4，5，6}{d}∅{e}{a}{c}{2，4，5，6}{3，4，5}{3，5，6}∅∅{f}{5}{4}{4，5}{f}{g}∅∅{f}{g}{4，5}{5，6}{3，5}{2，4，6}{4，5}{5，6}∅{g}{b}∅∅{b}{6}{5，6}{6}{5}{4}{6}经KL算法生成的表2的Hasse图见图2．10.13245/j.hust.241105.F002图2表2的Hasse图由图2可以看出：第1层知识层面中含有的概念是 ({2，4，5，6}，{e})，({3，4，5}，{a})和({3，5，6}，{c})；第2层知识层面中含有的概念是({2，4，6}，{e，f})，({3，5}，{a，c})，({4，5}，{e，a，g})和({e，d，c}，{5，6})；第3层知识层面中含有的概念是({4}，{e，a，f，g})，({5}，{e，a，g，d，c})和({6}，{e，f，d，c，b})．a．从知识层面可以看出：第三层学生基础最好，合格的科目最多，分别为学生4、学生5、学生6和学生1；第二层学生基础位于中游，分别为学生2与学生3；第一层学生基础最差，但是按此分类方法并没有学生在此层中．b．根据分层的结果：从学校角度，可以针对这些学生指定专门的有难度的可能进行学习；从教师的角度，可以对这些学生指定特定学习计划．5 结语本研究提出KL算法，将形式背景中的数据转换为可视化知识表达形式——Hasse图，同时获取每个知识层面，为利用概念格进行知识提取并获取每个层面提供了更为可适的手段，进一步为概念格理论的应用提供了可扩充的理论依据．虽然从是否生成Hasse图与知识层面的角度，KL算法有绝对的优势，但是在算法复杂度上，KL算法略微高于已有生成概念格的某些算法，这个劣势当数据量较小或对象集的数据较小时并不明显，但是当数据量较大，特别是属性集的规模较大时，KL算法速度方面的劣势则会显现，这将在未来工作中加以改进．