当前位置:文档之家› How to cluster evolving graphs

How to cluster evolving graphs

Project Number001907

DELIS

Dynamically Evolving,Large-scale Information Systems

Integrated Project

Member of the FET Proactive Initiative Complex Systems

DELIS-TR-382

How to Cluster Evolving Graphs Marco Gaertler and Robert G¨o rke and

Dorothea Wagner and Silke Wagner

2006

How to Cluster Evolving Graphs

(Extended Abstract)

Marco Gaertler,Robert G¨o rke,Dorothea Wagner,and Silke Wagner

Faculty of Informatics,Universit¨a t Karlsruhe(TH),

{gaertler,rgoerke,wagner,swagner}@informatik.uni-karlsruhe.de Abstract.Clustering is a frequently used tool in the analysis and evaluation of large and

complex networks.Most such networks result from or model dynamic processes,thus cluster-

ing techniques need to be adapted.We provide a model for clustering graphs that are subject

to changes.More precisely,we address the update problem,i.e.,maintaining the clustering

while nodes and edges can be inserted and deleted,as well as the issue of clustering graph

sequences.Furthermore,we give some illustrating examples and point out several pitfalls.

This work is a?rst step towards a sound foundation for clustering on evolving graphs.

1Introduction

The study of real-world networks,ranging from the Internet,the World Wide Web,net-works of sexual contacts,scienti?c collaboration networks,to metabolic networks,have recently identi?ed several prominent features—high clustering coe?cient,scale-free de-gree distribution,small-world characteristics,and degree-degree correlation.Furthermore, several studies[1,2]have pointed out that both natural and arti?cial networks that have innate self-organizing capabilities exhibit community structure.In general,networks are not static over time but are subject to an evolution either by design or as a result of changing circumstances.

Including the evolution of a network in the analysis of inherent community structure is a task that has not yet been well understood.In the following we de?ne models for the clustering of evolving networks.In particular we focus on two salient problems,the update of a clustering after a change in the network and the clustering of the graph that consists of a sequence of snapshots of an evolving network.Among the numerous applications for the update problem are social studies and the analysis of crystal growth,where large scale inhomogeneities are monitored during an evolutionary process.Clustering each state of the network from scratch may result in prohibitive computational costs,particularly in the case of online tasks.Obvious applications for the clustering of graph sequences are the identi?cation of microscopic and macroscopic trends in the community structure.Both for cause studies and for the prediction of future behavior,these analyses are invaluable.

This paper is organized as follows:In Section2,we present the necessary preliminaries such as structural operations,graph sequences,and the general clustering notation.The dynamic clustering problem is introduced in Section3alongside a short discussion.In Section4,we de?ne the clustering problem for graph sequences over time.We conclude the paper with Section5.

This work was partially supported by the DFG under grant WA654/14-3and EU under grant DELIS (contract no.001907)and CREEN project(contract no.012684).

2Preliminaries

Let G :={(V,E,ω)|E ? V

2 ,ω:E →R +}be the set of all undirected weighted graphs.

For a given graph G =(V,E,ω),?ve structural operations are de?ned:

deleteEdge (G ):= (V,E ,ω )∈G |?e ∈E :E =E \{e },ω =ω|E insertEdge (G ):= G ∈G |G ∈deleteEdge(G ) deleteNode (G ):= (V ,E ,ω )∈G ?u ∈V :V =V \{u },E =E ∩ V 2 ,ω =ω|E insertNode (G ):= G ∈G |G ∈deleteNode(G ) changeWeight (G ):= (V,E,ω )∈G |?e ∈E :ω |E \{e }=ω|E \{e }

A graph modi?cation is a mapping ?:G →G .It is called simple ,if the modi?cation can be expressed by one of the above structural operations or the identity function for all graphs.Let T ?N be a ?nite collection of nonnegative integers.For every t ∈T ,the immediate predecessor (successor)is naturally de?ned as the largest (smallest)integer t that is contained in T and smaller (larger)than t ,if such an element exists.Otherwise,we set it to t .A graph sequence is a mapping s :T →G .The sequence is simple ,if there exists a simple graph modi?cations ?t for all t ∈T such that

?t ∈T :t =succ (t )=?s (succ (t ))=?t (s (t ))

.

v 1v 3v 1v 3v 4

v 4v 1v 3time Fig.1.An example of a simple graph se-quence

Note that any graph modi?cation can be composed by a sequence of simple graph

modi?cations.Thus,by replacing each graph modi?cation of a non-simple graph sequence by an equivalent sequence of simple graph modi?cations,we can translate any graph

sequence into a,possibly much longer,sim-ple graph sequence.Time-independent sim-

ple graph sequences are simple graph se-

quences where the modi?cation function ?t is the same for all t ∈T .Note that the sequence (G,G,H )for two di?erent

graphs G =H is a simple graph sequence but not time-independent.An example of a simple graph sequence is given in Figure 1.

