求解大规模谱聚类的近似加权核k-means算法

谱聚类将聚类问题转化成图划分问题,是一种基于代数图论的聚类方法.在求解图划分目标函数时,一般利用Rayleigh熵的性质,通过计算Laplacian矩阵的特征向量将原始数据点映射到一个低维的特征空间中,再进行聚类.然而在谱聚类过程中,存储相似矩阵的空间复杂度是O(n²),对Laplacian矩阵特征分解的时间复杂度一般为O(n³),这样的复杂度在处理大规模数据时是无法接受的.理论证明,Normalized Cut图聚类与加权核k-means都等价于矩阵迹的最大化问题.因此,可以用加权核k-means算法来优化Normalized Cut的目标函数,这就避免了对Laplacian矩阵特征分解.不过,加权核k-means算法需要计算核矩阵,其空间复杂度依然是O(n²).为了应对这一挑战,提出近似加权核k-means算法,仅使用核矩阵的一部分来求解大数据的谱聚类问题.理论分析和实验对比表明,近似加权核k-means的聚类表现与加权核k-means算法是相似的,但是极大地减小了时间和空间复杂性.     

多值Łukasiewicz逻辑公式的范式表示和计数问题

将符号化计算树逻辑中的Shannon展开式做了推广,在n值Łukasiewicz逻辑系统Łn中,研究了由逻辑公式导出的n值McNaughton函数的展开式,给出了m元n值McNaughton函数的准析取范式和准合取范式.在此基础上,给出了m元n值McNaughton函数的计数问题,并在n值Łukasiewicz逻辑系统Łn中,给出了m元逻辑公式的构造方法及其逻辑等价类的计数问题.     

基于距离比值的迭代分形图

由于逃逸时间算法不能绘制函数收敛区域,所以现有的分形图大都存在大片的黑色区域.提出一种新的构造分形图的方法:距离比值迭代法.该方法采用两点迭代,利用其距离比值的收敛次数来绘制分形图.利用距离比值迭代法绘制了复映射z←z^α+c的广义M-J集并分析其构图性质.距离比值广义M-J集的内部收敛区域具有复杂的细节和自相似结构,当α>0时其外部边界与经典M-J集一致,当α<0时能够绘制出经典M-J集所没有的复杂结构.     

支持多约束的K-匿名化方法

K-匿名化(K-anonymization)是数据发布环境下保护数据隐私的一种重要方法.目前,K-匿名化方法主要针对单一约束条件进行处理,而实际应用中涉及到大量的多约束条件,使K-匿名化问题更加复杂.如果简单地将单一约束K-匿名化方法应用到多约束情况,会造成大量的信息损失及过低的处理效率.根据多约束之间的关系,通过继承Classfly算法的元组概括过滤思想,提出多约束K-匿名化方法Classfly⁺及相应的3种算法,包括朴素算法、完全IndepCSet算法和部分IndepCSet的Classfly⁺算法.实验结果显示,Classfly⁺能够很好地降低多约束K-匿名化的信息损失,改善匿名化处理的效率.     

单向Hash函数的一种构造方法*

单向Hash函数已成为密码学的一个重要组成部分．给定任一定长单向Hash函数f：∑^m→∑^t,m>t，本文给出了利用f构造一单向Hash函数F的一种新方法，该方法易于并行化．     

模糊聚类计算的最佳算法

