半监督二次划分聚类算法及其报表系统应用  

Semi-supervised Quadratic Partitional Clustering Algorithm and its Application in Spreadsheet System

作　　者：赵立永[1] 赵冲冲[1] 时鹏[1] 胡长军[1] 

机构地区：[1]北京科技大学信息工程学院,北京100083

出　　处：《小型微型计算机系统》2011年第3期499-505,共7页Journal of Chinese Computer Systems

基　　金：国家"八六三"高技术研究发展计划基金项目(2008AA01Z109)资助

摘　　要：在基于B/S结构的Web报表系统中,报表单元格之间往往存在着复杂的依赖关系,某一单元格的求值过程会进行大量的涉及到其它单元格的公式计算,而在多用户访问的情况下,这种计算开销更为可观,导致服务器负载过重,响应速度变慢.优化报表的计算任务,可以有效减少计算量和减轻服务器端负载.为此本文提出一种半监督二次划分聚类算法,在单元格聚类的基础上,以报表单元格为顶点,以单元格之间的引用关系为有向边建立有向最大无环子图,然后通过协同计算各有向最大无环子图的拓扑序列,从而获得较优的计算顺序,达到提高Web报表计算效率,减轻服务器负载的目的.通过该算法与常规算法的对比试验,验证了其能有效降低计算量,提高系统响应速度.该算法已经成功应用于实际的Web报表系统中,表现出良好的实用性.The evaluation of a cell in spreadsheet may cost a mass of formula computing because of complicated dependency relationships among ceils. In particular, computational cost is more considerable when many users simultaneously access the Web spreadsheet system on Browser/Server structure. Fast response and light server load can be achieved by optimizing the computation task of spreadsheet. This paper proposes a semi-supervised quadratic partitional clustering algorithm to acquire more optimal computation sequence. Topological sorting of directed maximum acyclic graph, which is constituted with vertex （ spreadsheet cell } and directed edge { citation relations between cells） based on cell clustering, is cooperatively computed in order to increase computation efficiency and reduce the server load. Comparative experiments show that the algorithm can efficiently decrease the amount of calculation and increase system response speed. In addition, the algorithm has been applied in practical Web spreadsheet system and shown favorable practicability.

关 键 词：半监督二次划分聚类算法 WEB报表 有向无环图 依赖关系 拓扑排序 报表单元格 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]