论文部分内容阅读
摘 要：针对工作流模型的XML文档的特殊性，提出了基于XML的工作流模型挖掘算法，该算法综合利用了结构信息与内容信息对XML文档进行分析，并将XML文档的结构与内容进行了量化，用一个矩阵来表示文档，进一步对文档进行综合挖掘，为工作流模型的挖掘提供了一种有效的方法。
关键词：XML；挖掘；工作流模型
中图分类号：TP311.52
工作流是企业可用计算机实现管理的结构化或非结构化业务流程的计算机模型，它的概念起源于生产组织和办公自动化领域，是针对日常工作中具有独立程序的活动而提出的一个概念。不同的研究者和工作流产品供应商从不同的角度给出了工作流的定义，但基本上都认为工作流是经营过程的计算机实现。工作流模型数据通常以XML格式出现，而传统的基于XML只是从结构或内容单方面进行挖掘，但是在流程数据中，文档的结构与内容都是表征流程的重要信息，这就需要一种兼顾文档结构与内容的挖掘方法。XML作为一种新兴的技术，在信息时代快速发展的今天，正在得到越来越广泛的应用，越来越多的数据以XML的格式进行存储和交换，因此，面向XML文档的数据挖掘变得尤为重要。
1 XML的特点
XML是Extensible Markup Language的简写，是一种用于标记电子文件使其具有结构性的标识语言。所谓标识，就是为了处理的目的，在数据中加入的附加信息。应用标识法描述的结构化数据的形式语言称为标识语言。一般认为，XML具有如下优点：
（1）可扩展性：XML提供了一个表示信息的框架。它允许信息提供者根据自己的需求和意愿定义任意的标记，数据经过XML的处理之后，表达方式简单易读，同时也易于由其他应用进行进一步的加工和处理。
（2）结构性：数据存储格式不受显示格式的制约，一般包括三个要素：数据、结构以及显示方式。XML使用DTD（或者XML Schema）规定一套关于标记符号的语法、语义规则，比较准确地描述文件资料的内容、含义、结构、特征和关系等信息，而把资料的外观表现形式交给样式表处理，这样就把信息的内容和其表现形式合理地隔开，从而大大提高XML信息的可理解性、可交换性和重用性。
（3）平台独立性：XML使用普通文本，而不是二进制的数据格式，具有跨平台的优点，运用XML可以有效地解决新旧系统平台，不同应用系统平台之间或者不同数据源之间的数据共享与交互问题。
（4）自描述性：XML以显式语句和隐式嵌套结构描述结构化信息，任何应用都可以方便访问其中的数据并清楚地了解到标记内容的含义，自描述性使其非常适用于不同应用间的数据交换，而且这种交换是不以预先规定一组数据结构定义为前提，因此，具备很强的开放性。
（5）灵活性：XML文档中，数据、数据结构与文档的表现方式是分离的，它与HTML的组织方式完全不同，结构化的数据通过可扩展的样式表XSL将数据呈现在同的終端设备上，通过使用不同的XSL摸板可以将数据方便地呈现在各种不同系统的浏览器上，而在这些不同的应用上，数据本身是一样的。
（6）规范、简单性：XML与HTML一样，XML也是源于标准通用标记语言SGML，它保留了SGML的80%的功能，而复杂性只有它的20%，此外，XML文档有一套严谨而简洁的语法结构，这为XML解析器获取文档所含信息提供了前提。
2 XML文档的挖掘
对XML的挖掘包括对XML结构上的挖掘和对XML内容上的挖掘两种。
2.1 XML结构上的挖掘
XML是半结构化的数据，元素的标记以及它们的嵌套关系表示了XML文档的结构，从半结构的载体中挖掘出XML的结构部分对分析理解XML文档具有重要的意义。XML结构的挖掘关键是对DTD或Schema的挖掘，在实际操作过程中是将每一个XML文档的结构看作是一棵有根、有序的标记树，在此基础上对树的挖掘。
结构上的挖掘是仅和XML文档结构内部有关，我们也可以靠知识发现得到XML文档内部的结构信息，即文档的类型定义DTD，从而引入对有效的XML文档的分析。有效的XML文档，应该是结构良好的XML文档，该文档中不仅定义了和文档相关的DTD，而且经过验证发现该文档也是完全符合这个DTD规范的。
通常使用集合论符号来标识XML的内部关系，包括XML的对象用X标识，用D标识XML文档的集合，则有 。W代表结构良好的XML文档，如果D通过了结构上的验证，保证了结构的良好，那么D=W。V用于标识有效的XML文档， 。同时，可以定义出结构不良好的XML文档对象，也就是 。
XML的结构挖掘又可以进一步分为结构内挖掘和结构间挖掘。
2.2 结构内挖掘
结构内挖掘是对一个XML文档内的结构进行挖掘以发现隐藏在结构内的知识，也就是对DTD或Schema的挖掘，这里仅以DTD为例进行说明。挖掘的结果可以用来：
分类：可以根据预定义的分类对新XML文档进行归类。DTD可以用来对XML文档的类别进行描述。分类过程先收集DTD文档作为训练集，然后根据这个训练集对新文档进行分类。这一任务在有效的XML文档中比较容易实现，因为新文档的DTD已经定义了，可以通过比较分类DTD与新DTD来进行。
对任何一个定义有关联的DTD的XML文档来说，它应该首先进行有效性验证，即验证文档是否和DTD中的定义一致。区分XML文档是有效还是仅仅结构良好，这一点非常重要。对于那些仅仅结构良好的XML来说，可以根据分类DTD来解析文档。一个成功地被解析的文档被作为相关DTD的一个实例而进行分类。对于结构不好的XML来说，在一个错误发生前，如果有字够的文档被解析，也可以用来进行分类，然后分好的类别可以用来发现潜在的有价值的信息。
聚类：被用来识别各种XML文档间的相似性。聚类算法收集DTD并根据自身的相似性进行组合，这些相似性然后被用来生成新DTD，通常来说，新DTD是DTD训练集的超类。 关联规则挖掘：被用来描述共同在XML文档中出现的标记间的关系。XML文档可以很自然地分析为树形结构，它的结构DTD也是树形结构的。把树形结构的XML结构转化为以“事务”为单位的对象，就可以利用以有的数据挖掘关联规则方法挖掘出一些有意义的规则，如可以生成“如果包含一个A则80%包含一个B”等。
2.3 结构间挖掘
结构间挖掘是挖掘XML文档之间的结构中的知识，这些知识包括主题、组织方式以及节点之间的关系。它同样可以用于：
分类：被应用到命名空间和URI，根据关联的DTD，用来对新的XML文档进行分类。
聚类：这种方法可以用来进行不同XML文档之间的相似度严整。通过聚类算法把一个DTD的集合根据相互相似度的特征聚合，再在这个通过相似度聚合子集的基础上产生新的泛化的DTD，这个新的DTD和这个DTD聚合子集有着层次关系，是这个DTD聚合子集的父类，也就是对聚类子集中所有DTD的泛化。
2.4 XML内容上的挖掘
XML内容的挖掘即是对标记的值的挖掘。它也有两种形式的挖掘，单个XML文档的挖掘和群组XML文档的挖掘。
2.5 单个XML文档的挖掘
单个XML文档本身就是包含信息极其丰富的挖掘对象，可以被看作为一个数据库，因此可以在单个的XML文档中进行知识提取，如文档内部内容的分类、关联规则分析、聚类挖掘等。但是，正如前面所提到的，尽管作为信息主要载体的XML提供了一种方便地标识和交换信息的方法，但它可能并不是一个很好的可以从中自动抽取与数据驱动的服务或者应用程序相关的信息的结构，它的结构使它很难用系统的方法来利用信息。
2.6 群组XML文档的挖掘
群组XML文档的挖掘是在一組XML文档上进行的，而且挖掘的对象与文档标记无关，只与标记的值有关。此时，XML文档标记的作用已经退化，而标记的值在被提取出来之后，组成的内容的集合和文本基本等价。因此，在群组XML文档上进行的内容挖掘也就退化为一般的文本挖掘，使用一般的分类、聚类、关联规则分析等方法即可。
参考文献：
[1]Agrawal R，Gunopulos D，Leymann F.Mining process modelsfrom workflow logs[C]∥Proceedings of the Sixth International Conference on Extending Database Technology.[s.l.]：[s.n.]，1998：469-483.
[2]van der Aalst W M P，Weijters T，Maruster L.Workflow Mining：Discover-ing Process Models from Event Logs[J].IEEE Transactions on Knowledge and Data Engineering，2004（09）：1128-1142.
[3]Herbst J，Karagiannis D.Workflow mining with InWoLve[J].Computers in Industry，2004（53）：245-264.
[4]范玉顺.工作流管理技术基础—实现企业经营过程重组与经营过程自动化的核心技术[M].北京：清华大学出版社，2001.
作者简介：吕克（1963.12-），男，江苏扬州人，现代教育技术管理科科长，研究方向：教育技术研究。
作者单位：扬州大学教务处，江苏扬州 225009
关键词：XML；挖掘；工作流模型
中图分类号：TP311.52
工作流是企业可用计算机实现管理的结构化或非结构化业务流程的计算机模型，它的概念起源于生产组织和办公自动化领域，是针对日常工作中具有独立程序的活动而提出的一个概念。不同的研究者和工作流产品供应商从不同的角度给出了工作流的定义，但基本上都认为工作流是经营过程的计算机实现。工作流模型数据通常以XML格式出现，而传统的基于XML只是从结构或内容单方面进行挖掘，但是在流程数据中，文档的结构与内容都是表征流程的重要信息，这就需要一种兼顾文档结构与内容的挖掘方法。XML作为一种新兴的技术，在信息时代快速发展的今天，正在得到越来越广泛的应用，越来越多的数据以XML的格式进行存储和交换，因此，面向XML文档的数据挖掘变得尤为重要。
1 XML的特点
XML是Extensible Markup Language的简写，是一种用于标记电子文件使其具有结构性的标识语言。所谓标识，就是为了处理的目的，在数据中加入的附加信息。应用标识法描述的结构化数据的形式语言称为标识语言。一般认为，XML具有如下优点：
（1）可扩展性：XML提供了一个表示信息的框架。它允许信息提供者根据自己的需求和意愿定义任意的标记，数据经过XML的处理之后，表达方式简单易读，同时也易于由其他应用进行进一步的加工和处理。
（2）结构性：数据存储格式不受显示格式的制约，一般包括三个要素：数据、结构以及显示方式。XML使用DTD（或者XML Schema）规定一套关于标记符号的语法、语义规则，比较准确地描述文件资料的内容、含义、结构、特征和关系等信息，而把资料的外观表现形式交给样式表处理，这样就把信息的内容和其表现形式合理地隔开，从而大大提高XML信息的可理解性、可交换性和重用性。
（3）平台独立性：XML使用普通文本，而不是二进制的数据格式，具有跨平台的优点，运用XML可以有效地解决新旧系统平台，不同应用系统平台之间或者不同数据源之间的数据共享与交互问题。
（4）自描述性：XML以显式语句和隐式嵌套结构描述结构化信息，任何应用都可以方便访问其中的数据并清楚地了解到标记内容的含义，自描述性使其非常适用于不同应用间的数据交换，而且这种交换是不以预先规定一组数据结构定义为前提，因此，具备很强的开放性。
（5）灵活性：XML文档中，数据、数据结构与文档的表现方式是分离的，它与HTML的组织方式完全不同，结构化的数据通过可扩展的样式表XSL将数据呈现在同的終端设备上，通过使用不同的XSL摸板可以将数据方便地呈现在各种不同系统的浏览器上，而在这些不同的应用上，数据本身是一样的。
（6）规范、简单性：XML与HTML一样，XML也是源于标准通用标记语言SGML，它保留了SGML的80%的功能，而复杂性只有它的20%，此外，XML文档有一套严谨而简洁的语法结构，这为XML解析器获取文档所含信息提供了前提。
2 XML文档的挖掘
对XML的挖掘包括对XML结构上的挖掘和对XML内容上的挖掘两种。
2.1 XML结构上的挖掘
XML是半结构化的数据，元素的标记以及它们的嵌套关系表示了XML文档的结构，从半结构的载体中挖掘出XML的结构部分对分析理解XML文档具有重要的意义。XML结构的挖掘关键是对DTD或Schema的挖掘，在实际操作过程中是将每一个XML文档的结构看作是一棵有根、有序的标记树，在此基础上对树的挖掘。
结构上的挖掘是仅和XML文档结构内部有关，我们也可以靠知识发现得到XML文档内部的结构信息，即文档的类型定义DTD，从而引入对有效的XML文档的分析。有效的XML文档，应该是结构良好的XML文档，该文档中不仅定义了和文档相关的DTD，而且经过验证发现该文档也是完全符合这个DTD规范的。
通常使用集合论符号来标识XML的内部关系，包括XML的对象用X标识，用D标识XML文档的集合，则有 。W代表结构良好的XML文档，如果D通过了结构上的验证，保证了结构的良好，那么D=W。V用于标识有效的XML文档， 。同时，可以定义出结构不良好的XML文档对象，也就是 。
XML的结构挖掘又可以进一步分为结构内挖掘和结构间挖掘。
2.2 结构内挖掘
结构内挖掘是对一个XML文档内的结构进行挖掘以发现隐藏在结构内的知识，也就是对DTD或Schema的挖掘，这里仅以DTD为例进行说明。挖掘的结果可以用来：
分类：可以根据预定义的分类对新XML文档进行归类。DTD可以用来对XML文档的类别进行描述。分类过程先收集DTD文档作为训练集，然后根据这个训练集对新文档进行分类。这一任务在有效的XML文档中比较容易实现，因为新文档的DTD已经定义了，可以通过比较分类DTD与新DTD来进行。
对任何一个定义有关联的DTD的XML文档来说，它应该首先进行有效性验证，即验证文档是否和DTD中的定义一致。区分XML文档是有效还是仅仅结构良好，这一点非常重要。对于那些仅仅结构良好的XML来说，可以根据分类DTD来解析文档。一个成功地被解析的文档被作为相关DTD的一个实例而进行分类。对于结构不好的XML来说，在一个错误发生前，如果有字够的文档被解析，也可以用来进行分类，然后分好的类别可以用来发现潜在的有价值的信息。
聚类：被用来识别各种XML文档间的相似性。聚类算法收集DTD并根据自身的相似性进行组合，这些相似性然后被用来生成新DTD，通常来说，新DTD是DTD训练集的超类。 关联规则挖掘：被用来描述共同在XML文档中出现的标记间的关系。XML文档可以很自然地分析为树形结构，它的结构DTD也是树形结构的。把树形结构的XML结构转化为以“事务”为单位的对象，就可以利用以有的数据挖掘关联规则方法挖掘出一些有意义的规则，如可以生成“如果包含一个A则80%包含一个B”等。
2.3 结构间挖掘
结构间挖掘是挖掘XML文档之间的结构中的知识，这些知识包括主题、组织方式以及节点之间的关系。它同样可以用于：
分类：被应用到命名空间和URI，根据关联的DTD，用来对新的XML文档进行分类。
聚类：这种方法可以用来进行不同XML文档之间的相似度严整。通过聚类算法把一个DTD的集合根据相互相似度的特征聚合，再在这个通过相似度聚合子集的基础上产生新的泛化的DTD，这个新的DTD和这个DTD聚合子集有着层次关系，是这个DTD聚合子集的父类，也就是对聚类子集中所有DTD的泛化。
2.4 XML内容上的挖掘
XML内容的挖掘即是对标记的值的挖掘。它也有两种形式的挖掘，单个XML文档的挖掘和群组XML文档的挖掘。
2.5 单个XML文档的挖掘
单个XML文档本身就是包含信息极其丰富的挖掘对象，可以被看作为一个数据库，因此可以在单个的XML文档中进行知识提取，如文档内部内容的分类、关联规则分析、聚类挖掘等。但是，正如前面所提到的，尽管作为信息主要载体的XML提供了一种方便地标识和交换信息的方法，但它可能并不是一个很好的可以从中自动抽取与数据驱动的服务或者应用程序相关的信息的结构，它的结构使它很难用系统的方法来利用信息。
2.6 群组XML文档的挖掘
群组XML文档的挖掘是在一組XML文档上进行的，而且挖掘的对象与文档标记无关，只与标记的值有关。此时，XML文档标记的作用已经退化，而标记的值在被提取出来之后，组成的内容的集合和文本基本等价。因此，在群组XML文档上进行的内容挖掘也就退化为一般的文本挖掘，使用一般的分类、聚类、关联规则分析等方法即可。
参考文献：
[1]Agrawal R，Gunopulos D，Leymann F.Mining process modelsfrom workflow logs[C]∥Proceedings of the Sixth International Conference on Extending Database Technology.[s.l.]：[s.n.]，1998：469-483.
[2]van der Aalst W M P，Weijters T，Maruster L.Workflow Mining：Discover-ing Process Models from Event Logs[J].IEEE Transactions on Knowledge and Data Engineering，2004（09）：1128-1142.
[3]Herbst J，Karagiannis D.Workflow mining with InWoLve[J].Computers in Industry，2004（53）：245-264.
[4]范玉顺.工作流管理技术基础—实现企业经营过程重组与经营过程自动化的核心技术[M].北京：清华大学出版社，2001.
作者简介：吕克（1963.12-），男，江苏扬州人，现代教育技术管理科科长，研究方向：教育技术研究。
作者单位：扬州大学教务处，江苏扬州 225009