k-均值算法的初始化方法综述

k-均值问题自提出以来一直吸引组合优化和计算机科学领域的广泛关注, 是经典的NP-难问题之一. 给定N个d维实向量构成的观测集, 目标是把这N个观测点划分到k(\leq N)个集合中, 使得所有集合中的点到对应的聚类中心距离的平方和最小, 一个集合的聚类中心指的是该集合 中所有观测点的均值. k-均值算法作为解决k-均值问题的启发式算法,在实际应用中因其出色的收敛速度而倍受欢迎. k-均值算法可描述为: 给定问题的初始化分组, 交替进行指派(将观测点分配到离其最近的均值点)和更新(计算新的聚类的均值点)直到收敛到某一解. 该算法通常被认为几乎是线性收敛的. 但缺点也很明显, 无法保证得到的是全局最优解, 并且算法结果好坏过于依赖初始解的选取. 于是学者们纷纷提出不同的初始化方法来提高k-均值算法的质量. 现筛选和罗列了关于选取初始解的k-均值算法的初始化方法供读者参考.     

k-平均问题及其变形的算法综述

k-平均问题是计算机科学和组合优化领域的经典问题之一.k-平均聚类作为最受重视而且最简单易懂的一种聚类分析方法流行于数据挖掘领域.k-平均问题可描述为:给定n个元素的观测集,其中每个观测点都是d维实向量,目标是把这n个观测点划分到k(≤n)个集合中,使得所有集合中的点到对应的聚类中心的距离的平方和最小,其中一个集合的聚类中心指的是该集合中所有观测点的均值.k-平均问题在理论上是NP-难的,但有高效的启发式算法,广泛应用在市场划分、机器视觉、地质统计学、天文学和农业等实际背景中.随着实际问题中遇到的k-平均问题更加复杂,数据量更加庞大,还需学者进行更深一步的研究.罗列出k-平均问题及其诸多变形及推广问题的经典算法,并总结k-平均中尚待研究的若干问题.     

关于k-消去二分图的一些结果

图 G的一个 k-正则支撑子图称为 G的 k-因子 ,若对 G的任一边 e,图 G- e总存在一个 k-因子 ,则称 G是 k-消去图 .证明了二分图 G=( X,Y) ,且 | X | =| Y|是 k-消去图的充分必要条件是 k| S|≤ r1 + 2 r2 +…+ k( rk+… + rΔ) - ε( S)对所有 S X成立 .并由此给出二分图是 k-消去图的充分度条件 .     

奇图的匹配可扩性

设G是一个图,n,k和d是三个非负整数,满足n+2k+d≤|V(G)|-2,|V(G)|和n+d有相同的奇偶性.如果删去G中任意n个点后所得的图有k-匹配,并且任一k-匹配都可以扩充为一个亏d-匹配,那么称G是一个(n,k,d)-图.Liu和Yu[1]首先引入了(n,k,d)-图的概念,并且给出了(n,k,d)-图的一个刻划和若干性质. (0,k,1)-图也称为几乎k-可扩图.在本文中,作者改进了(n,k,d)-图的刻划,并给出了几乎k-可扩图和几乎k-可扩二部图的刻划,进而研究了几乎k-可扩图与n-因子临界图之间的关系.     

Banach空间范数的k-点态粗性和k-粗性

对Banach空间范数引入了k-点态粗和k-粗的概念,利用Banach空间理论的方法,给出了x∈S(X)为范数的k-粗糙点和X的范数是k-粗的一些充分必要条件,证明了(k+1)-粗糙点是k-粗糙点以及k-粗糙点与Fréchet可微性的一些结果.特别地,在k=1的情形下蕴含了关于范数的粗糙点、点态粗范数和粗范数的相应结果.     

关于拟k-连通图的一个注释

