Quantum Relief Algorithm
Quantum Relief Algorithm
复制标题
量子救济算法
DOI：
10.1007/s11128-018-2048-x
复制
发表时间：
2018
影响因子：
2.5
通讯作者：
Ching-Nung Yang
中科院分区：
文献类型：
--
作者：
Wenjie Liu;Peipei Gao;Wenbin Yu;Zhiguo Qu;Ching-Nung Yang
Relief算法是Kira和Rendell提出的一种用于二值分类的特征选择算法，其计算复杂度随着样本规模和特征数量的增加而显著增加。为了降低复杂度，提出了一种基于Relief算法的量子特征选择算法，也称为量子Relief算法。该算法通过CMP和旋转操作将每个样本的所有特征叠加到某个量子态上，然后对该量子态进行交换测试和测量，得到两个样本之间的相似性。然后通过计算最大相似度得到Near-hit和Near-miss，并进一步应用于更新特征权向量WT，得到与阈值相关的特征。为了验证算法的有效性，利用一个简单的算例进行了基于IBM Q的仿真实验。效率分析表明，该算法的计算复杂度为O（M），而原Relief算法的计算复杂度为O（NM），其中N为每个样本的特征数，M为样本集的大小。显然，我们的量子Relief算法具有优于经典算法上级加速性能。
Relief algorithm is a feature selection algorithm used in binary classification proposed by Kira and Rendell, and its computational complexity remarkably 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 CMP and rotation operations, then the swap test and measurement are applied on this state to get the similarity between two samples. After that,Near-hitandNear-missare obtained by calculating the maximal similarity, and further applied to update the feature weight vector WT to getthat determine the relevant features with the threshold. 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 isO(M), while the complexity of the original Relief algorithm isO(NM), whereNis the number of features for each sample, andMis the size of the sample set. Obviously, our quantum Relief algorithm has superior acceleration than the classical one.