Throughout this paper,we will use the same notation for clusterings as introduced in [3].More precisely,let G =(V,E,ω)∈G be a connected graph and C ={C 1,...,C k }a partition of V .We call C a clustering of G and C i a cluster ;C is called trivial if either k =1,or all clusters C i contain only one element.In the following,we often identify a cluster C i with the induced subgraph of G ,i.e.,the graph G [C i ]:=(C i ,E (C i ),ω|E (C i )),where E (C i ):={{v,w }∈E :v,w ∈C i }.Then E (C ):= k i =1E (C i )is the set of intra-cluster edges and E \E (C )the set of inter-cluster edges .The set E (C i ,C j ):={{v,w }∈

E:v∈C i w∈C j}is the set of edges that have one end-node in C i and the other end-node in C j.

Furthermore,we will distinguish between a clustering technique and a clustering algo-rithm.A clustering technique is a mapping that maps each graph to a set of clusterings. For example,the set of all clusterings having maximum score with respect to a quality measure.In contrast,a clustering algorithm or an implementation maps each graph to ex-actly one clustering.A clustering algorithm A is associated with a clustering technique T, if for every graph G the clustering A(G)is contained in T(G).Note that the crucial point is that a speci?c implementation generally does not?nd all optimal solutions,while the image of the corresponding technique consists of all optimal solutions.For example,an implementation resolves degrees of freedom always in the same manner,thus excluding equivalent solutions.

3Dynamic Clustering

The dynamic clustering problem is to update a given clustering with respect to a cluster-ing technique when the associated graph changes.Since every graph modi?cation can be modeled as a sequence of simple graph modi?cations,we restrict ourselves to Problem1 as follows.

Problem1Given a graph G,a clustering technique T,a clustering C∈T(G)and a simple graph modi?cation?.Calculate a clustering C ∈T(?(G)).

Naturally,Problem1can be solved by applying an implementation of the technique T to the modi?ed graph?(G).However,implementations may be demanding with respect to running time or space consumption;in addition,this approach does not take any advantage of the given clustering C.

On the other hand,an update strategy that performs better than every algorithm for the clustering technique T,cannot improve the time complexity by more than a factor of n,where n is the number of nodes.Otherwise,we could use the update strategy to de?ne a faster algorithm which incrementally builds the graph with insertNode–operations.

In some cases,the exact update of a clustering technique may produce undesirable clusterings.For example,when the clustering technique consists of optimizing a quality measure,the global optima in G and?(G)might di?er substantially.Many applications that are based on dynamic clusterings not only rely on the induced quality of the clustering but also on structural properties.Thus,it is desirable to preserve structural properties already obtained.As a consequence,the formulation of Problem1needs to be subjected to further constraints.Therefore,Problem1becomes a bicriteria optimization problem, where one criterion is the quality aspect(induced by the technique)and the other criterion is the similarity to the given clustering C.This additional restriction is also called the preservation of the mental map[4].Most of the techniques for measuring the similarity of two clusterings are based on distance functions on partitions.However,these approaches neglect the edge set entirely,since they have their origin in the data mining community where pairwise information is available.For current approaches including a generalization for graph clusterings see[5].

3.1Heuristic Approaches to Dynamic Clustering

Although the above model re?ects all theoretical aspects of dynamic clustering an imple-mentation is highly non-trivial.Among the problems are that most clustering algorithms are either heuristics since the associated optimization problem is N P-hard or de?ned as an iterative process without optimizing a global quality function.Examples are the algo-rithm Iterative Conductance Cutting[6,7],which is a heuristic approach to optimize the intra-cluster conductance,or the betweenness clustering algorithm[8],which iteratively removes an edge with maximum betweenness.On the other hand,there is no obvious way to formalize the mental map property by distance measures.

Feasible approaches to dynamic clustering in general are local update or shifting strate-gies,see[3]for an overview.For several optimization criteria,the update can be determined with a low computational cost.By limiting the number of executed updates,one naturally obtains a clustering close to the initial clustering,thus preserving the mental map.In addition the search range for the updates can be scaled to achieve a trade-o?between the obtained quality and the preservation of the mental map.

3.2Counter-Examples

While the above models for clustering on changing graphs incorporate several important theoretical aspects,there clearly are situations where attention has to be paid to counterin-tuitive behavior.In the following,we give some basic examples consisting of the insertion of an intra-cluster edge(Figure2(a))and the deletion of an inter-cluster edge(Figure2(b)).

(a)insertion of intra-cluster edge

(b)deletion of inter-cluster edge

Fig.2.Two examples of counterintuitive splitting and merging resulting from the insertion and the deletion of a single edge,respectively.

4Time-Dependent Clustering

The time-dependent clustering problem is to identify structural groups within a given graph sequence.As a simple example consider the temporal evolution of a recommenda-tion system for books as used for example by https://www.doczj.com/doc/4a18751506.html,.In particular,the book‘The Lord of the Rings’by J.R.R.Tolkien.Before the major success of the?lm adaptation, the book belonged to the community of role playing and fantasy literature,afterwards it

