Piecewise linear classifiers based on nonsmooth optimization approaches
- Authors: Bagirov, Adil , Kasimbeyli, Refail , Ozturk, Gurkan , Ugon, Julien
- Date: 2014
- Type: Text , Book chapter
- Relation: Optimization in Science and Engineering p. 1-32
- Full Text: false
- Reviewed:
- Description: Nonsmooth optimization provides efficient algorithms for solving many machine learning problems. In particular, nonsmooth optimization approaches to supervised data classification problems lead to the design of very efficient algorithms for their solution. In this chapter, we demonstrate how nonsmooth optimization algorithms can be applied to design efficient piecewise linear classifiers for supervised data classification problems. Such classifiers are developed using a max–min and a polyhedral conic separabilities as well as an incremental approach. We report results of numerical experiments and compare the piecewise linear classifiers with a number of other mainstream classifiers.
Global optimality conditions and optimization methods for constrained polynomial programming problems
- Authors: Wu, Zhiyou , Tian, Jing , Ugon, Julien , Zhang, Liang
- Date: 2015
- Type: Text , Journal article
- Relation: Applied Mathematics and Computation Vol. 262, no. (2015), p. 312-325
- Full Text:
- Reviewed:
- Description: The general constrained polynomial programming problem (GPP) is considered in this paper. Problem (GPP) has a broad range of applications and is proved to be NP-hard. Necessary global optimality conditions for problem (GPP) are established. Then, a new local optimization method for this problem is proposed by exploiting these necessary global optimality conditions. A global optimization method is proposed for this problem by combining this local optimization method together with an auxiliary function. Some numerical examples are also given to illustrate that these approaches are very efficient. (C) 2015 Elsevier Inc. All rights reserved.
Optimality conditions and optimization methods for quartic polynomial optimization
- Authors: Wu, Zhiyou , Tian, Jing , Quan, Jing , Ugon, Julien
- Date: 2014
- Type: Text , Journal article
- Relation: Applied Mathematics and Computation Vol. 232, no. (2014), p. 968-982
- Full Text: false
- Reviewed:
- Description: In this paper multivariate quartic polynomial optimization program (QPOP) is considered. Quartic optimization problems arise in various practical applications and are proved to be NP hard. We discuss necessary global optimality conditions for quartic problem (QPOP). And then we present a new (strongly or ε-strongly) local optimization method according to necessary global optimality conditions, which may escape and improve some KKT points. Finally we design a global optimization method for problem (QPOP) by combining the new (strongly or ε-strongly) local optimization method and an auxiliary function. Numerical examples show that our algorithms are efficient and stable.
Chebyshev approximation by linear combinations of fixed knot polynomial splines with weighting functions
- Authors: Sukhorukova, Nadezda , Ugon, Julien
- Date: 2016
- Type: Text , Journal article
- Relation: Journal of Optimization Theory and Applications Vol. 171, no. 2 (2016), p. 536-549
- Full Text: false
- Reviewed:
- Description: In this paper, we derive conditions for best uniform approximation by fixed knots polynomial splines with weighting functions. The theory of Chebyshev approximation for fixed knots polynomial functions is very elegant and complete. Necessary and sufficient optimality conditions have been developed leading to efficient algorithms for constructing optimal spline approximations. The optimality conditions are based on the notion of alternance (maximal deviation points with alternating deviation signs). In this paper, we extend these results to the case when the model function is a product of fixed knots polynomial splines (whose parameters are subject to optimization) and other functions (whose parameters are predefined). This problem is nonsmooth, and therefore, we make use of convex and nonsmooth analysis to solve it.
Analysis and comparison of co-occurrence matrix and pixel n-gram features for mammographic images
- Authors: Kulkarni, Pradnya , Stranieri, Andrew , Kulkarni, Sid , Ugon, Julien , Mittal, Manish
- Date: 2015
- Type: Text , Conference paper
- Relation: International Conference on Communication and Computing p. 7-14
- Full Text: false
- Reviewed:
- Description: Mammography is a proven way of detecting breast cancer at an early stage. Various feature extraction techniques such as histograms, co-occurrence matrix, local binary patterns, Gabor filters, wavelet transforms are used for analysing mammograms. The novel pixel N-gram feature extraction technique has been inspired from the character N-gram concept of text retrieval. In this paper, we have compared the novel N-gram feature extraction technique with the co-occurrence matrix feature extraction technique. The experiments were conducted on the benchmark miniMIAS mammography database. Classification of mammograms into normal and abnormal category using N-gram features showed promising results with greater classification accuracy, sensitivity and specificity compared to classification using co-occurrence matrix features. Moreover, N-gram features computation are found to be considerably faster than co-occurrence matrix feature computation
Nonsmooth DC programming approach to clusterwise linear regression : Optimality conditions and algorithms
- Authors: Bagirov, Adil , Ugon, Julien
- Date: 2018
- Type: Text , Journal article
- Relation: Optimization Methods and Software Vol. 33, no. 1 (2018), p. 194-219
- Relation: http://purl.org/au-research/grants/arc/DP140103213
- Full Text: false
- Reviewed:
- Description: The clusterwise linear regression problem is formulated as a nonsmooth nonconvex optimization problem using the squared regression error function. The objective function in this problem is represented as a difference of convex functions. Optimality conditions are derived, and an algorithm is designed based on such a representation. An incremental approach is proposed to generate starting solutions. The algorithm is tested on small to large data sets. © 2017 Informa UK Limited, trading as Taylor & Francis Group.
Nonsmooth optimization algorithm for solving clusterwise linear regression problems
- Authors: Bagirov, Adil , Ugon, Julien , Mirzayeva, Hijran
- Date: 2015
- Type: Text , Journal article
- Relation: Journal of Optimization Theory and Applications Vol. 164, no. 3 (2015), p. 755-780
- Relation: http://purl.org/au-research/grants/arc/DP140103213
- Full Text: false
- Reviewed:
- Description: Clusterwise linear regression consists of finding a number of linear regression functions each approximating a subset of the data. In this paper, the clusterwise linear regression problem is formulated as a nonsmooth nonconvex optimization problem and an algorithm based on an incremental approach and on the discrete gradient method of nonsmooth optimization is designed to solve it. This algorithm incrementally divides the whole dataset into groups which can be easily approximated by one linear regression function. A special procedure is introduced to generate good starting points for solving global optimization problems at each iteration of the incremental algorithm. The algorithm is compared with the multi-start Spath and the incremental algorithms on several publicly available datasets for regression analysis.
Finite alternation theorems and a constructive approach to piecewise polynomial approximation in chebyshev norm
- Authors: Crouzeix, Jean-Pierre , Sukhorukova, Nadezda , Ugon, Julien
- Date: 2020
- Type: Text , Journal article
- Relation: Set-Valued and Variational Analysis Vol. 28, no. 1 (2020), p. 123-147. http://purl.org/au-research/grants/arc/DP180100602
- Full Text: false
- Reviewed:
- Description: One of the purposes in this paper is to provide a better understanding of the alternance property which occurs in Chebyshev polynomial approximation and continuous piecewise polynomial approximation problems. In the first part of this paper, we prove that alternating sequences of any continuous function are finite in any given segment and then propose an original approach to obtain new proofs of the well known necessary and sufficient optimality conditions. There are two main advantages of this approach. First of all, the proofs are intuitive and easy to understand. Second, these proofs are constructive and therefore they lead to new alternation-based algorithms. In the second part of this paper, we develop new local optimality conditions for free knot polynomial spline approximation. The proofs for free knot approximation are relying on the techniques developed in the first part of this paper. The piecewise polynomials are required to be continuous on the approximation segment. © 2020, Springer Nature B.V.
Visual character N-grams for classification and retrieval of radiological images
- Authors: Kulkarni, Pradnya , Stranieri, Andrew , Kulkarni, Siddhivinayak , Ugon, Julien , Mittal, Manish
- Date: 2014
- Type: Text , Journal article
- Relation: International Journal of Multimedia & Its Applications Vol. 6, no. 2 (April 2014), p. 35-49
- Full Text:
- Reviewed:
- Description: Diagnostic radiology struggles to maintain high interpretation accuracy. Retrieval of past similar cases would help the inexperienced radiologist in the interpretation process. Character n-gram model has been effective in text retrieval context in languages such as Chinese where there are no clear word boundaries. We propose the use of visual character n-gram model for representation of image for classification and retrieval purposes. Regions of interests in mammographic images are represented with the character n-gram features. These features are then used as input to back-propagation neural network for classification of regions into normal and abnormal categories. Experiments on miniMIAS database show that character n-gram features are useful in classifying the regions into normal and abnormal categories. Promising classification accuracies are observed (83.33%) for fatty background tissue warranting further investigation. We argue that Classifying regions of interests would reduce the number of comparisons necessary for finding similar images from the database and hence would reduce the time required for retrieval of past similar cases.
A new modified global k-means algorithm for clustering large data sets
- Authors: Bagirov, Adil , Ugon, Julien , Webb, Dean
- Date: 2009
- Type: Text , Conference paper
- Relation: Paper presented at XIIIth International Conference : Applied Stochastic Models and Data Analysis, ASMDA 2009, Vilnius, Lithuania : 30th June - 3rd July 2009 p. 1-5
- Full Text: false
- Description: The k-means algorithm and its variations are known to be fast clustering algorithms. However, they are sensitive to the choice of starting points and inefficient for solving clustering problems in large data sets. Recently, in order to resolve difficulties with the choice of starting points, incremental approaches have been developed. The modified global k-means algorithm is based on such an approach. It iteratively adds one cluster center at a time. Numerical experiments show that this algorithm considerably improve the k-means algorithm. However, this algorithm is not suitable for clustering very large data sets. In this paper, a new version of the modified global k-means algorithm is proposed. We introduce an auxiliary cluster function to generate a set of starting points spanning different parts of the data set. We exploit information gathered in previous iterations of the incremental algorithm to reduce its complexity.
- Description: 2003007558
An incremental approach for the construction of a piecewise linear classifier
- Authors: Bagirov, Adil , Ugon, Julien , Webb, Dean
- Date: 2009
- Type: Text , Conference paper
- Relation: Paper presented at XIIIth International Conference : Applied Stochastic Models and Data Analysis, ASMDA 2009, Vilnius, Lithuania : 30th June - 3rd July 2009 p. 507–511
- Relation: https://purl.org/au-research/grants/arc/DP0666061
- Full Text: false
- Description: In this paper the problem of finding piecewise linear boundaries between sets is considered and is applied for solving supervised data classification problems. An algorithm for the computation of piecewise linear boundaries, consisting of two main steps, is proposed. In the first step sets are approximated by hyperboxes to find so-called “indeterminate” regions between sets. In the second step sets are separated inside these “indeterminate” regions by piecewise linear functions. These functions are computed incrementally starting with a linear function. Results of numerical experiments are reported. These results demonstrate that the new algorithm requires a reasonable training time and it produces consistently good test set accuracy on most data sets comparing with mainstream classifiers.
- Description: 2003007559
Almost simplicial polytopes : the lower and upper bound theorems
- Authors: Nevo, Eran , Pineda-Villavicencio, Guillermo , Ugon, Julien , Yost, David
- Date: 2020
- Type: Text , Journal article
- Relation: Canadian Journal of Mathematics Vol. 72, no. 2 (2020), p. 537-556. http://purl.org/au-research/grants/arc/DP180100602
- Full Text:
- Reviewed:
- Description: We study -vertex -dimensional polytopes with at most one nonsimplex facet with, say, vertices, called almost simplicial polytopes. We provide tight lower and upper bound theorems for these polytopes as functions of, and, thus generalizing the classical Lower Bound Theorem by Barnette and the Upper Bound Theorem by McMullen, which treat the case where s = 0. We characterize the minimizers and provide examples of maximizers for any. Our construction of maximizers is a generalization of cyclic polytopes, based on a suitable variation of the moment curve, and is of independent interest. © 2018 Canadian Mathematical Society.
Connectivity of cubical polytopes
- Authors: Bui, Hoa , Pineda-Villavicencio, Guillermo , Ugon, Julien
- Date: 2019
- Type: Text , Journal article
- Relation: Journal of Combinatorial Theory Series A Vol. 169, no. (Jan 2019), p. 21
- Full Text:
- Reviewed:
- Description: A cubical polytope is a polytope with all its facets being combinatorially equivalent to cubes. We deal with the connectivity of the graphs of cubical polytopes. We first establish that, for any d >= 3, the graph of a cubical d-polytope with minimum degree 5 is min{delta, 2d - 2}-connected. Second, we show, for any d >= 4, that every minimum separator of cardinality at most 2d - 3 in such a graph consists of all the neighbours of some vertex and that removing the vertices of the separator from the graph leaves exactly two components, with one of them being the vertex itself. (C) 2019 Elsevier Inc. All rights reserved.
Pixel N-grams for mammographic lesion classification
- Authors: Kulkarni, Pradnya , Stranieri, Andrew , Ugon, Julien , Mittal, Manish , Kulkarni, Siddhivinayak
- Date: 2017
- Type: Text , Conference proceedings
- Relation: 2017 2nd International Conference on Communication Systems, Computing and IT Applications, CSCITA , Mumbai; 7th-8th April, 2017; published in CSCITA 2017 - Proceedings p. 107-111
- Full Text: false
- Reviewed:
- Description: Automated classification algorithms have been applied to breast cancer diagnosis in order to improve the diagnostic accuracy and turnover time. However, classification accuracy, sensitivity and specificity could still be improved further. Moreover, reducing computational cost is another challenge as the number of images to be analyzed is typically large. In this paper, a novel Pixel N-gram approach inspired from character N-grams in the text retrieval context has been applied for mammographic lesion classification. The experiments on real world database demonstrate that the Pixel N-grams outperform the existing histogram as well as Haralick features with respect to classification accuracy as well as sensitivity. Effect of varying N and using various classifiers is also analyzed in this paper. Results show that optimum value of N is equal to 3 and MLP classifier performs better than SVM and KNN classifier using 3-gram features.
Texture image classification using pixel N-grams
- Authors: Kulkarni, Pradnya , Stranieri, Andrew , Ugon, Julien
- Date: 2016
- Type: Text , Conference proceedings
- Relation: 2016 IEEE International Conference on Signal and Image Processing (ICSIP); Beijing, China; 13-15 Aug, 2016 p. 137-141
- Full Text: false
- Reviewed:
- Description: Various statistical methods such as co-occurrence matrix, local binary patterns and spectral approaches such as Gabor filters have been used for generating global features for image classification. However, global image features fail to distinguish between local variations within an image. Bag-of-visual-words (BoVW) model do capture local variations in an image, but typically do not consider spatial relationships between the visual words. Here, a novel image representation ‘Pixel N-grams’, inspired from the character N-gram concept in text retrieval has been applied for texture classification purpose. Texture is an important property for image classification. Experiments on the benchmark texture database (UIUC) demonstrates that the overall classification accuracy resulting from Pixel N-gram approach (89.5%) is comparable with that achieved using BoVW approach (84.4%) with the added advantage of simplicity and reduced computational cost.
An Agile group aware process beyond CRISP-DM: A hospital data mining case study
- Authors: Sharma, Vishakha , Stranieri, Andrew , Ugon, Julien , Martin, Laura
- Date: 2017
- Type: Text , Conference proceedings
- Relation: ICCDA '17: Proceedings of the International Conference on Computer and Data Analysis May 2017 p. 109-113
- Full Text: false
- Reviewed:
- Description: The CRISP-DM methodology is commonly used in data analytics exercises within an organisation to provide system and structure to data mining processes. However, in providing a rigorous framework, CRISP-DM overlooks two facets of data analytics in organisational contexts; data mining exercises are far more agile and subject to change than presumed in CRISP-DM and central decisions regarding the interpretation of patterns discovered and the direction of analytics exercises are typically not made by individuals but by committees or groups within an organisation. The current study provides a case study of data mining in a hospital setting and suggests how the agile nature of an analytics exercise and the group reasoning inherent in key decisions can be accommodated within a CRISP-DM methodology.
The linkedness of cubical polytopes: the cube
- Authors: Bui, Hoa , Pineda-Villavicencio, Guillermo , Ugon, Julien
- Date: 2021
- Type: Text , Journal article
- Relation: Electronic Journal of Combinatorics Vol. 28, no. 3 (2021), p.
- Relation: http://purl.org/au-research/grants/arc/DP180100602
- Full Text:
- Reviewed:
- Description: The paper is concerned with the linkedness of the graphs of cubical polytopes. A graph with at least 2k vertices is k-linked if, for every set of k disjoint pairs of vertices, there are k vertex-disjoint paths joining the vertices in the pairs. We say that a polytope is k-linked if its graph is k-linked. We establish that the d-dimensional cube is [(d + 1)/2]-linked, for every d ≠ 3; this is the maximum possible linkedness of a d-polytope. This result implies that, for every d ≥ 1, a cubical d-polytope is [d/2]-linked, which answers a question of Wotzlaw (Incidence graphs and unneighborly polytopes, Ph.D. thesis, 2009). Finally, we introduce the notion of strong linkedness, which is slightly stronger than that of linkedness. A graph G is strongly k-linked if it has at least 2k + 1 vertices and, for every vertex v of G, the subgraph G − v is k-linked. We show that cubical 4-polytopes are strongly 2-linked and that, for each d ≥ 1, d-dimensional cubes are strongly
Chebyshev multivariate polynomial approximation and point reduction procedure
- Authors: Sukhorukova, Nadezda , Ugon, Julien , Yost, David
- Date: 2021
- Type: Text , Journal article
- Relation: Constructive Approximation Vol. 53, no. 3 (2021), p. 529-544
- Relation: http://purl.org/au-research/grants/arc/DP180100602
- Full Text:
- Reviewed:
- Description: We apply the methods of nonsmooth and convex analysis to extend the study of Chebyshev (uniform) approximation for univariate polynomial functions to the case of general multivariate functions (not just polynomials). First of all, we give new necessary and sufficient optimality conditions for multivariate approximation, and a geometrical interpretation of them which reduces to the classical alternating sequence condition in the univariate case. Then, we present a procedure for verification of necessary and sufficient optimality conditions that is based on our generalization of the notion of alternating sequence to the case of multivariate polynomials. Finally, we develop an algorithm for fast verification of necessary optimality conditions in the multivariate polynomial case. © 2019, Springer Science+Business Media, LLC, part of Springer Nature.
Chebyshev multivariate polynomial approximation : alternance interpretation
- Authors: Sukhorukova, Nadezda , Ugon, Julien , Yost, David
- Date: 2018
- Type: Text , Book chapter
- Relation: 2016 Matrix Annals p. 177-182
- Full Text:
- Reviewed:
- Description: In this paper, we derive optimality conditions for Chebyshev approximation of multivariate functions. The theory of Chebyshev (uniform) approximation for univariate functions was developed in the late nineteenth and twentieth century. The optimality conditions are based on the notion of alternance (maximal deviation points with alternating deviation signs). It is not clear, however, how to extend the notion of alternance to the case of multivariate functions. There have been several attempts to extend the theory of Chebyshev approximation to the case of multivariate functions. We propose an alternative approach, which is based on the notion of convexity and nonsmooth analysis.
Schur functions for approximation problems
- Authors: Sukhorukova, Nadezda , Ugon, Julien , Yost, David
- Date: 2020
- Type: Text , Book chapter
- Relation: 2018 Matrix Annals p. 331-337
- Full Text: false
- Reviewed:
- Description: In this paper we propose a new approach to least squares approximation problems. This approach is based on partitioning and Schur function. The nature of this approach is combinatorial, while most existing approaches are based on algebra and algebraic geometry. This problem has several practical applications. One of them is curve clustering. We use this application to illustrate the results.