摘要:聚类分析是统计学、模式识别和机器学习等领域的研究热点.通过有效的聚类分析，数据集的内在结构与特征可以被很好地发掘出来.然而，无监督学习的特性使得当前已有的聚类方法依旧面临着聚类效果不稳定、无法对多种结构的数据集进行正确聚类等问题.针对这些问题，首先将K-means算法和层次聚类算法的聚类思想相结合，提出了一种混合聚类算法K-means-AHC；其次，采用拐点检测的思想，提出了一个基于平均综合度的新聚类有效性指标DAS（平均综合度之差，difference of average synthesis degree），以此来评估K-means-AHC算法聚类结果的质量；最后，将K-means-AHC算法和DAS指标相结合，设计了一种寻找数据集最佳类簇数和最优划分的有效方法.实验将K-means-AHC算法用于测试多种结构的数据集，结果表明：该算法在不过多增加时间开销的同时，提高了聚类分析的准确性.与此同时，新的DAS指标在聚类结果的评价上要优于当前已有的常用聚类有效性指标.

摘要:时钟约束语言CCSL是一种用于描述实时嵌入式系统中事件之间约束的形式化语言，它是UML针对实时嵌入式系统建模的扩展包MARTE （modeling and analysis of real-time and embedded systems）中用于对时间建模的一个子语言.给定一组由CCSL定义的时钟约束条件，需要判断是否存在某种调度策略满足约束、是否所有满足这些约束的行为都不会导致系统死锁等分析.目前已经有一定的针对CCSL的形式化分析研究工作，如基于状态迁移系统与时间自动机的方法等.但这些方法要么只针对某种特定的分析，要么只适用于部分CCSL约束，要么分析效率较低.提出了基于SMT的统一且高效的CCSL形式化分析方法.统一性体现在其可用于有效性证明、迹分析、死锁检测、LTL模型检测等方面的验证与分析.基于该方法开发了原型工具，同时支持上述4种验证功能.工具集成了当前最高效的SMT求解器Z3和CVC4.得益于SMT求解器的高效性，实验中大部分的验证可以在短时间内完成.

摘要:确定数据集的聚类数目是聚类分析中一项基础性的难题.常用的trail-and-error方法通常依赖于特定的聚类算法,且在大型数据集上计算效率欠佳.提出一种基于层次思想的计算方法,不需要对数据集进行反复聚类,它首先扫描数据集获得CF(clustering feature,聚类特征)统计值,然后自底向上地生成不同层次的数据集划分,增量地构建一条关于不同层次划分的聚类质量曲线;曲线极值点所对应的划分用于估计最佳的聚类数目.另外,还提出一种新的聚类有效性指标用于衡量不同划分的聚类质量.该指标着重于簇的几何结构且独

摘要:缺乏特征模型的有效性维护功能已经成为目前特征造型系统存在的一个严重而亟待解决的问题.在对特征有效性条件进行深入分析的基础上,提出了一个基于扩展属性邻接图(extended attributed adjacency graph,简称EAAG)的特征有效性表示方法,特别是提出了基于局部特征识别的特征有效性维护新方法.该方法不仅能够自动判别特征的有效性是否被破坏,而且能确定导致特征无效的原因和遭破坏后特征的状态,从而能够根据用户的意图自动维持特征模型的有效性.

摘要:如何提供不同的服务质量(quality of service,简称QoS)是互联网络面临的一个重要问题,而服务质量路由(quality-of-service routing,简称QoSR)则是其中的核心技术和热点问题.QoSR的主要作用是为QoS业务请求寻找可行路径,这体现了QoSR的两个目标:(1) 满足业务QoS需求;(2) 最大限度地提高网络利用率.由于QoSR是NP完全问题,研究者们设计了很多启发式算法进行了广泛深入的研究.在有权图和QoS度量的基础上介绍了QoSR的基本概念,详细分析了面向单播应用的QoSR算法中的热点问题,并按照所求解的问题类型和求解方法,将这些算法分成以下几类:多项式非启发类、伪多项式非启发类、探测类、限定QoS度量类、路径子空间搜索类、QoS度量相关类、花费函数类和概率求解类.在分析每类中典型算法的基础上,总结和对比了各类的特点,进而详细剖析了算法的有效性,并基于此总结了基于概率模型求解QoSR问题的方法.最后指出了该领域中需要进一步研究的热点问题.