belonged to a much broader community including other popular bestsellers.Another typ-ical example,which we will illustrate in Figure 4below,are the collaboration dynamics in science.Researchers usually start out working in a narrow ?eld,then,by interdisciplinary commitment,they enter other communities,possibly migrating to another ?eld entirely.

A formal de?nition of the term time-dependent clustering is given in De?nition 1.De?nition 1.Given a graph sequence s :T →G ,where T is a ?nite subset of N .The node set of graph s (t )is denoted by V (t ).A time-dependent clustering C (s )is a partition of the time-dependent node set V which is de?ned as

V :={(v,t )|t ∈T,v ∈V (t )}.(1)

Clustering each graph of the sequence independently yields a sequence of clusterings that naturally form a time-dependent clustering.Since temporal relations are not taken

into v 1v 2v 3v 4t 1t 2t

3Fig.3.The time-expanded graph of the se-quence given in Figure 1.

account,the clustering cannot be used to

identify temporal trends.However,the se-quence of clusterings may serve as a start-ing point and can be transformed into a

‘real’time-dependent clustering.One pos-

sible transformation could be to merge

temporally neighbored clusters that share a large fraction of nodes.

Another approach to obtain a time-

dependent clustering employing static

clustering methods is based on the

time-expanded graph .Given a graph se-

quence s :T →G the time-expanded graph G (s )=(V ,E , ω),where the edge set is de?ned as the union of the two sets E graph

and E time .

E graph :={{(v,t ),(w,t )}|v,w ∈V (t ),{v,w }∈E (t ),t ∈T }E time := (v,t ),(v,t ) |v ∈V (t ),t =min t |t >t ∧v ∈V (t ) ,

where E (t )denotes the edge set of the graph s (t ).The weight of an intra-graph edge {(v,t ),(w,t )}∈E graph is give by the weight of ωt ({v,w }),where ωt is the weighting function of graph s (t ).The weights on the inter-time edges,i.e.,those contained in E time ,are an additional degree of freedom which can be tuned in order to obtain meaningful time-dependent clusterings.As an example,the time-expanded graph of the sequence given in Figure 1is shown in Figure 3.Figure 4shows an excerpt from the time-expanded graph of collaborations of the scientist Thomas Lengauer.In the 80’s Lengauer concerned himself with algorithmic graph theory,focusing on planarity.However,in the early 90’s he began collaborations in the ?eld of bioinformatics and biology and at the present he is an es-tablished scientist of the bioinformatics community.The clustering of the time-expanded collaboration graph clearly reveals this development,identifying the community transition in the 90’s.

Fig.4.An excerpt from the collaboration graph of T.Lengauer is shown for the years1988,1992,1993, 1996,and1998.Round shapes correspond to publications in the?eld of biology,and rectangular shapes to those in computer science.The time-expanded graph is clustered by the large boxes and inter-time edges are drawn dashed.

5Conclusion

Summarizing,we introduced a formal model for clustering on evolving graphs.More pre-cisely,we considered the update problem(dynamic clustering)as well as the clustering of graph sequences(time-dependent clustering).Each formulation re?ects speci?c aspects of the dynamics present in real-world networks.The models we introduced are theoretically sound,yet,as indicated in Section3.2,counterintuitive situations may easily arise.These pitfalls are due to naive or even inconsistent human agendas postulating contradictory behavior of a clustering paradigm.This work is a?rst step towards a uni?ed theoreti-cal foundation for generalized clustering of graphs,including dynamics.Future work will be dedicated to utilizing,re?ning and further developing this model,speci?cally in the context of collaboration networks.r

References

1.Girvan,M.,Newman,M.E.J.:Community Structure in Social and Biological Networks.In:Proceedings

of the National Academy of Science of the USA.Volume99.(2002)7821–7826

2.Guimera,R.,Danon,L.,Diaz-Guilera,A.,Giralt,F.,Arenas,A.:Self-Similar Community Structure in

a Network of Human Interactions.Physical Review E68(2003)

3.Gaertler,M.:Clustering.In Brandes,U.,Erlebach,T.,eds.:Network Analysis:Methodological Foun-

dations.Volume3418of Lecture Notes in Computer Science.Springer-Verlag(2005)178–215

4.Eades,P.,Lai,W.,Misue,K.,Sugiyama,K.:Preseving the Mental Map of a Diagramm.In:Proceedings

of Compugraphics’91.(1991)24–33

5.Delling,D.,Gaertler,M.,G¨o rke,R.,Wagner,D.:Experiments on comparing graph clusterings.Tech-

nical Report2006-16,ITI Wagner,Faculty of Informatics,Universit¨a t Karlsruhe(TH)(2006)

6.Vempala,S.,Kannan,R.,Vetta,A.:On clusterings-good,bad and spectral.In:Proceedings of the