G是一个k-连通图,T是G的一个k-点割,若G-T可被划分成两个子图G1,G2,且|G1 |≥2,|G2 |≥2,则称T是G的一个非平凡点割.假定G是一个不含非平凡(k-1)点割的(k-1)-连通图,则称G是一个拟k-连通图.证明了对任意一个k≥5且t＞k/2的整数,若G是一个不含(K2+tK1)的k-连通图,且G中任...     

k-素数和唯一分解

在本文中,作者揭示了唯一k-素因数分解的更深层原因.在第二节中,首先引入S_k中的k-组合条件和费马定理;并证明了下面4论断是等价的:(1) k-组合条件成立,(2)中唯一k-素因数分解成立,(3) Sk中费马定理成立,(4)k=1或2.为了更好地理解k-素数,在第三节中作者考察了一类特殊的k-素数,即3-素数.众所周知唯一3-素因数分解一般是不成立的,那么S₃中的哪些正整数具有唯一3-素因数分解性质呢?在第三节中,作者得到一个S₃中的整数具有唯一3-素因数分解的充要条件.在第三节最后,作者引入π₃(x),它表示小于等于x的3-素数个数.由素数定理,作者得到π₃(x)的一个具体公式以及一些近似公式.     

k-树的补图的最小填充和树宽

一个图的最小填充问题是寻求边数最少的弦母图,一个图的树宽问题是寻求团数最小的弦母图,这两个问题分别在稀疏矩阵计算及图的算法设计中有非常重要的作用．一个k-树G的补图G称为k-补树．本文给出了k-补树G的最小填充数f(G) 及树宽TW(G)．     

Pancake网络的t/k-诊断度及其算法

由于大型多处理机系统规模的不断扩大, 其组件脆弱性也随之增加, 因此故障容错性能对于多处理机系统尤为重要. t/k-诊断分析是一种能极大提高多处理机系统自我诊断性能的系统级故障诊断策略,该诊断策略能识别至多t个故障处理机节点, 其中可能包含至多$k$个被误诊的处理机. 首先给出了Pancake网络P_n(n\geq 5) 的容错性分析, 其后证明了P_n在PMC模型下是((k+1)n-3k-1)/k-可诊断的, 其中1\leq k\leq 3, 最后还给出复杂度为O(NlogN)的快速诊断算法来识别所有的故障节点.     

有元素类型约束的k-划分问题研究

研究有元素类型约束且每个元素权重为正数的k-集合划分问题,元素类型约束指k-划分后每个集合所包含的元素的类型均不同. 该问题是对k-划分问题(k-partitioning problem)的一个拓展,在一人可拥有多技能执照的行业有广泛的应用背景. 提出基于LPT算法思想的贪婪算法,并得出以下结论: k≤2, 该算法给出最优解: k>2, 最坏情况下的性能比为2-m^-1, 这里m指待分配集合的数量.     

关于整数向量卷积的一个算法的时间复杂度

众所周知,两个n维整数向量循环卷积的常规算法(即按定义计算)的时间复杂度为O(n~2),现在已有时间复杂度为O(nlog_2n)的快速算法,[1]中提出一个新算法,称其时间复杂度为O(n),因而是最佳的。 本文首先指出[1]的错误原因,再根据算法分析理论得出[1]中算法的时间复杂度不低于O(n~2log_2n),因而比常规算法的运算量还大。     

关于矩阵乘法的一个改进算法的时间复杂度

两个ｎ阶非负整数方阵相乘,常规算法的时间复杂度为Ｏ（ｎ^３）,文献［１］提出一个“运算次数”为Ｏ（ｎ²）的“最佳”算法,文献［２］对此算法做了进一步研究,提出三种改进策略．本文根据算法分析理论,得出改进后的算法的时间复杂度仍不低于Ｏ（ｎ^３ｌｏｇｎ）,因而其阶仍高于常规算法的运算量的阶．     

关于矩阵乘法的一个算法的时间复杂度

