Quantum Relief Algorithm

Abstract

Relief algorithm is a feature selection algorithm used in binary classification proposed by Kira and Rendell, and its computational complexity remarkable increases with both the scale of samples and the number of features. In order to reduce the complexity, a quantum feature selection algorithm based on Relief algorithm, also called quantum Relief algorithm, is proposed. In the algorithm, all features of each sample are superposed by a certain quantum state through the \emph{CMP} and \emph{rotation} operations, then the \emph{swap test} and measurement are applied on this state to get the similarity between two samples. After that, \emph{Near-hit} and \emph{Near-miss} are obtained by calculating the maximal similarity, and further applied to update the feature weight vector $WT$ to get $W{T}^{\prime }$ that determine the relevant features with the threshold $\tau$. In order to verify our algorithm, a simulation experiment based on IBM Q with a simple example is performed. Efficiency analysis shows the computational complexity of our proposed algorithm is \emph{O(M)}, while the complexity of the original Relief algorithm is \emph{O(NM)}, where $N$ is the number of features for each sample, and $M$ is the size of the sample set. Obviously, our quantum Relief algorithm has superior acceleration than the classical one.

15 pges, 6 gigures

Cited by in corpus (8)

• A Unitary Weights Based One-Iteration Quantum Perceptron Algorithm for Non-Ideal Training Sets
• A Novel Quantum Visual Secret Sharing Scheme
• Quantum forgery attacks on COPA,AES-COPA and marble authenticated encryption algorithms
• Quantum Searchable Encryption for Cloud Data Based on Full-Blind Quantum Computation
• Quantum-Based Feature Selection for Multi-classification Problem in Complex Systems with Edge Computing
• A Quantum-based Database Query Scheme for Privacy Preservation in Cloud Environment
• Quantum Privacy-Preserving Price E-Negotiation
• A Unitary Operator Construction Solution Based on Pauli Group for Maximal Dense Coding