位置：成果数据库 > 期刊 > 期刊详情页
基于初始点选取的k-means聚类近似常数算法
  • ISSN号：1000-1239
  • 期刊名称：《计算机研究与发展》
  • 时间：0
  • 分类：TP391[自动化与计算机技术—计算机应用技术;自动化与计算机技术—计算机科学与技术]
  • 作者机构：山东大学计算机科学与技术学院,济南,250100, 山东交通学院信息工程系,济南,250023 山东大学计算机科学与技术学院,济南,250100 山东大学计算机科学与技术学院,济南,250100
  • 相关基金：国家自然科学基金项目(60573024)
作者： 王守强, 朱大铭, 韩爱丽
关键词： k-means, 聚类, 质心点, ε可分割性
中文摘要：

k-means聚类是聚类划分中应用最广泛的一种方案,但是现在许多关于此问题的研究并没有给出近似比为常数的算法.给出了一个随机算法,该算法通过以不同概率选取初始k个点,保证了以一定概率分别属于不同最优聚类簇的k个点.以这k个点作为初始中心点对输入点集进行交换分别执行局部搜索算法,证明了可得到近似比至多为2的解.实验结果表明该算法能够取得较优的近似解结果.

同期刊论文项目
基因组重组比较算法与复杂性研究
期刊论文 15 会议论文 4 著作 1
同项目期刊论文
有向无环图最小度生成树问题的一种近似算法
欧氏空间货郎担问题的一个多项式时间近似方案的改进与实现
A 1.75-approximation algorithm for unsigned translocation distance
Faster algorithms for sorting by transpositions and sorting by block interchanges
A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with
A (1.5+()-approximation algorithm for unsigned translocation distance
两元指纹向量聚类问题的复杂性与改进启发式算法
一般设施定位问题计算复杂度和近似算法研究
有向基因组反转和转位排序最小权重问题的1.5k近似算法
基因组一般移位排序问题的多项式时间算法
合取范式3可满足问题的局部搜索近似算法
带约束最长公共子序列快速算法
求解K-means聚类更有效的算法
基于最小聚类划分的K-means聚类(1+ε)近似算法
期刊信息
  • 《计算机研究与发展》
  • 中国科技核心期刊
  • 主管单位:中国科学院
  • 主办单位:中国科学院计算技术研究所
  • 主编：徐志伟
  • 地址：北京市科学院南路6号中科院计算所
  • 邮编：100190
  • 邮箱：crad@ict.ac.cn
  • 电话：010-62620696 62600350
  • 国际标准刊号：ISSN：1000-1239
  • 国内统一刊号：ISSN：11-1777/TP
  • 邮发代号:2-654
  • 获奖情况:
  • 2001-2007百种中国杰出学术期刊，2008中国精品科...,中国期刊方阵“双效”期刊
  • 国内外数据库收录:
  • 俄罗斯文摘杂志,荷兰文摘与引文数据库,美国工程索引,日本日本科学技术振兴机构数据库,中国中国科技核心期刊,中国北大核心期刊（2004版）,中国北大核心期刊（2008版）,中国北大核心期刊（2011版）,中国北大核心期刊（2014版）,中国北大核心期刊（2000版）
  • 被引量:40349