41st Annual IEEE Symposium on Foundations of Computer Science(FOCS’00).(2000)367–378

7.Brandes,U.,Gaertler,M.,Wagner,D.:Experiments on graph clustering algorithms.In:Proceedings

of the11th Annual European Symposium on Algorithms(ESA’03).Volume2832of Lecture Notes in Computer Science.(2003)568–579

8.Newman,M.E.J.,Girvan,M.:Finding and evaluating community structure in networks.Physical

Review E69(2004)

行业知识库平台解决方案

行业知识库平台解决方案

XX公司行业知识库平台 解决方案 重点行业信息化知识库及服务体系构造

1 概要 行业发起建设行业知识库平台可对整个行业起到的促进作用如下: ? 推动大企业向高端咨询转型。 ? 引导中小企业向专业化服务转型。 ? 加强行业用户与软件企业的战略合作。 ? 拓展行业应用市场, 抵制国外对手占据高端应用,扩大市场份额。 ? 优化行业结构,提升软件行业发展速度。 行业信息化知识库,是指软件企业在服务于行业信息化建设过程中所积累的行业关键知识、实施经验、软件构件重用等的总称。行业知识库的内容包括以下内容: 图表 1 行业知识库参考模型 行业知识库系统是一个复杂而庞大的系统,随着时代的进步而不断发展和创新,不同时期存在不同的情况、业务模式和不同的操作方法,在应用过程中又不断发现问题,不断加以改进和完善。所有这些过程、模式和业逻辑,都需要行业知识作为基础架构进行支撑,通过 行业信息化知识库 行业信息化全景图 行业业务模型行业数据模型行业解决方 案 行业解决方案仿真系统 行业领域构件 行业标准 行业法规法律 行业分析报告

面向知识的架构(SOA)提升行业信息化整体应用水平。 2 项目特点 行业知识库包括两大部分,即行业知识库体系以及行业知识库本身。前者是知识库理论基础,其文档系统可以概括为: 1. 知识体系。行业的知识与分类、行业标准法规文件、行业业务模型、行业数据模型、 行业信息系统的构件、行业案例、行业分析报告和信息资源定义等 2. 技术体系。行业总体解决方案、行业技术框架、系统需求分析、硬件网络环境、系统 概要设计、系统详细设计、系统测试报告、行业系统软件源码、构件软件和构件实体等 3. 服务体系。产业链全程服务体系、服务组织机构、服务规则规章、服务方式方法、服 务技术支撑框架、售前售中售后条例等。 知识库本身是知识库解决方案的实现,包括知识库开发平台和知识库应用平台。XX公司知识库开发平台采用SOA架构,以服务方式提供知识构件。在知识应用平台上构件作为服务与知识库解决方案、业务模型、数据模型等知识一样进行注册等维护管理。 行业知识库建设将改变传统的生产经营模式,通过实施行业整个供应链的一体化管理,实现以市场为导向优化资源配置、提高效率、降低成本、提升效益的目标;把信息化融入到行业、企业的实际工作中,全面落实依法行政、依法管理、依法经营,运用信息化开展技术创新、管理创新和制度创新,建立全面准确量化的管理体系,实现管理从定性向定量、由静态向动态、由事后向实时的转变,提升行业生产经营管理水平,提高应对国际竞争环境的能力。 XX公司在行业知识库开发上从知识体系建设和技术体系建设出发,采用两个建设并进的策略进行。在知识体系建设上,首先对目标行业进行全业务梳理,摸清目标行业的家底,调查、收集和整理行业相关的法律法规、标准文件,按照元数据的标准进行编目和归类,生成可以管理和操作的知识元素库。同时在技术体系上,构建以SOA架构为基础的知识库技术平台,参照业务梳理的成果,按照知识库的知识组织思路,在新架构下支撑对老系统的升级改造和新业务的构件开发。

一种动态知识库结构模型研究