两个n阶非负整数方阵相乘,常规算法的时间复杂度为O(n³),文献[1]提出一个“运算次数”为O(n²)的“最佳”算法,本文根据算法分析理论得出此算法的时间复杂度不低于O(n³log₂ⁿ),因而比常规算法的运算量还大.     

关于最小化最大延迟的分批排序问题的一个动态规划算法的注解（英文）

In parallel-batching machine scheduling, all jobs in a batch start and complete at the same time, and the processing time of the batch is the maximum processing time of any job in it. For the unbounded parallel-batching machine scheduling problem of minimizing the maximum lateness, denoted 1|p-batch|L_(max), a dynamic programming algorithm with time complexity O(n~2) is well known in the literature.Later, this algorithm is improved to be an O(n log n) algorithm. In this note, we present another O(n log n) algorithm with simplifications on data structure and implementation details.     

Complexity analysis of an interior point algorithm for the semidefinite optimization based on a kernel function with a double barrier term

In this paper, we establish the polynomial complexity of a primal-dual path-following interior point algorithm for solving semidefinite optimization(SDO) problems. The proposed algorithm is based on a new kernel function which differs from the existing kernel functions in which it has a double barrier term. With this function we define a new search direction and also a new proximity function for analyzing its complexity. We show that if q1 q2 1, the algorithm has O((q1 + 1) nq1+1/2(q1-q2)logn/ε)and O((q1 + 1)3q1-2q2+1/2(q1-q2)n~1/2 logn/ε) complexity results for large- and small-update methods, respectively.     

随机置换的分量与单调重新构组问题的计算等价性

In this note, it is shown that the monotone reconstruction problem is equi-valent to that of sorting, in the sense of computational complexity. In particular from any given sorting algorithm A, an algorithm B for the monotone reconstruc-tion problem can be developed with at most O(m) time and O( m) space cost more than that used in A, and vice versa. As a consequence of this result, it is obtai-ned that the time complexity of the monotone reconstruction problem of n-ele-ment random permutations is O(nlogn).     

所有点对之间最快路问题

所有点对之间最快路问题就是要在所有点对(Vs，Vt)之间传送数据δs,t,并找出一条最快的路线．解决所有点对之间最快路问题的关键是产生有效解的等价集合．运用动态点对最短路的算法，本文首先设计了一个时间复杂性为O(mn^2)的产生有效解等价集合的算法，然后研究了静态点对之间最快路问题和动态点对之间最快路问题，其算法的时间复杂性分别为O(mn^2)和O(m^2n^2)．最后本文研究了求和对最小的路问题，证明该问题可以在O(mn^2)时间内解决．     

计算周期三对角矩阵行列式和逆矩阵的新算法

给出了一种计算周期三对角矩阵行列式和逆矩阵的新递推算法,它们的运算复杂度分别为O(n)和O(n2),该算法是文献[5]和[6]中相关算法的拓广.     

一种基于能量的RNA二级结构预测的动态划分算法

预测单链RNA分子序列的二级结构是计算生物学中的一个重要内容.本文基于RNA分子结构的稳定性原理.提出了一种预测RNA二级结构的新算法——基于能量的动态划分算法.该算法的空间复杂度仅为O(n),时间复杂度近似为O(n2·logn),且预测结构有较好的精度.     

精确覆盖问题的加权分治算法

精确覆盖问题是组合优化中经典的NP-Hard问题之一,其在诸多领域具有广泛的应用价值。本文首先研究了精确覆盖问题的数学性质,并根据数学性质提出相应的分支降阶规则以缩小问题的规模;接着设计了一个基于分支降阶的回溯算法求解该问题;然后运用常规技术分析得出该精确算法的时间复杂度为O(1.4656^k);最后运用加权分治技术对该算法的时间复杂度进行分析,将该算法的时间复杂度降为O(1.3842^k)。文章最后通过一个示例进一步阐述该算法的原理,并与其他精确算法进行了对比分析,研究结果表明该算法是可行的,也是有效的。