聚类算法在少数民族文化的应用 本文关键词：民族文化，算法
聚类算法在少数民族文化的应用 本文简介：1引言少数民族文化内容丰富，形式多样。其中少数民族节日是民族文化中特点鲜明，底蕴深厚，最具特色的文化现象之一，是展现民族文化的最好平台。通过分析贵州黔南布依族苗族自治州民族节日的现状和特点，认为采用数字化技术可以实现对民族节日快速有效地整理和保护。对民族节日进行半结构化数据建模、存储，有助于指导民族
聚类算法在少数民族文化的应用 本文内容：
1引言
少数民族文化内容丰富，形式多样。其中少数民族节日是民族文化中特点鲜明，底蕴深厚，最具特色的文化现象之一，是展现民族文化的最好平台。通过分析贵州黔南布依族苗族自治州民族节日的现状和特点，认为采用数字化技术可以实现对民族节日快速有效地整理和保护。对民族节日进行半结构化数据建模、存储，有助于指导民族文化数字化生成和民族文化的自动分类等领域。当前对数字文化模型的研究有岩刻图案的数字化研究［1］，古希腊陶瓷的3D模型［2］，剪纸文化的数据模型［3－4］，这些研究都提取了研究对象的文化特征，进行数据建模，但研究都局限于对对象图像上的模型设计，没有考虑到对文化内涵的进一步挖掘设计。本文以黔南布依族苗族自治州少数民族节日为研究对象，创建了符合少数民族节日的XML子树序列表示，有效保存了XML节点的路径和层次信息。在此基础上从XML文档的路径、节点层次、权重综合计算相识度出发，提出一种基于子树的XML相似度计算方法，对k-means算法进行改进，设计了一种新的增量式聚类算法。实验证明该算法能提高XML数据聚类的质量，以实现民族文化的数字化建设。
2增量式聚类算法
少数民族节日数量多，内容丰富多彩，表现形式多样，每一个节日都是展示民族文化的平台和传承文化的载体。但是由于贵州黔南少数民族大杂居小聚居的分布特点，使得少数民族节日具有很大程度上的场所选择性、地方性、时令性［5－6］。同一民族，由于居住地不同，同一节日的时间、名称、内容可能不完全一样。针对以上数据特点，用传统关系数据库无法完整记录节日信息。XML是一种允许用户对自己的标记语言进行定义的源语言，可用来标记数据、定义数据类型。XML是实现程序之间、用户之间、计算机与用户之间以及本地数据与网络数据之间结构化信息共享中使用最广泛的格式之一。XML具有自描述性、层次性、可扩展性，适合民族文化数据的半结构化数据建模。通过分析民族文化的特点，生成相应的XML文档，将XML文档中的元素和属性转换成树的节点，XML文档中的元素之间的关系转换为树的边。得到的XML文档树表示如图1所示。文档树中holiday表示一个具体的节日，可以实现不同层次上的内容检索。
2．1XML文档的相似度计算
目前聚类算法主要有划分聚类［7－8］和层次聚类［9］，算法的核心是XML文档的相似度计算。图1的XML文档树包含的节点个数较多，不同层次包含的相同节点所表示的含义不同，用基于树编辑距离和pg-gramsp［10］的方法计算XML文档树之间的相似度比较困难。将XML文档树划分成若干能代表独立信息的子树，综合所有子树的相似度得到整个XML文档树的相似度。定义1(XML子树的序列表示):XML子树的序列表示为T=(N，P，V，nr)，其中:N是有限的结点集合;nr∈N，表示树的唯一根结点;P是N中结点到后续结点的映射，p=(n’，n)∈P，n∈N(n≠nr)，n’≠n，n’为父结点，n为子结点;V表示赋值的集合，v=(n，s)，s为简单类型的值，n∈N。定义2(子树划分):对于一棵XML文档树T，去掉根节点后，生成n棵子树{t1，…tn}，(n≥2)。(本文中所有的XML文档树的根节点都有多个子节点。)定义3(候选子树)如果子树ti(1≤i≤n)的节点个数大于2，则为候选子树，候选子树包含了独立信息，需要计算相似度。如果子树ti的节点个数小于等于2，只有文本信息，不包含结构信息，则不计算相似度。定义4(候选子树序列表示):如果子树ti(1≤i≤n)有m个节点，按先根遍历编号排序，候选子树序列表示为{{v1，p1，w(v1)}，．．{vj，pj，w(vj)}．．{vm，pm，w(vm)}}，(1≤j≤m)。vj表示节点标签;pj表示该节点父节点的先根遍历编号，根据pi的值可以保存节点的路径结构信息，子树根节点的p1为0;w(vj)表示节点权重，w(vj)=(1/2)i－1，i表示节点的层次。在XML文档中，不同层次节点的信息概括能力不同，高层节点信息概括能力强，对文档的作用大。(1)定义6(文档树相似度计算):假设T1和T2为XML文档树，T1被划分成m棵候选子树t1i(1≤i≤m)，T2被划分成n棵候选子树t2j(1≤j≤n)。计算T1和T2的相似性需要进行m次计算。每次在T2的所有候选子树中找出和T1的候选子树t1i(1≤i≤m)有相同根节点的候选子树进行相似度计算，记录下最大相似度值sim(t1i，t2j)。如果没有根节点相同的子树，则相似度为0。最后通过计算(2)。
2．2基于划分的增量式聚类算法
本文在k-means算法的基础上进行改进，设计了一种基于划分的增量式聚类算法。该算法可以随时处理新的XML文档，动态调整聚类的簇心，提高聚类内部的相似度，保证高质量的聚类生成。同时可以设定不同的最小相似度阀值λ，以达到不同的聚类效果。算法的时间复杂度为O(n)，n表示输入的XML文档数。算法的具体步骤如下:输入:输入一个XML文档树T、最小相似度阀值λ输出:聚类集合C(1)如果当前聚类集合C为空，则生成一个新的聚类C1，T并入C1，并且C1的簇心设置为T。C=C∪C1。(2)否则，如果聚类集合C已有n个聚类，计算T与每个聚类Ci(1≤i≤n)簇心Ti1的相似度similarity(T，Ti1)．，满足λ≤similarity(T，Ti1)≤1，取具有最大相似度的聚类Ci，执行步骤3);如果没有找到满足条件的聚类Ci，则执行步骤4)。(3)T并入Ci，重新计算Ci的簇心。分别计算Ci中的每一个文档树与Ci中其余文档树相似度之和，相似度之和最高的文档树设置为Ci的新簇心。(4)否则，生成一个新的聚类Cn+1，T并入Cn+1，并且聚类Cn+1的簇心设置为T。C=C∪Cn+1。
2．3实验分析
为了验证基于划分的增量式聚类算法在民族节日挖掘中的可行性。验证了公式(1)和(2)的有效性，本文与文献［11］的计算对比结果如图2所示。本文提出的相似度计算是针对路径的完全匹配。对于满足树嵌入匹配的XML文档能得到较高的相似度。图2XML文档树相似度对比同时本文选取了黔南地区的85个节日作为测试数据，所有节日均用XML描述。采用基于划分的增量式聚类算法进行聚类后，生成6个聚类，每个聚类中都包含相同的地域信息，召回率为85．3%。
3结束语
针对民族文化特点，用XML文档保存民族文化信息，提出了XML子树的序列表示方法和基于子树的相似度计算方法，通过实验验证基于划分的增量式聚类算法在民族节日挖掘中的可行性。本文的下一步研究为继续将XML技术应用于实现民族数字化。
作者：任廷艳 单位：黔南民族师范学院 计算机与信息学院 地方民族文化数字化工程研究中心
聚类算法在少数民族文化的应用 来源：网络整理
免责声明：本文仅限学习分享，如产生版权问题，请联系我们及时删除。
相关文章