INTELLIGENCE 1.引言 知识管理的理论研究,现今的情况是理论上学说纷杂,没有一个成熟的、能得到大家公认的理论体系,从而导致实际应用中的知识管理系统实现并不能完全达到人们预期的目标。这种情况的产生,固然和知识本身的内隐性、不确定性以及不稳定性相关,但理论研究和实际应用的脱节也是其中最重要的一个原因。 本文试图建立一个理论上相对成熟、实践中具有可操作性的动态知识库。在总结前人研究成果的基础上,结合数据挖掘、知识推理等知识管理系统中必不可少的技术,探讨一种与组织业务流程无关、着重知识学习、基于知识传导模型的知识分类体系,并在此基础上建立了组织的动态知识库。由于这种知识库与企业具体的业务流程无关,所以具体到每个企业的知识库实现时,知识库可以动态扩充。这种扩充体现在两个方面,一是企业可以基于这个知识库结构模型,把这个知识库模型视为一个单元知识,在其最外层加上业务流程的约束,即形成了自己的知识库。二是在知识库内部,知识所处的分类层次也不是固定不变的,当知识在组织内部传导、重构时,知识的状态发生改变,知识库能自动感知这种变化,并将其推送(或者重构新知识)到相应的分类层次中去。 2.动态知识库理论基础 2.1理论研究中的知识分类。理论研究中的知识分类,最重要的莫过于隐性知识和显性知识的概念。这两个概念的建立将知识管理和信息管理从内容上区分开来,具有划时代的意义。显性知识是指已经编码化的知识,它以人类语言的各种表现形式而存在,如书本、视频等。隐性知识主要指“隐含经验类知识”,往往是个人或组织经过长期积累而拥有的知识,通常不易用语言表达,也难以传播。 1996年,OECD(经济合作发展组织)把知识分为四类。即know-what(知道是什么的知识),是关于事实方面的知识。例如企业有多少员工、产品用的什么原料、企业的主要产品等;know-why(知道为什么的知识),指自然原理和规律方面的科学理论,企业的know-why知识指企业生产的原理和规律,比如为什么选用某种原料、为什么生产某种产品而不是另外一种等;know-how(知道怎样做的知识),是指做业务流程中的技术和能力,比如熟练工人操作机器的技术等等;know-who(知道是谁的知识),是指关于谁知道什么和怎么做的知识,例如在工作过程中,如果出现了问题应该请教谁。 OECD对知识的四类划分中,关于知道是什么(Know-what)和知道为什么(Know-why)的知识基本属于显性知识,而隐性知识所对应的是OECD分类中关于知道怎样做(Know-how)和知道是谁(Know-who)的知识 2.2Helund的知识传导模式。在知识的转化过程中,日本著名的知识管理专家野中郁次郎和竹内广孝提出了知识转化的四种模式:从隐性知识到隐性知识称为群化,(Socialization);从隐性知识到显性知识称为外化(Externalization);从显性知识到显性知识称为融合(Combination);从显性知识到隐性知识称为内化(Internalization)。 Helund提出了知识传导模式有三种:编码化及内化、外延和占有、消化及扩散。1.编码化及内化。编码化表示了组织中隐性知识显性化的过程,企业组织可以视作为一个编码的机器。而内化指知识变成员工个人隐性知识的过程。内化使得有限认知、知觉以及协调资源变得更有效率。显性和隐性之间的活动称为映射,创新和现实的知识往往是借这个活动而形成的。2.外延和占用。外延是指知识由较低层移动到较高层,层次分为个人、小团队、组织、跨组织-,可能是隐性知识也可能是显性知识。而占用是外延的反向过程。对话则是外延和占用的互动,对话通常发生在某一特定层级之中,从个人到跨组织的领域。“对话”与“思考”的质与量被假设与知识管理模式的质与量高度相关。以学校为例,教师与学生在教室的对话与学生在家中的思考同等重要。3.消化及扩散:从环境之中取得知识并将其扩散于环境中。消化及扩散类似于知识输入及知识输出,被吸收的知识可能是隐性也可能是显性的,包括认知、产品及技能等形式。例如复杂的隐性知识可通过招募关键性的人员来取得;如果知识较易编码化,则企业买卖专利权是一个适当的策略。若知识的隐性度较高,则表示知识的消化方式是以内化为主导的。 3.动态知识库结构模型 3.1动态知识库模型的特点。 a.多层次知识分类结构。目前理论界从不同的角度对知识有多种分类方法,但任何一种单独的分类方法都不足以用来描述组织的业务流程知识。而且如果采用了一种不成熟的分类方法,就不能保证知识分类的完备性和相对独立性,本知识库结构模型应该能够具有实 践操作性,也就是说知 识库必须要是实际应 用中的一个模型结构。 所以知识库综合运用 了四种分类方法,即 OECD的知识分类方 法:know-what(知道是 什么的知识), know-why(知道为什么 的知识),know-how(知 道怎样做的知识), know-who(知道是谁的 知识)。在这四种分类 方法中,又按知识的拥 有者:个人、团体、组 织、跨组织进行了交叉重叠分类。这几类知识的重叠形成了16类知识。对企业知识的划分,隐性知识和显性知识是必不可少的,对显性知识按存储形式(结构知识、半结构知识、非结构知识)然后和隐性知识并列对组织业务流程知识进行了第三次分类。第四次分类实际上对上述这些知识的抽象,元知识用来描述组织业务流程知识本身,关系知识用来描述组织业务流程知识之间的关系。 b.业务流程无关性。纵观企业的经营模式,即使是具有相同业务的企业,其业务流程也会千差万别,而且企业的经营模式也有可能因企业管理层的改变等原因而变化。所以,一个能得到良好应用的知识库结构模型,应是与组织业务流程无关的。在动态知识库结构模型中,抽象出来的知识分类是每一个业务 一种动态知识库结构模型研究 广州科技职业技术学院邝云英 教学实践与管理 247

00基于故障树分析法构建专家系统知识库模型