给出模糊关系传递闭包在对应模糊图上的几何意义,并提出一个基于图连通分支计算的模糊聚类最佳算法.对任给的n个样本,新算法最坏情况下的时间复杂性函数T(n)满足O(n)≤T(n)≤O(n²).与经典的基于模糊传递闭包计算的模糊聚类算法的O(n³logn)计算时间相比,新算法至少降低了O(n相似文献   

基于节点向量表达的复杂网络社团划分算法

社团结构划分对复杂网络研究在理论和实践上都非常重要.借鉴分布式词向量理论,提出一种基于节点向量表达的复杂网络社团划分方法（CDNEV）.为了构建网络节点的分布式向量,提出启发式随机游走模型.利用节点启发式随机游走得到的节点序列作为上下文,采用SkipGram模型学习节点的分布式向量.选择局部度中心节点作为K-Means算法的聚类中心点,然后用K-Means算法进行聚类,最终得到社团结构.在真实和模拟两种网络上做了丰富的实验,与主流的全局社团划分算法和局部社团划分算法作了比较.在真实网络上CDNEV算法的F1指标比其他算法平均提高19%;在模拟网络上,F1指标则可以提高15%.实验结果表明,相对其他算法,CDNEV算法的精度和效率都较高.     

隐函数的布尔操作

若隐函数曲面由等式f(x,y,z)=0定义,则其相对应的实体满足不等式f(x,y,z)≥0,对这种实体的并、交、差等布尔操作采用R-函数来实现.特别地,由Metaball定义的隐函数,除具有隐函数的一般性质外,还可用于实体造型中的过渡及变形控制等.证明了用R-函数实现实体的布尔操作的可行性及Metaball模型在几何造型中能光滑过渡等性质.     

基于距离不等式的K-medoids聚类算法

本文研究加速K-medoids聚类算法,首先以PAM（Partitioning Around Medoids）、TPAM（Triangular Inequality Elimination Criteria PAM）算法为基础,给出两个加速引理,并基于中心点之间距离不等式提出两个新加速定理.同时,以O（n+K²）额外内存空间开销辅助引理、定理的结合而提出加速SPAM（Speed Up PAM）聚类算法,使得K-medoids聚类算法复杂度由O（K（n-K）²）降低至O（（n-K）²）.在实际及人工模拟数据集上的实验结果表明,相对PAM、TPAM、FKMEDOIDS（Fast K-medoids）等参考算法均有改进,运行时间比PAM至少提升0.828倍.     

Said-Bézier型广义Ball曲线显式降多阶

给出了计算Said-Bézier型广义Ball曲线(SBGB曲线)在L₂范数下保持端点约束的一种最佳降多阶算法.基于SBGB基函数、幂基函数和Jacobi基函数之间的相互转换关系,得到了SBGB基函数和Jacobi基函数之间的显式转换矩阵;进一步利用Jacobi基的正交性和上述转换矩阵的逆矩阵,导出了SBGB曲线在L₂范数下的显式约束降多阶算法.此算法蕴含了Said-Ball曲线、Bézier曲线以及位置介于这两类曲线之间的一大类参数曲线的相应降多阶算法.证明了这是一种可以预报最佳误差且满足端点高阶约束的一次性降多阶算法.最后用数值实例说明了算法的正确性和优越性.     

On intractability of the classUP

The classUP [V] is the class of sets accepted by polynomial-time nondeterministic Turing machines which have at most one accepting path for every input. The complexity of this class closely relates to that of computing inverses ofone-way functions, where a one-way function is a one-to-one, length-increasing, and polynomial-time computable function whose inverse cannot be computed within polynomial time. It is known [GS], [K] that there exists a one-way function if and only ifP UP. In this paper the intractability of sets inUP is investigated in terms of polynomial-time reducibility to a sparse set. It is shown thatUP has a set that is _m ^P -reducible to no sparse set ifP UP. We interpret this structural property in the relation with approximation algorithms: it is shown that ifP UP, thenUP has a set with no 1-APT approximation and, furthermore,UP has a set that is not _m ^P -reducible to any set with a 1-APT approximation. The implication of this result in the study of one-way functions is also discussed. In order to prove the main theorem, we introduce a variation of tree-pruning methods.This paper was written while the author visited the Department of Mathematics, University of California, Santa Barbara. This research was supported in part by the National Science Foundation under Grant CCR-8611980.     

On characterizing the existence of partial one-way permutations

We study the easy certificate classes introduced by Hemaspaandra, Rothe, and Wechsung, with regard to the question of whether or not surjective one-way functions exist. This is a natural open question in worst-case cryptography. We show that the existence of partial one-way permutations can be characterized by separating P from the class of UP sets that, for all unambiguous polynomial-time Turing machines accepting them, always have easy (i.e., polynomial-time computable) certificates. This characterization expands results of Grollmann and Selman. We also establish characterizations of the existence of (partial and total) surjective poly-to-one one-way functions.     

Limiting negations in non-deterministic circuits

The minimum number of NOT gates in a Boolean circuit computing a Boolean function f is called the inversion complexity of f. In 1958, Markov determined the inversion complexity of every Boolean function and, in particular, proved that log₂(n+1) NOT gates are sufficient to compute any Boolean function on n variables. In this paper, we consider circuits computing non-deterministically and determine the inversion complexity of every Boolean function. In particular, we prove that one NOT gate is sufficient to compute any Boolean function in non-deterministic circuits if we can use an arbitrary number of guess inputs.     

Malign Distributions for Average Case Circuit Complexity

In contrast to machine models like Turing machines or random access machines, circuits are a static computational model. The internal information flow of a computation is fixed in advance, independent of the actual input. Therefore, size and depth are natural and simple measures for circuits and provide a worst-case analysis. We consider a new model in which an internal gate is evaluated as soon as its result has been determined by a partial assignment of its inputs. This way, a dynamic notion of delay is obtained which gives rise to an average case measure for the time complexity of circuits. In a previous paper we have obtained tight upper and lower bounds for the average case complexity of several basic Boolean functions. This paper examines the asymptotic average case complexity for the set of alln-ary Boolean functions. In contrast to worst case analysis a simple counting argument does not work. We prove that with respect to the uniform probability distribution almost all Boolean functions require at leastn−log n−log log nexpected time. On the other hand, there is a significantly large subset of functions that can be computed with a constant average delay. Finally, for an arbitrary Boolean function we compare its worst case and average case complexity. It is shown that for each function that requires circuit depthd, i.e. of worst-case complexityd, the expected time complexity will be at leastd−log n−log dwith respect to an explicitly defined probability distribution. In addition, a nontrivial upper bound on the complexity of such a distribution will be obtained.     

A lower bound on the mod 6 degree of the OR function

We examine the computational power of modular counting, where the modulus m is not a prime power, in the setting of polynomials in Boolean variables over Z _m . In particular, we say that a polynomial P weakly represents a Boolean function f (both have n variables) if for any inputs x and y in {0,1}ⁿ, we have whenever . Barrington et al. (1994) investigated the minimal degree of a polynomial representing the OR function in this way, proving an upper bound of O(n ^{1/ r} ) (where r is the number of distinct primes dividing m) and a lower bound of . Here, we show a lower bound of when m is a product of two primes and in general. While many lower bounds are known for a much stronger form of representation of a function by a polynomial (Barrington et al. 1994, Tsai 1996), very little is known using this liberal (and, we argue, more natural) definition. While the degree is known to be for the generalized inner product because of its high communication complexity (Grolmusz 1995), our bound is the best known for any function of low communication complexity and any modulus not a prime power. received 29 September 1994     

Resolution-based lower bounds in MaxSAT

The lower bound (LB) implemented in branch and bound MaxSAT solvers is decisive for obtaining a competitive solver. In modern solvers like MaxSatz and MiniMaxSat, the LB relies on the cooperation of the underestimation and inference components. Actually, the underestimation component of some solvers guides the application of the inference component when a conflict is reached and certain structures are found. In this paper we analyze algorithmic and logical aspects of the underestimation components that have been implemented in MaxSatz during its evolution. From an algorithmic point of view, we define novel strategies for selecting unit clauses in UP (the underestimation of LB in UP is the number of independent inconsistent subformulas detected using unit propagation), the extension of UP with failed literal detection, and a clever heuristic for guiding the application of MaxSAT resolution when UP augmented with failed literal detection is applied in the presence of cycles structures. From a logical point of view, we prove that the inconsistent subformulas detected by UP are minimally unsatisfiable, but this property does not hold if failed literal detection is added. In the presence of cycle structures in conflicts detected by UP augmented with failed literal detection, we prove that the application of MaxSAT resolution produces smaller inconsistent subformulas and, besides, generates additional clauses that may be used to improve the LB. The conducted empirical investigation indicates that the LB techniques described in this paper lead to better quality LBs.     

On the complexity of nested-object matching

Query languages for object-oriented data models involvematching ofnested-objects or nested-terms. Nested-objects are extended first-order terms: with sets and tuples as the only constructors (no function symbols). This paper studies the complexity of nested-term matching. The main result is the following complete characterization. Letset-nesting index (tuples-nesting index) denote the level of set nesting (tuple nesting) of a nested-term; letS _i,j denote the set of all nested-terms with set-indexi and tuple-indexj. Then,the matching problem for a given class S _i,j is NP-Complete if either i2,or i>0and j>0;otherwise, the complexity of the matching problem for S _i,j is in PTIME. We compare our work with the related work on set-matching, and show that our results yield an alternative proof, using fewer interpreted symbols, for the NP-completeness of the set-matching problem.     

Backdoor Sets for DLL Subsolvers

We study the parameterized complexity of detecting small backdoor sets for instances of the propositional satisfiability problem (SAT). The notion of backdoor sets has been recently introduced by Williams, Gomes, and Selman for explaining the ‘heavy-tailed’ behavior of backtracking algorithms. If a small backdoor set is found, then the instance can be solved efficiently by the propagation and simplification mechanisms of a SAT solver. Empirical studies indicate that structured SAT instances coming from practical applications have small backdoor sets. We study the worst-case complexity of detecting backdoor sets with respect to the simplification and propagation mechanisms of the classic Davis–Logemann–Loveland (DLL) procedure. We show that the detection of backdoor sets of size bounded by a fixed integer k is of high parameterized complexity. In particular, we determine that this detection problem (and some of its variants) is complete for the parameterized complexity class W[P]. We achieve this result by means of a generalization of a reduction due to Abrahamson, Downey, and Fellows.     

Communication complexity towards lower bounds on circuit depth

Karchmer, Raz, and Wigderson (1995) discuss the circuit depth complexity of n-bit Boolean functions constructed by composing up to d = log n/log log n levels of k = log n-bit Boolean functions. Any such function is in AC¹ . They conjecture that circuit depth is additive under composition, which would imply that any (bounded fan-in) circuit for this problem requires depth. This would separate AC¹ from NC¹. They recommend using the communication game characterization of circuit depth. In order to develop techniques for using communication complexity to prove circuit depth lower bounds, they suggest an intermediate communication complexity problem which they call the Universal Composition Relation. We give an almost optimal lower bound of dk—O(d ²(k log k)^1/2) for this problem. In addition, we present a proof, directly in terms of communication complexity, that there is a function on k bits requiring circuit depth. Although this fact can be easily established using a counting argument, we hope that the ideas in our proof will be incorporated more easily into subsequent arguments which use communication complexity to prove circuit depth bounds. Received: July 30, 1999.     

The BNS-Chung criterion for multi-party communication complexity

The "Number on the Forehead" model of multi-party communication complexity was first suggested by Chandra, Furst and Lipton. The best known lower bound, for an explicit function (in this model), is a lower bound of , where n is the size of the input of each player, and k is the number of players (first proved by Babai, Nisan and Szegedy). This lower bound has many applications in complexity theory. Proving a better lower bound, for an explicit function, is a major open problem. Based on the result of BNS, Chung gave a sufficient criterion for a function to have large multi-party communication complexity (up to ). In this paper, we use some of the ideas of BNS and Chung, together with some new ideas, resulting in a new (easier and more modular) proof for the results of BNS and Chung. This gives a simpler way to prove lower bounds for the multi-party communication complexity of a function. Received: December 12, 1997.