聚类方法综述

文中对聚类方法作了综述。系统地讨论了聚类研究中的4个关键内容:数据点之间"距离"函数的定义方法、类数目的确定、高效优良的聚类算法和聚类算法好坏的评估。分析了各类聚类算法的优劣性,指出了聚类分析研究的发展趋势。     

一种基于尾匹配q-gram的近似串匹配算法

近似串匹配是生物信息学、文本检索、信号处理等领域的一个基础问题,如何提高近似串匹配的速度一直都是研究的关键问题。提出一种新的在大文本库中快速查找近似匹配的无损过滤算法。为保证在大文本库中的匹配速度,本算法使用了查询速度较快的q-gram索引。为通过提高过滤算法的过滤效率达到提升算法整体性能的目的,详细分析了含有匹配串的文本区域,提取了一些基于尾匹配q-gram特征的新过滤条件,然后用这些特征优化了过滤算法的过滤标准。实验数据表明,新过滤条件有效地提高了算法的过滤效率,提升了算法的整体性能。结果显示新算法适合各种匹配错误率下的近似匹配,算法的通用性较强。     

一种基于空间滤波的钢轨表面擦伤检测改进算法

钢轨表面擦伤检测是保障铁路运输安全的重要手段之一。应用图像处理和模式识别技术来处理钢轨数字图像,检测并定位擦伤区域是一种可行且发展迅速的研究手段。课题组在前期工作中提出了一种鲁棒实时的钢轨表面擦伤检测算法,该算法首先对钢轨图像进行灰度对比度增强,在此基础上定位可疑擦伤区域并进行判定。算法对于常规擦伤图像具有较高的检测性能,但对于钢轨图像包含多处擦伤且擦伤区域灰度值差异较大的情况,往往造成漏检。针对原算法的不足,提出了一种基于空间滤波的钢轨表面擦伤检测改进算法,该算法对原算法检测到的擦伤区域进行钢轨灰度图均值填充,并对填充后的图像进行二次检测,在重新生成的灰度对比度图中,原检测图像中灰度值不明显的擦伤区域的灰度对比度值得到增强,从而增加了检出的可能性。经实验结果验证,改进算法具有较高的检测性能:在总的时间耗费没有明显增加的情况下,检测的平均准确率为90.8%,平均漏检率为4.0%,较原算法有较大改善。     

基于混合图像分割与梯度算法的发光物体图像重建技术研究

传统的图像重建算法存在光源分布不均以及噪声干扰等问题,导致图像重建效果差。针对该问题,提出了一种改进的混合图割算法和梯度算法的发光体图像重建技术。算法首先采用图像分割算法得到在未知先验条件的情况下的发光源情况;然后利用不同的梯度算法,根据重建状态得到发光源准确的分布情况;最后利用内部光源的多级网络提高计算速度和重建的准确性。仿真实验结果表明,本方法即使在存在检测噪声和模型结构误差的情况下,仍然能够得到很好的重建性能,具有较高的实际应用价值。     

代数约简的条件信息熵表示及其高效约简算法

给出如何保持正区域不变的语义分析,提出一种修正条件信息熵计算公式,证明保持修正条件信息熵不变与保持正区域不变相互等价。在此基础上,给出代数约简概念的修正条件信息熵表示。给出反例说明修正条件信息熵不具有单调性,导致没法给出自底向上的启发式约简算法,证明了代数协调集中不可删除属性的不可逆性质,提出一种自顶向下直接删除属性的高效约简算法。它从所有条件属性集出发,逐步删除不必要的属性,只需遍历各属性一次,即可保证得到原始决策表的一个代数约简。数值算例和实验验证了该算法的正确性和高效性。     

云环境下基于Canopy聚类的FCM算法研究

FCM算法是目前广泛使用的算法之一。,针对FCM聚类质量和收敛速度依赖于初始聚类中心的问题,结合Canopy聚类算法能够粗略快速地对数据集进行聚类的优点,提出了一种基于Canopy聚类的FCM算法。该算法通过将Canopy算法快速获取到的聚类中心作为FCM算法的输入来加快FCM算法收敛速度。并在云环境下设计了其MapReduce化方案,实验结果表明,MapReduce化的基于Canopy聚类的FCM算法比MapReduce化的FCM聚类算法具有更好的聚类质量和运行速度。     

基于综合散列度的拓扑探测源选取方法

在对非授权目标网络进行拓扑发现时,探测源的选取直接决定拓扑发现的效果,当探测源数量一定时,恰当地从备选探测源集合选取探测源组合可以使得拓扑发现的范围大大增加。针对该问题设计了一种描述探测源组合整体逻辑距离的指标——探测源综合散列度,并利用实验证明综合散列度较大的探测源组合倾向于发现更大范围的拓扑结构;提出了最大综合散列度选取法,即从备选探测源集合选取综合散列度最大的探测源组合进行拓扑探测。随后,对常被运用于电力网规划的混合遗传模拟退火算法进行定制处理,用于更准确地选取综合散列度最大的探测源组合。通过实验,证明了与SDIS选取法、低连接度选取法和随机选取法相比,最大综合散列度选取法选取得到的探测源可以发现更多的路由接口和路由链接。     

一种双权重参数的RFID防碰撞Q值算法研究

标签防碰撞算法是RFID技术研究的热点,也是高强度、大规模应用的关键。在研究了EPC-C1G2标准防碰撞机制中推荐的Q值调整算法的特点后,针对其不足,提出了一种双参数的Q值调整算法——ODWQA,详细阐述了算法的思想、运算流程和关键参数确定方法。在ODWQA算法中,将单一的调整参数c分解为两个权重参数c1和c2,分别对应着碰撞和空闲两种情况,用来调控碰撞时隙和空闲时隙的个数。接着通过实验分析,确定了在不同Q值条件下权重参数c1和c2的最优取值。最后对ODWQA算法进行了仿真测试,结果表明,该算法能够有效减少碰撞时隙的个数,增大系统的吞吐率,降低标签的识别时延。     

带隐变量的回归模型EM算法

带有隐变量的回归模型具有非常广泛的应用场合,隐回归模型的参数求解问题依赖于自变量的分布假设。基于自变量的beta分布的假设条件,给出了隐回归模型的EM算法,详细地推导了模型中的参数求解过程,给出了使用牛顿法求解beta分布参数的算法,并提出一个合适的初值选择算法。在模拟数据和真实数据的基础上进行了详细的比较性试验,结果表明,对具有不同分布特征的因变量观察值,EM算法能够有效地求解隐回归模型的参数。     

游戏场景中基于势场的交互寻路方法

在即时战略游戏中,路径规划是一种重要且常见的任务。游戏的实时性要求玩家能够快速寻找一条进攻的路径,而且游戏单元之间普遍存在的交互作用对寻路质量有着重要的影响。传统的寻路算法如Dijkstra算法虽然能够找到最优路径,但是耗时较多,而且未体现真实游戏中的交互。为此选取RTS游戏中一种典型的攻防场景,提出基于人工势场的快速高效动态寻路方法,同时为了体现RTS中游戏单元之间的交互性,将模糊测度引入到势场寻路中。实验结果表明,采用人工势场法寻路较Dijkstra算法耗时少、路径平滑;而引入模糊测度体现了真实游戏中单元之间的交互影响作用,与真实的游戏场景更为接近。