基于故障树分析法构建专家系统知识库模型 摘要:本文在广泛搜集往复式压缩机故障类型的基础上,探析故障机理。运用故障分析法,建立故障树模型,并用二维表格将其表示出来。然后并运用access数据库和vb语言构建知识库链表。最后,给出故障诊断专家系统知识库维护方法。 关键词:往复式压缩机知识库故障树 引言:往复式压缩机由于其自身的特点广泛应用于石油石化企业。但由于机构复杂、零件繁多,现场维修人员在诊断故障问题时困难重重。在维护和维修往复式压缩机时,故障诊断专家系统可以给现场维修人员提出宝贵建议的。在往复式压缩机故障诊断专家系统中,知识库的优劣直接影响到诊断的准确性和真实性。在构建知识库过程中,故障树分析法直接简明、逻辑性强等特点,所以本文采用故障树模型建立往复式压缩机故障诊断系统的知识库,保证诊断的准确性和真实性。 Building a knowledge base of expert system model based on the fault tree analysis 1,故障树分析法基本知识 1.1定义: 故障树分析法就是把所研究系统的最不希望发生的故障状态作为故障分析的目标,然后寻找直接导致这一故障发生的全部因素,再找出造成下一级事件发生的全部直接因素,一直追查到那些原始的、其故障机理或概率分布都是已知的,毋需再深究的因素为止。 通常,把最不希望发生的事件称为顶事件,毋需在深究的事件称为底事件,介于顶事件和底事件之间的一切事件为中间事件,用相应的符号代表这些事件,再用适当的逻辑门把顶事件、中间事件和底事件联结成树形图。这样的树形图称为故障树,用以表示系统或各个部件故障事件之间的逻辑结构关系。以故障树为工具,分析系统发生故障的各种途径,计算各个可靠性特征量,对系统的安全性或可靠性进行评价的方法称为故障树分析法。 1.The failure analysis 1.1 Basic knowledge of fault tree analysis Fault tree analysis is that the most reluctant fault condition occurred in the studied system will be as a failure analysis of target; then look for all the factors leading to the most reluctant fault condition; next seek for all the direct factors causing the next level faults till original fault factors、well known failure mechanisms or open Probability distribution of fault factors would be fond out; finally, you can obtain all the original fault factors that can’t be divided. Usually, the most reluctant fault case would be considered as the top incindents; the fault factors that couldn’t be searched would be acted as the bottom incindents; the fault case in the middle of the top incindents and the bottom incindents would be though as intermediate incindents. By appropriate symbols of fault tree analysis expressing the three typle of mentioned incindents and combining the top incindents、intermediate incindents and the bottom incindents in logic relationship, we can make out the model of the fault tree analysis-the graph of fault tree analysis that it would indicate the logic structure for each fault incidents or fault tree analysis. Fault tree analysis is the method that it can evaluate security and reliability of the studied systems accuratelly that by the way of the model of fault tree, analyzing all kinds of faults incindent, caculating vavious characteristic quantities of reliability. 1.2故障树分析法步骤 故障树分析步骤具体如下: 1.对所选定的系统作必要分析,了解系统的组成及各项操作的内容。 2.对系统的故障进

1零点知识库—KANO模型翻译

KANO模型:如何取悦你的客户? Elmar Sauerwein , Franz Bailom, Kurt Matzler, Hans H. Hinterhuber* Department of Management, University of Innsbruck 什么产品和服务能用来获取更高程度的客户满意度?什么产品特性能产生对客户满意度超过常规的影响?或者,什么属性在客户眼里属于绝对必须的? 迄今为止,客户满意度多数时候被视为一种一维结构――接受到的产品感知质量越高,客户的满意度也就越高,反之亦然。但是,对于个人产品需求的充分满足并不必然意味着高水平的客户满意度。在现实中,更多的则是由于消费者需求的不同类型而带来的的产品感知质量和由之而来的客户满意度的差异。从针对客户满意度的KANO模型出发,我们在这儿将介绍一种在客户满意度研究中用来判定影响产品和服务因素构成的途径。笔者同样试图证明,一个消费者调查的结果如何针对客户满意度管理的层次来进行解释以及其结论如何被提取和使用。 客户满意度中的KANO模型 在模型中,狩野紀昭(Noriaki Kano,1984)先生辨析了三种在不同形式上影响客户满意度的产品需求: 必要需求(Must-be requirements):假如这些需求得不到满足,客户将会非常的不满意。换个角度,正是由于客户认为这些需求是离索应当的,他们在这些方面的满足甘并不会增加满意度。必要需求对于产品来说是一个基准。对必要需求的满足仅仅会带来客户“没有感到不满意”的态度。客户把必要需求当作是事前的基本预求,他们认为理所应当并所以而不会明确的提出对此的需求。必要需求在所有的场合下都是决定性的因素,并且假如这些需求得不到满足,客户将会对产品完全丧失兴趣。 一维需求(One-dimensional requirements):关于这些需求,客户满意度会根据需求的满足水平成比例的改变――满足度越高,客户满意度也就越高,反之亦然。一维需求往往客户会明确的提出对它的需要。 吸引性需求(Attractive requirements):这些需求并不是产品的标准配备要求,并且它假如在产品中向客户提供的话,则将在极大程度上影响客户的满意度。吸引性需求既不会由消费者明确提出也并非消费者事前能够预期的。对这些需求的满足能够带来客户满意度超越常规的提升。然而,假如他们没有得到满足,也不会所以让客户产生不满意的态度。 * Professor Hans H. Hinterhuber is head of the Department of Management at the University of

