抽样子空间约束改进大数据谱聚类算法

在分析经典谱聚目标函数与加权核k-means目标函数等价基础上,设计了一种基于抽样子空间约束的改进大规模数据谱聚类算法,算法通过加权核k-means迭代优化避免矩阵特征分解的大量资源被占用,通过数据抽样及聚类中心的子空间约束,避免全部核矩阵都被使用,从而降低经典算法的时间空间复杂度。理论分析和实验结果表明,改进算法保持与经典算法相近聚类精度,提高了聚类效率,验证了改进算法的有效性。     

Balanced multiple controllers placement with latency and capacity bound in software-defined network

Software-defined network (SDN) used a network architecture which separates the control plane and data plane. The control logic of SDN was implemented by the controller. Because controller's capacity was limited, in large scale SDN networks, single controller can not satisfy the requirement of all switches. Multiple controllers were needed to han-dle all data flows. By the reason that the latency between controller and switch would significantly affect the forwarding of new data flow, the rational placement of controllers would effectively improve the performance of entire network. By partition the network into multiple sub domains, on the base of spectral clustering, a method that added a balanced de-ployment object function into k-means was given and a balanced multiple controllers placement algorithm in SDN net-works which has the latency and capacity limitations was proposed. In this approach, a penalty function was introduced in the algorithm to avoid isolation nodes appearing. The simulations show that this algorithm can balance partition the net-work, keep the latency between controller and switch small and keep loads balancing between controllers.     

Inferring road maps from sparsely sampled GPS traces

We propose a novel segmentation-and-grouping framework for road map inference from sparsely sampled GPS traces. First, we extend Density-Based Spatial Clustering of Application with Noise with an orientation constraint to partition the entire point set of the traces into point clusters representing the road segments. Second, we propose an adaptive k-means algorithm that the k value is determined by an angle threshold to reconstruct nearly straight line segments. Third, the line segments are grouped according to the ‘Good Continuity’ principle of Gestalt Law to form a ‘Stroke’ for recovering the road map. Experimental results demonstrate that our algorithm is robust to noises and sampling rates. In comparison with previous work, our method has advantages to infer road maps from sparsely sampled GPS traces.     

基于最小聚类求解k-means问题算法

针对每个划分子集要求至少满足一定数量点的k-means问题,设计了该问题的随机近似算法.给出一个样本子集,证明了该样本子集至少以1/2的概率包含每个最优子集中至少一个点,进一步设计近似度为2的随机算法.设计了该问题的(1+ε)随机近似算法,算法的成功概率至少为3/2k+2.利用取样技术,设计了k-means问题的局部搜索随机算法.     

无线传感器网络事件簇的数据聚集容错机制

针对数据聚集操作的容错要求,提出了事件簇的数据聚集容错机制EFSA.在生成事件簇的基础上,采用k-means算法提取加权平均数作为近似的事件值,并且计算和迭代地调整节点的可信度,作为聚集计算的数据权值和节点是否出现数据错误的指标.分析和实验表明,EFSA机制能够削弱数据错误的影响,实现数据聚集的正确性与可靠性.     

Comparison of Clustering Methods in Yeast Saccharomyces Cerevisiae

In recent years,microarray technology has been widely applied in biological and clinical studies for simultaneous monitoring of gene expression in thousands of genes.Gene clustering analysis is found useful for discovering groups of correlated genes potentially co-regulated or associated to the disease or conditions under investigation.Many clustering methods including k-means,fuzzy c-means,and hierarchical clustering have been widely used in literatures.Yet no comprehensive comparative study has been performed to evaluate the effectiveness of these methods,specially,in yeast saccharomyces cerevislae.In this paper,these three gene clustering methods are compared.Classification accuracy and CPU time cost are employed for measuring performance of these algorithms.Our results show that hierarchical clustering outperforms k-means and fuzzy c-means clustering.The analysis provides deep insight to the complicated gene clustering problem of expression profile and serves as a practical guideline for routine microarray cluster analysis of gene expression.     

基于KNN的Deep Web数据源分类研究

针对Deep Web的查询需求,文章提出了改进的对Deep Web数据源的分类方法:在对数据源进行分类时,采用了KNN分类算法来进行。由于KNN分类算法的K值选的过大或者过小都会对分类结果产生影响,因此提出了对K值进行优化的改进的KNN算法。文章利用k-means聚类算法来进行聚类,分别计算取得每个类别的k个距离相近的数据并计算这k个数据到聚类中心的距离,把这个距离的倒数作为该数据点对分类结果的贡献值。对训练集进行聚类后返回聚类中心,根据聚类中心计算权重,从而进一步来计算每个类别中k个最近邻贡献值之和S,选取S最大的类别作为测试数据的类别来进行分类,从而可达到比较好的分类效果。     

基于视觉词袋模型的图像分类改进方法

文中主要基于视觉词袋（BOVW, Bag-Of-Visual-Words）模型对图像进行分类处理,并对传统视觉词袋模型存在的不足进行了改进,提出了一种基于视觉词典的权重直方图来表达图像,采用优化的k-means聚类算法（k-means+）用于视觉词典的构建,代入KNN（K-Nearest-Neighbors）分类器进行分类。通过对Caltech 101和Caltech 256这两个经典数据库进行实验,实验结果表明该改进方案较传统方法提高了分类的正确率。     

基于自适应最优聚类的目标匹配跟踪算法

提出了一种基于新的自适应最优聚类的模板匹配跟踪方法。利用模式分类准则计算最优聚类数,然后根据最优聚类数采用k-均值方法进行多次聚类。根据聚类结果计算熵矢量和距离矢量,组合得到特征矢量,利用特征矢量进行匹配跟踪。匹配采用简单的相似性准则,实时模板更新算法为多模更新。测试结果表明,该算法针对不同的目标能自适应地选择聚类参数,在目标发生几何变化时,能实现精确稳定的跟踪。     

A local search approximation algorithm for k-means clustering

In k-means clustering we are given a set of n data points in d-dimensional space and an integer k, and the problem is to determine a set of k points in  , called centers, to minimize the mean squared distance from each data point to its nearest center. No exact polynomial-time algorithms are known for this problem. Although asymptotically efficient approximation algorithms exist, these algorithms are not practical due to the very high constant factors involved. There are many heuristics that are used in practice, but we know of no bounds on their performance.

We consider the question of whether there exists a simple and practical approximation algorithm for k-means clustering. We present a local improvement heuristic based on swapping centers in and out. We prove that this yields a (9+)-approximation algorithm. We present an example showing that any approach based on performing a fixed number of swaps achieves an approximation factor of at least (9−) in all sufficiently high dimensions. Thus, our approximation factor is almost tight for algorithms based on performing a fixed number of swaps. To establish the practical value of the heuristic, we present an empirical study that shows that, when combined with Lloyd's algorithm, this heuristic performs quite well in practice.