Spelling suggestions: "subject:"stabilility dumber"" "subject:"stabilility 1umber""
1 |
Voting in clustering and finding the number of clustersDimitriadou, Evgenia, Weingessel, Andreas, Hornik, Kurt January 1999 (has links) (PDF)
In this paper we present an unsupervised algorithm which performs clustering given a data set and which can also find the number of clusters existing in it. This algorithm consists of two techniques. The first, the voting technique, allows us to combine several runs of clustering algorithms, with the number of clusters predefined, resulting in a common partition. We introduce the idea that there are cases where an input point has a structure with a certain degree of confidence and may belong to more than one cluster with a certain degree of "belongingness". The second part consists of an index measure which receives the results of every voting process for diffrent number of clusters and makes the decision in favor of one. This algorithm is a complete clustering scheme which can be applied to any clustering method and to any type of data set. Moreover, it helps us to overcome instabilities of the clustering algorithms and to improve the ability of a clustering algorithm to find structures in a data set. / Series: Report Series SFB "Adaptive Information Systems and Modelling in Economics and Management Science"
|
2 |
Advanced Characterization of Hydraulic Structures for Flow Regime Control: Experimental DevelopementHamedi, Amirmasoud 26 May 2017 (has links)
A good understanding of flow in a number of hydraulic structures, such as energy dissipators, among others, is needed to effectively control upstream and downstream flow conditions, for instance, high water depth and velocity to ensure, scouring, flow stability and control scouring, which is thus crucial to ensuring safe acceptable operation. Although some previous research exists on minimizing scouring and flow fluctuations after hydraulic structures, none of this research can fully resolve all issues of concern. In this research, three types of structures were studied, as follows: a) a vertical gate; b) a vertical gate with an expansion; and c) a vertical gate with a contraction. A Stability Concept was introduced and defined to characterize the conditions downstream of gated structures. When established criteria for stability are met, erosion is prevented. This research then investigated and evaluated two methods to classify the flow downstream of a gated vii structure to easily determine stability. The two classification methods are: the Flow Stability Factor and the Flow Stability Number. The Flow Stability Factor, which is developed based on the Fuzzy Concept, is defined in the range of 0 to 1; the maximum value is one and indicates that the flow is completely stable; and the minimum value is zero and indicates that the flow is completely unstable. The Flow Stability Number is defined as the ratio of total energy at two channel sections with a maximum value of one, and it allows flow conditions to be classified for various hydraulic structures; the number is dimensionless and quantitatively defines the flow stability downstream of a hydraulic structure under critical and subcritical flow conditions herein studied, also allowing for an estimate of the downstream stable condition for operation of a hydraulic structure. This research also implemented an Artificial Neural Network to determine the optimal gate opening that ensures a downstream stable condition. A post-processing method (regression-based) was also introduced to reduce the differences in the amount of the gate openings between experimental results and artificial intelligence estimates. The results indicate that the differences were reduced approximately 2% when the post-processing method was implemented on the Artificial Neural Network estimates. This method provides reasonable results when few data values are available and the Artificial Neural Network cannot be well trained. Experiments were conducted in two laboratories, for two different scales, to investigate any possible scale effect. Results indicate, for instance, that the case of the vertical gate with an expansion performs better in producing a downstream stable condition than the other two studied structures. Moreover, it was found that smaller changes caused by expansions and contractions on the channel width show better performance in ensuring a viii downstream stable condition in the cases of a vertical gate with an expansion and a vertical gate with a contraction over a wide range of structures. Moreover, upstream flow depths in the gate with expansion are higher than in the cases of a gate and a gate with a contraction, suggesting that it may be more appropriate for agriculture applications. This research also applied Game Theory and the Nash Equilibrium Concept in selecting the best choice among various structures, under different flow expectations. In addition, the accuracy of the Flow Stability Factor and the Flow Stability number were compared. This showed that the Flow Stability Factor and the Flow Stability number had good agreement in stable conditions. Hence, the Flow Stability Factor can then be used instead of the Flow Stability number to define stable conditions, as a visual method that does not need any measurement. Importantly, a Fuzzy-based Efficiency Index, a method based on an image processing technique, was also innovatively tested to estimate the hydraulic efficiency of the hydraulic structures. The method was tested and validated using laboratory data with an average agreement of 96.45%, and then demonstrated for prototype case situations in Florida and California. These cases yielded overall efficiencies of 96% and 97.87% in Spillway Park, FL and Oroville Dam, CA, respectively. Statistical assessment was also done on the image, determining an Efficiency Index. Specifically, an image histogram was extracted from the grayscale image, then the mean and standard deviation of the histogram was used to calculate the Index. The method uses the darkness and whiteness of the image to estimate the Efficiency Index; it is easy to use, quick, low cost, and trustworthy.
|
3 |
Algorithms for the Maximum Independent Set ProblemLê, Ngoc C. 13 July 2015 (has links) (PDF)
This thesis focuses mainly on the Maximum Independent Set (MIS) problem. Some related graph theoretical combinatorial problems are also considered. As these problems are generally NP-hard, we study their complexity in hereditary graph classes, i.e. graph classes defined by a set F of forbidden induced subgraphs.
We revise the literature about the issue, for example complexity results, applications, and techniques tackling the problem. Through considering some general approach, we exhibit several cases where the problem admits a polynomial-time solution. More specifically, we present polynomial-time algorithms for the MIS problem in:
+ some subclasses of $S_{2;j;k}$-free graphs (thus generalizing the classical result for $S_{1;2;k}$-free graphs);
+ some subclasses of $tree_{k}$-free graphs (thus generalizing the classical results for subclasses of P5-free graphs);
+ some subclasses of $P_{7}$-free graphs and $S_{2;2;2}$-free graphs; and various subclasses of graphs of bounded maximum degree, for example subcubic graphs.
Our algorithms are based on various approaches. In particular, we characterize augmenting graphs in a subclass of $S_{2;k;k}$-free graphs and a subclass of $S_{2;2;5}$-free graphs. These characterizations are partly based on extensions of the concept of redundant set [125]. We also propose methods finding augmenting chains, an extension of the method in [99], and finding augmenting trees, an extension of the methods in [125]. We apply the augmenting vertex technique, originally used for $P_{5}$-free graphs or banner-free graphs, for some more general graph classes.
We consider a general graph theoretical combinatorial problem, the so-called Maximum -Set problem. Two special cases of this problem, the so-called Maximum F-(Strongly) Independent Subgraph and Maximum F-Induced Subgraph, where F is a connected graph set, are considered. The complexity of the Maximum F-(Strongly) Independent Subgraph problem is revised and the NP-hardness of the Maximum F-Induced Subgraph problem is proved. We also extend the augmenting approach to apply it for the general Maximum Π -Set problem.
We revise on classical graph transformations and give two unified views based on pseudo-boolean functions and αff-redundant vertex. We also make extensive uses of α-redundant vertices, originally mainly used for $P_{5}$-free graphs, to give polynomial solutions for some subclasses of $S_{2;2;2}$-free graphs and $tree_{k}$-free graphs.
We consider some classical sequential greedy heuristic methods. We also combine classical algorithms with αff-redundant vertices to have new strategies of choosing the next vertex in greedy methods. Some aspects of the algorithms, for example forbidden induced subgraph sets and worst case results, are also considered.
Finally, we restrict our attention on graphs of bounded maximum degree and subcubic graphs. Then by using some techniques, for example ff-redundant vertex, clique separator, and arguments based on distance, we general these results for some subclasses of $S_{i;j;k}$-free subcubic graphs.
|
4 |
Algorithms for the Maximum Independent Set ProblemLê, Ngoc C. 18 February 2015 (has links)
This thesis focuses mainly on the Maximum Independent Set (MIS) problem. Some related graph theoretical combinatorial problems are also considered. As these problems are generally NP-hard, we study their complexity in hereditary graph classes, i.e. graph classes defined by a set F of forbidden induced subgraphs.
We revise the literature about the issue, for example complexity results, applications, and techniques tackling the problem. Through considering some general approach, we exhibit several cases where the problem admits a polynomial-time solution. More specifically, we present polynomial-time algorithms for the MIS problem in:
+ some subclasses of $S_{2;j;k}$-free graphs (thus generalizing the classical result for $S_{1;2;k}$-free graphs);
+ some subclasses of $tree_{k}$-free graphs (thus generalizing the classical results for subclasses of P5-free graphs);
+ some subclasses of $P_{7}$-free graphs and $S_{2;2;2}$-free graphs; and various subclasses of graphs of bounded maximum degree, for example subcubic graphs.
Our algorithms are based on various approaches. In particular, we characterize augmenting graphs in a subclass of $S_{2;k;k}$-free graphs and a subclass of $S_{2;2;5}$-free graphs. These characterizations are partly based on extensions of the concept of redundant set [125]. We also propose methods finding augmenting chains, an extension of the method in [99], and finding augmenting trees, an extension of the methods in [125]. We apply the augmenting vertex technique, originally used for $P_{5}$-free graphs or banner-free graphs, for some more general graph classes.
We consider a general graph theoretical combinatorial problem, the so-called Maximum -Set problem. Two special cases of this problem, the so-called Maximum F-(Strongly) Independent Subgraph and Maximum F-Induced Subgraph, where F is a connected graph set, are considered. The complexity of the Maximum F-(Strongly) Independent Subgraph problem is revised and the NP-hardness of the Maximum F-Induced Subgraph problem is proved. We also extend the augmenting approach to apply it for the general Maximum Π -Set problem.
We revise on classical graph transformations and give two unified views based on pseudo-boolean functions and αff-redundant vertex. We also make extensive uses of α-redundant vertices, originally mainly used for $P_{5}$-free graphs, to give polynomial solutions for some subclasses of $S_{2;2;2}$-free graphs and $tree_{k}$-free graphs.
We consider some classical sequential greedy heuristic methods. We also combine classical algorithms with αff-redundant vertices to have new strategies of choosing the next vertex in greedy methods. Some aspects of the algorithms, for example forbidden induced subgraph sets and worst case results, are also considered.
Finally, we restrict our attention on graphs of bounded maximum degree and subcubic graphs. Then by using some techniques, for example ff-redundant vertex, clique separator, and arguments based on distance, we general these results for some subclasses of $S_{i;j;k}$-free subcubic graphs.
|
Page generated in 0.0466 seconds