行业知识库平台解决方案要点

XX公司行业知识库平台 解决方案 重点行业信息化知识库及服务体系构造

1 概要 行业发起建设行业知识库平台可对整个行业起到的促进作用如下: ?推动大企业向高端咨询转型。 ?引导中小企业向专业化服务转型。 ?加强行业用户与软件企业的战略合作。 ?拓展行业应用市场, 抵制国外对手占据高端应用,扩大市场份额。 ?优化行业结构,提升软件行业发展速度。 行业信息化知识库,是指软件企业在服务于行业信息化建设过程中所积累的行业关键知识、实施经验、软件构件重用等的总称。行业知识库的内容包括以下内容: 图表 1 行业知识库参考模型 行业知识库系统是一个复杂而庞大的系统,随着时代的进步而不断发展和创新,不同时期存在不同的情况、业务模式和不同的操作方法,在应用过程中又不断发现问题,不断加以改进和完善。所有这些过程、模式和业逻辑,都需要行业知识作为基础架构进行支撑,通过面向知识的架构(SOA)提升行业信息化整体应用水平。

2 项目特点 行业知识库包括两大部分,即行业知识库体系以及行业知识库本身。前者是知识库理论基础,其文档系统可以概括为: 1. 知识体系。行业的知识与分类、行业标准法规文件、行业业务模型、行业数据模型、 行业信息系统的构件、行业案例、行业分析报告和信息资源定义等 2. 技术体系。行业总体解决方案、行业技术框架、系统需求分析、硬件网络环境、系统 概要设计、系统详细设计、系统测试报告、行业系统软件源码、构件软件和构件实体等 3. 服务体系。产业链全程服务体系、服务组织机构、服务规则规章、服务方式方法、服 务技术支撑框架、售前售中售后条例等。 知识库本身是知识库解决方案的实现,包括知识库开发平台和知识库应用平台。XX公司知识库开发平台采用SOA架构,以服务方式提供知识构件。在知识应用平台上构件作为服务与知识库解决方案、业务模型、数据模型等知识一样进行注册等维护管理。 行业知识库建设将改变传统的生产经营模式,通过实施行业整个供应链的一体化管理,实现以市场为导向优化资源配置、提高效率、降低成本、提升效益的目标;把信息化融入到行业、企业的实际工作中,全面落实依法行政、依法管理、依法经营,运用信息化开展技术创新、管理创新和制度创新,建立全面准确量化的管理体系,实现管理从定性向定量、由静态向动态、由事后向实时的转变,提升行业生产经营管理水平,提高应对国际竞争环境的能力。 XX公司在行业知识库开发上从知识体系建设和技术体系建设出发,采用两个建设并进的策略进行。在知识体系建设上,首先对目标行业进行全业务梳理,摸清目标行业的家底,调查、收集和整理行业相关的法律法规、标准文件,按照元数据的标准进行编目和归类,生成可以管理和操作的知识元素库。同时在技术体系上,构建以SOA架构为基础的知识库技术平台,参照业务梳理的成果,按照知识库的知识组织思路,在新架构下支撑对老系统的升级改造和新业务的构件开发。

基于本体化知识模型的知识库构建模式研究

