ChooseinitialseedeventsfromE

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Choose initial “seed” events from E,Determine a star for each seed against the other seed events,By appropriately modifying and selecting complexes from stars,construct a disjoint cover of E that optimizes the criterion LEF,Is the termination,Criterion satisfied?,END,a,Given: E-a set of data events k-the number of clusters LEF-the clustering quality criterion,Y,N,1,Is the clustering,quality improving?,Choose k new seeds which,Are central events,Choose k new seeds which,are “border” events,a,Y,N,2,e1,e2,X1 X2,0,1,2,X4,X3,0 1 2,3,Event,X1,X2,X3,X4,e1,0,a,0,1,e2,0,b,0,0,e3,0,c,1,2,e4,1,a,0,2,e5,1,c,1,1,e6,2,a,1,0,e7,2,b,0,1,e8,2,b,1,2,e9,2,c,0,0,e10,2,c,2,2,Variable Type:,L,S,L,N,4,d,f,a,b,c,K=2 ; LEF-sparseness, Complexity; Termination criterion:base=2,probe=2,Iteration 1,Step 1:,Select seed: e1,e2,Step 2:,Produce Stars: RG(e1|e2,m) RG(e2|e1,m) m=5,RG(e1|e2,m)=x2=ax3=01,X4=1 2,RG(e2|e1,m)=x2=b c,x4=0 2,5,Generalize:,RG(e1|e2,m)=x2=ax31,X4=12,RG(e2|e1,m)=x2=f,x4=02,Step 3:,Evaluation and Modification(disjoint),Sparseness Complexity,Complex 1: x2=ax31 15 2,Complex 2: x2=f 47 1,62 3,(b) Complex 1: x4=12,Complex 2: X2=f,(c) Complex 1: x2=ax31,Complex 2: X4=02,6,(d) Complex 1: x4=12,Complex 2: x4=02,Step 4:,The termination criterion is tested,Step 5:select new seeds,e1,e4,e6 e2,e3,e5,e7,e8,e9,e10,Central events: e4,e8,Iteration 2,Step 2:,Produce satrs RG(e4|e8,m ), RG(e8|e4,m),RG(e4|e8,m)=x2=ax31,x11x3 1,x3=0,RG(e8|e4,m)=x1=2,x2=f,x31,7,sparseness Complexity,Complex 1: x11x31 31 2,Complex 2: x1=2 22 1,53 3,Step 4:,Termination criterion is tested (the last of the base iterations),Step 5:,e1,e2,e3,e4,e5 e6,e7,e8,e9,e10,New seeds: e1,e8,Iteration 3,The iteration produces the same clustering as iteration1,Step 4: Termination criterion is tested (the first of the two probe,Stp 5: not better than the previous one, border events are selected,8,New seeds e2,e6,Iteration 4,Produces a new clustering:,Sparseness Complexity,Complex 1: x31 49 1,Complex 2: x3=0 22 1,71 2,结果：,x11x3 1,x1=2,9,e,1,e,2,X1 X2,0,1,2,X4,X3,0 1 2,10,知识发现,S1 S S2 S F1=Cover(S1,S-S1) F2=Cover(S2,S-S2) 如果 S2 S1 S 则 F2 F1,11,知识发现算法,1）例子分类。由两种方法对例子集合分类：,层次分类。将已知例子集s依次分为一个树状的层次结构，S,s,1,.Sn,S1,1,S,1k,S,k1,S,kk,。其中Sij是Si的子集。,平行分类。令k=2,3,r,分别对同一个例子集S分类成k各子集，形成r个族，S, , 。,2)描述抽象。产生每个子集在整个例子集S中的描述。即,对层次分类，产生 , , 。其中Fi=Cover (Si,S-Si),Fij=Cover(Sij,S-Sij)。,对平行分类。产生 , 。其中,i=1,2,l, 及 l=2,r。,3)规则形成。先在第1)步产生的集合中寻找子集关系，然后在第2)步产生相应的描述间构造决策规则。,12,13,1）脚=蹄 奶=有 毛发=有，因S,12,S,1,2) 食物=肉羽毛=无脚=有爪 奶=有 毛发=有，因S,11,S,1。,3）会飞=是脚=有爪 羽毛=有，因S,22,S,2,14,机器发现：,BACON系统,基本定律：,增加定律：,如果变元,x,的值随着变元,Y,的值增加而增加，则定义比值,X/Y,并检验该比值是否为常数。,(2) 减少定律,如果变元,x,的值随着变元,Y,的值减少而增加，则定义乘积,XY,并检验该乘积是否为常数。,(3) 常数定律,如果,x,的值对于很大一个数量接近于常数，则假定,x,总具有这个值,15,