基于本体化知识模型的知识库构建模式研究 袁磊1张浩2陈静3陆剑峰1 1(同济大学CIMS中心,上海2(0092) 2(上海电力学院,上海200092) 3(华东师范大学地理系,上海200062) 【摘要】在研究了知识模型及知识库相关理论和技术的基础上,结合本体论,提出了一种基于本体的知识模型,并从领域知识推理、方法知识和任务知识三个角度给出了本体化知识模型基于BNF范式的表达式;基于所建立的本体化知识模型,在对知识进行可拓性分析的基础上,提出了一种知识库结构模式,对于知识模型与知识库的匹配问题进行了讨论,并在理论研究的基础上,给出了利用SQL Server数据库系统建立的知识库示例。 【关键词】本体;知识模型;知识库;设计模式;知识工程 1引言 对于知识的研究与探索,人类自始至终从未停止过,直至人类进入信息化社会并正在向知识化社会迈进的过程中,人类通过计算机的应用才开始真正把知识从概念跃升到知识科学。知识工程便是一门新兴的关于知识获取、表示和推理,以及用一种特定形式把知识表示为计算机可操作对象的科学。其研究的目标是挖掘和抽取人类知识,这也使得计算机具有了人类的一定智能。 知识工程是在20世纪70年代后期,从构建专家系统、基于知识的系统和知识密集型的信息系统的技术发展而来的。Guus Schreiber认为"知识工程是一种建模活动,模型是对现实的某一部分进行的一种有目的的抽象。建模是对知识的少数几个方面建立一种好的描述,而忽略其他方面"。因此,知识工程领域最主要的研究内容是知识表示以及基于此的知识应用。知识模型本身是一个阐述"知识一密集型信息一处理任务结构"的工具。一个应用的知识模型可提供应用所需的数据和知识结构的规范说明。

网格环境下基于本体的知识库模型研究

第51卷第5期 2005年10月武汉大学学报(理学版) J.Wuhan Univ.(Nat.Sci.Ed.)Vol.51No.5 Oct.2005,603~608 收稿日期:2004211210 通讯联系人 E 2mail :chenhr @https://www.doczj.com/doc/4a18751506.html, 基金项目:湖北省教育厅科学研究计划(2003A012);湖北省自然科学基金(2003ABA049)资助项目作者简介:黄 屹(19692),男,博士生,现从事分布式系统与分布式流媒体等研究. E 2mail :huangyi @https://www.doczj.com/doc/4a18751506.html, 文章编号:167128836(2005)0520603206 网格环境下基于本体的知识库模型研究 黄 屹1,顾进广1,2,陈莘萌1 ,陈和平3 (1.武汉大学计算机学院,湖北武汉430072;2.武汉科技大学计算机科学与技术学院,湖北武汉430081; 3.武汉科技大学信息科学与工程学院,湖北武汉430081) 摘 要:针对知识技术仅用于描述网格服务的可用性以及如何被发现、调度和进化的现状,在开放网格服务体系结构(O GSA )的基础上,给出了知识库本体的形式化定义,分析了构建知识库所需的本体,在此基础上提出了网格环境下知识库通用体系结构及基于语义适配器的存储模型,克服了Sesame 存储模型在存储不同格式文件和本体方面所存在的不足,讨论了网格知识库的访问机制. 关 键 词:知识库;开放网格服务体系结构;知识网格;本体中图分类号:TP 391 文献标识码:A 0  引 言 网格[1]作为分布式环境下资源共享与协作计算 的集成基础设施,网格正受到越来越多的关注.网格应用涉及海量数据与密集计算,对目前的互联网和网络基础设施而言是一个极大的挑战,网格中间件正试图在通信、调度、安全、信息、数据访问和错误检测等多个领域迎接挑战.开放网格服务体系结构(O GSA )[1,2]借助Web service 成果,在网格中引入了服务定位.网格服务是Web service 的集合,它遵守一组控制、差错恢复和安全管理协定,并通过标准接口提供服务.知识网格[3]使用知识本体来描述网格资源,是网格和语义网络的一种演变.V EGA 2KG (http ://https://www.doczj.com/doc/4a18751506.html, )[4,5]和PD KD [6,7]是该方面研究的典型范例. 然而,目前关于知识和网格的研究主要集中在使用知识技术来描述网格服务的可用性,描述它们是如何被发现、调用和进化的,并且从服务描述和网络元素中获取知识.相反,网格上的知识却很少讨论.本文提出了一种网格知识应用———在网格的分布式节点上存储知识,使用网格与知识网格的基本概念如面向服务的中间件,网格的知识技术,基于本体的知识表示机制等等,来描述分布式知识库节点的资源处理能力. 作为词汇集和概念关系的形式化说明方法,知 识本体在语义网和知识网格中发挥重要作用.知识本体为确定领域中的应用提供共享概念,减少或消除多个概念和术语之间的混淆,使领域知识的处理更加精确和方便.使用DAML +OIL 等描述逻辑语言来表示基于本体的知识,DAML +OIL 采用一种面向对象的方法进行建模,一个领域通常用类和特性来表示,它在RDF (Resource Description Framework )的基础上进行了扩充,丰富了语言的建模能力.用类Horn 逻辑语言如TRIPL EI [8]表示知识规则. 1 知识库的本体定义 本体的主要目的是提供一种通用的方法,通过该方法,多个应用程序及使用者可以采用通用的方式来理解所涉及的领域知识及概念,达到重用资源的目的.通常用类、关系、函数、定理、实例的集合表示本体,文献[9]中给出了本体、关系、定理和词典的定义,本文在其基础上对本体进行扩充. 定义1 本体O 可用一个八元组来表示,O ∶=(C ,R ,A C ,A R ,≤C ,≤R ,σ,L ),其中,①C 和R 为两个集合,分别表示概念集合和关系集合;②A C ,A R 是两个属性集合容器,分别代表概念属性的集合容器和关系属性的集合容器,容器的每一个元素代表

相关主题
相关文档 最新文档