CN103648106B - WiFi indoor positioning method of semi-supervised manifold learning based on category matching - Google Patents

Abstract

The invention discloses a WiFi indoor positioning method of semi-supervised manifold learning based on category matching, and relates to an indoor positioning method. The WiFi indoor positioning method disclosed by the invention is used for solving the problems that a Radio Map database is large and the like in an existing WiFi indoor positioning method. The WiFi indoor positioning method comprises the following steps: 1. collecting Radio Map; 2. carrying out intrinsic dimension analysis on the Radio Map; 3. carrying out clustering analysis on the Radio Map; 4. carrying out dimensionality reduction on the Radio Map; 5. adding RSS in the Radio Map to obtain Radio Mapul; and 6. carrying out dimensionality reduction on the Radio Mapul to obtain a characteristic transformation matrix V, and forming an online positioning database through the Radio Map * and V. The WiFi indoor positioning method also comprises the following steps: 1. online testing RSS; 2. carrying out dimensionality reduction on the RSS to obtain RSS *; 3. outputting a positioning result; and 4. updating the database. The WiFi indoor positioning method disclosed by the invention is applied to the field of network technology.

Description

A WiFi Indoor Localization Method Based on Semi-supervised Manifold Learning of Category Matching

technical field

The invention relates to an indoor positioning method, in particular to a WiFi indoor positioning method based on category matching semi-supervised manifold learning.

Background technique

With the rapid development of wireless local area networks in the world and the widespread popularization of mobile terminal equipment, many technologies and applications related to indoor positioning have emerged in recent years. Due to the multipath effect, signal attenuation and the complexity of the indoor positioning environment, it is difficult for the indoor positioning method based on the traditional signal propagation model to meet the high-precision indoor positioning requirements. Although positioning methods based on Time of Arrival (Time of Arrival), Time Difference of Arrival (Time Difference of Arrival) and Angles of Arrival (Angles of Arrival) can basically meet the positioning accuracy requirements, they all require the positioning terminal to have additional hardware equipment support, which has a large Due to the limitations, the indoor positioning system based on the above-mentioned types of positioning methods has not been popularized.

At present, the WiFi indoor positioning method based on the WLAN location fingerprint (Finger Print) has been widely used. The network construction method of this method is low in cost, and it uses the 2.4GHz ISM (Industrial Science Medicine) public frequency band and does not need to add special hardware for positioning measurement on the existing facilities. It only needs to measure the received signal strength (Received SignalStrength, RSS) of the access point (Access Point, AP) through the wireless network card of the mobile terminal and the corresponding software, so as to construct the network signal coverage map (Radio Map), and then pass the matching Algorithms to predict the coordinates, or relative location, of where the mobile user is.

However, the Radio Map established by this method contains huge data information, and as the positioning area expands, the Radio Map may (according to the positioning matching method and algorithm selection) grow exponentially. Obtaining as much relevant data feature information as possible will improve the positioning accuracy for the entire system, but processing a large amount of feature information increases the algorithm overhead, and the positioning algorithm cannot run effectively on mobile terminals with limited processing capabilities. At the same time, some feature information may be It has no effect on positioning or even has a negative effect, resulting in a reduction in matching efficiency, which leads to more complex implementation of matching positioning algorithms and a decrease in positioning accuracy.

When the number of APs increases and the reference point (Reference Point) for positioning increases, the data information of the Radio Map increases. At this time, the information on the number of APs represented in the Radio Map indicates the dimensionality of the data. Therefore, when the number of APs increases, the Radio Map becomes high-dimensional data. To reduce the burden of dealing with high-dimensional data, dimensionality reduction algorithm is one of the effective solutions. High-dimensional data may contain many features, all of which describe the same thing, and these features are closely connected to a certain extent. For example, when taking pictures of the same object from various angles at the same time, the obtained data contains overlapping information. If some simplified non-overlapping expressions of these data can be obtained, the efficiency of data processing operation will be greatly improved and the accuracy will be improved to a certain extent. The purpose of dimensionality reduction algorithm is to improve the processing efficiency of high-dimensional data.

In addition to simplifying data for efficient processing, dimensionality reduction methods also enable data visualization. Due to the poor accuracy of many statistical and machine learning algorithms for the optimal solution, the visualization application of dimensionality reduction can enable users to actually see the spatial structure of high-dimensional data and the ability of algorithm output, which has strong application value.

There are currently many dimensionality reduction algorithms for different purposes, including linear and nonlinear dimensionality reduction algorithms. Among them, PCA (Principal Component Analysis) and LDA (Linear Discriminant Analysis) are typical linear dimensionality reduction algorithms. This type of algorithm has good processing results for high-dimensional data with a linear structure, but has no good results for high-dimensional data with a nonlinear structure. A typical nonlinear dimensionality reduction algorithm is the Manifold Learning algorithm. In 2000, Science magazine published 3 articles about manifold learning algorithms in the same issue, and proposed 2 classic manifold learning algorithms: LLE (Local Linear Embedding) and ISOMAP (Isometric Mapping). As a result, various manifold learning algorithms based on different criteria have been proposed and some of them are applied to image processing. The LDE (Local Discriminant Embedding) algorithm was proposed later in the manifold learning algorithm. It is a typical manifold learning algorithm based on feature extraction, not just based on the visualization target.

The above-mentioned dimensionality reduction algorithm cannot improve the accuracy of dimensionality reduction for the RSS data obtained online or the newly added RSS. Due to changes in the indoor positioning environment, the correlation between RSS data will decrease at different moments, especially after a long time. Among the existing algorithms, there is a class of algorithms that can add RSS data at different times to the corresponding existing data at the same time, thereby enhancing the correlation between different data and improving the accuracy of dimensionality reduction. This type of algorithm is usually called semi-supervised algorithm. According to the characteristics of semi-supervised algorithm, a semi-supervised discriminant embedding (Semi-supervised Discriminant Embedding, SDE) algorithm is proposed.

According to the characteristics of the SDE algorithm, the newly obtained online RSS is added to the existing RadioMap by category matching, and then the local discriminative embedding is carried out to reduce the dimensionality, thus a Classification Matching Based Semi-supervised Discriminant Embedding Algorithm (Classification Matching Based Semi-supervised Discriminant Discriminant) is proposed. Embedding, CM-SDE). The CM-SDE algorithm is used to reduce the dimension of the Radio Map, and the dimension-reduced Radio Map is obtained. The indoor positioning of the reduced-dimensional Radio Map is used to propose a WiFi indoor positioning algorithm based on the CM-SDE algorithm.

Contents of the invention

The present invention is to solve the problem of the large Radio Map database existing in the existing WiFi indoor positioning method, and the difficulty in applying the online phase to obtain RSS data due to the high computational complexity of the online positioning phase, the difficulty in realizing it in the mobile terminal, and the difficulty in ensuring real-time positioning. In order to meet the performance requirements and other issues, a WiFi indoor localization method based on category matching semi-supervised manifold learning is provided.

The WiFi indoor positioning method based on category matching semi-supervised manifold learning offline stage positioning process is implemented in the following steps:

1. Arrange APs in the indoor area to be positioned, so that the wireless signal covers the indoor area to be positioned, and complete the construction of the WiFi network;

Select and record the corresponding coordinates of the reference point in the indoor area to be positioned, measure and record the RSS signals of all APs received by the reference point in turn as location feature information, construct a Radio Map, and store the Radio Map;

2. Use the GMST eigendimension estimation algorithm to analyze the eigendimension of the Radio Map constructed in step 1. The obtained eigendimension is used as one of the input parameters of the CM-SDE algorithm to determine the dimensionality of the Radio Map after dimension reduction. dimension;

3. Use the KFCM algorithm to perform clustering analysis on the Radio Map, realize the category mark of the established Radio Map, and use it as one of the input parameters of CM-SDE, and provide the corresponding initial cluster center and category mark;

4. The intrinsic dimension in step 2 and the category mark in step 3 are used as input parameters, and the CM-SDE algorithm is used to reduce the dimension of the Radio Map constructed in step 1, and the corresponding dimension-reduced RadioMap ^* , RadioMap ^* is obtained Used as a matching location database for the online location stage;

5. Add the unmarked RSS obtained from the online positioning stage test of different users to the existing Radio Map by category matching, and obtain the corresponding RadioMap _ul that contains the unmarked signal coverage map. The cluster center updated by category matching is used as the CM - New category input parameter in SDE algorithm;

6. The updated clustering center in step 5 is used as an input parameter, and the feature transformation matrix V′ is obtained by using CM-SDE to reduce the dimensionality of RadioMap _ul , and V′ and RadioMap ^* together constitute an online matching and positioning database for online stage positioning; , the specific line stage positioning is:

Six (1), online test RSS;

Six (2), use V to reduce the RSS dimension to RSS ^* ;

Six (3), using the KNN algorithm for matching and positioning to output positioning results;

Six (four), user positioning terminal positioning database update;

That is, the offline stage implementation of a WiFi indoor positioning method based on category matching semi-supervised manifold learning is completed.

The WiFi indoor positioning method based on semi-supervised manifold learning of category matching is realized in the online stage positioning process through the following steps:

1. Test RSS online;

2. The RSS of the point to be located is obtained by using the feature transformation matrix dimensionality reduction transformation to obtain RSS*;

3. Use the KNN algorithm to match RSS* and Radio Map*, predict the specific location coordinates of the positioning point and update the online data. The implementation process is as follows:

(1) In the online stage, the RSS=[AP ₁ ,AP ₂ ,…,AP _n ] received at the test point is multiplied by the feature transformation matrix V′, so as to obtain the reduced RSS′=[AP ₁ ,AP ₂ ,...AP _d ], where d represents the intrinsic dimension;

(2) Use the KNN algorithm to realize the matching between RSS′ and Radio Map*, and use the average value of the coordinates of the K reference points closest to RSS′ as the test point (x′, y′), whose expression is:

In the formula, (x′, y′) is the predicted coordinate of the test point, ( _xi , y _i ) is the coordinate of the i-th neighbor point, and K is the number of neighbors in the KNN algorithm;

4. The user positioning terminal positioning database is updated, that is, the indoor positioning method in the WiFi online stage is completed based on category matching semi-supervised manifold learning.

Invention effect:

In view of the CM-SDE algorithm and background requirements proposed by the present invention, the positioning is carried out through the indoor positioning area formed by the corridor on the 12th floor of Building 2A, Science Park of Harbin Institute of Technology. Using Lenovo V450 laptop and NetStumbler software to test the RSS at all reference points to form a Radio Map, and use the CM-SDE algorithm to reduce the dimension of the Radio Map and use the KNN algorithm to achieve indoor positioning. In the simulation of FIG. 4 , the dimensionality of the reduced Radio Map is one third of that of the original Radio Map. From the simulation results in Figure 4, the positioning performance of the CM-SDE algorithm is comparable to that of the initial KNN algorithm, but the positioning complexity of CM-SDE is only one-third, and the CM-SDE algorithm can effectively Apply the new RSS obtained in real time to the density of the Radio Map, thereby effectively improving the positioning accuracy.

Description of drawings

Fig. 1 is the implementation flowchart of off-line database positioning in the present invention; The solid line arrow represents the data transmission between the steps;

Fig. 2 is the implementation flowchart of online database location in the present invention; The solid line arrow represents the data transmission between the steps;

Figure 3 is a schematic diagram of the construction and experimental environment of a WiFi-based indoor positioning network;

Fig. 4 is a sampling grid diagram;

Figure 5 is a comparison chart of positioning performance using CM-SDE and KNN algorithms; among them, Indicates CM-SDE, stands for KNN.

detailed description

Specific implementation mode one: The offline stage positioning process of the WiFi indoor positioning method based on category matching semi-supervised manifold learning in this embodiment is implemented in the following steps:

1. Arrange APs in the indoor area to be positioned, so that the wireless signal covers the indoor area to be positioned, and complete the construction of the WiFi network;

Select and record the corresponding coordinates of the reference point in the indoor area to be positioned, measure and record the RSS signals of all APs received by the reference point in turn as location feature information, construct a Radio Map, and store the Radio Map;

2. Use the GMST eigendimension estimation algorithm to analyze the eigendimension of the Radio Map constructed in step 1. The obtained eigendimension is used as one of the input parameters of the CM-SDE algorithm to determine the dimensionality of the Radio Map after dimension reduction. dimension;

3. Use the KFCM algorithm to perform clustering analysis on the Radio Map, realize the category mark of the established Radio Map, and use it as one of the input parameters of CM-SDE, and provide the corresponding initial cluster center and category mark;

4. The intrinsic dimension in step 2 and the category mark in step 3 are used as input parameters, and the CM-SDE algorithm is used to reduce the dimension of the Radio Map constructed in step 1, and the corresponding dimension-reduced RadioMap ^* , RadioMap ^* is obtained Used as a matching location database for the online location stage;

5. Add the unmarked RSS obtained from the online positioning stage test of different users to the existing Radio Map by category matching, and obtain the corresponding RadioMap _ul that contains the unmarked signal coverage map. The cluster center updated by category matching is used as the CM - New category input parameter in SDE algorithm;

6. The updated clustering center in step 5 is used as an input parameter, and the feature transformation matrix V′ is obtained by using CM-SDE to reduce the dimensionality of RadioMap _ul , and V′ and RadioMap ^* together constitute an online matching and positioning database for online stage positioning; , the specific line stage positioning is:

Six (1), online test RSS;

Six (2), use V to reduce the RSS dimension to RSS ^* ;

Six (3), using the KNN algorithm for matching and positioning to output positioning results;

Six (four), user positioning terminal positioning database update;

That is, the offline stage implementation of a WiFi indoor positioning method based on category matching semi-supervised manifold learning is completed.

Both the offline phase and the online phase are completed at the positioning terminal.

Specific embodiment two: the difference between this embodiment and specific embodiment one is: adopt GMST intrinsic dimension estimation algorithm to analyze the intrinsic dimension of the Radio Map constructed in step one in step two, its calculation formula is:

Geodesic minimum spanning tree algorithm

In the above formula A in represents the slope of the linear fitting expression y=ax+b of the minimum spanning tree.

Other steps and parameters are the same as those in Embodiment 1.

Specific embodiment three: the difference between this embodiment and specific embodiment one or two is: in the step 4, generate a new dimensionality-reduced signal coverage map RadioMap ^* and the V' expression in the step 6 is:

Radio Map*=V′·X

X is a Radio Map that needs dimensionality reduction.

Other steps and parameters are the same as those in Embodiment 1 or Embodiment 2.

Specific implementation mode four: this implementation mode is different from one of specific implementation modes one to three in that: the realization of category matching in step five, its core process is completed in two steps:

The first step is to find the category attribute of unmarked RSS, and complete the category attribute labeling by the following formula:

Step 2: Threshold detection of RSS: By calculating and determining the relationship between the generalized symbol value and the threshold value, the update of the Radio Map and category tag data is realized, and the update of the generalized symbol value and cluster center is completed by the following two formulas:

Wherein, the threshold value V _T =0.9N.

Other steps and parameters are the same as those in Embodiments 1 to 3.

Specific embodiment five: the WiFi online stage indoor positioning method based on category matching semi-supervised manifold learning is realized through the following steps:

1. Test RSS online;

2. The RSS of the point to be located is obtained by using the feature transformation matrix dimensionality reduction transformation to obtain RSS*;

3. Use the KNN algorithm to match RSS* and Radio Map*, predict the specific location coordinates of the positioning point and update the online data. The implementation process is as follows:

(1) In the online stage, the RSS=[AP ₁ ,AP ₂ ,…,AP _n ] received at the test point is multiplied by the feature transformation matrix V′, so as to obtain the reduced RSS′=[AP ₁ ,AP ₂ ,...AP _d ], where d represents the intrinsic dimension;

(2) Use the KNN algorithm to realize the matching between RSS′ and Radio Map*, and use the average value of the coordinates of the K reference points closest to RSS′ as the test point (x′, y′), whose expression is:

In the formula, (x′, y′) is the predicted coordinate of the test point, ( _xi , y _i ) is the coordinate of the i-th neighbor point, and K is the number of neighbors in the KNN algorithm;

4. The user positioning terminal positioning database is updated, that is, the indoor positioning method in the WiFi online stage is completed based on category matching semi-supervised manifold learning;

The offline stage is completed on the server; the online stage is completed on the positioning terminal.

Specific embodiment six: the difference between this embodiment and specific embodiment five is: in step 3, the specific position coordinates of the positioning point to be predicted and the updating of online data are realized by the offline database and the online database described in claim 1:

The implementation of the offline positioning database is as follows: the RSS measured by the positioning user in this positioning is added to the Radio Map as unmarked data by category matching, and the local online matching positioning database is updated on the mobile terminal to realize dynamic Update local data to realize offline database positioning;

The implementation of the online database is as follows: After the user’s online positioning is completed, the RSS value measured online by the user is uploaded to the server where the online positioning database is located, and the online positioning database is updated on the server side, and the online positioning data is sent back to upload Positioning terminal for RSS data.

Other steps and parameters are the same as one of the specific embodiments 1 to 5.

Simulation:

1. A detailed description of this simulation experiment is given in conjunction with Figure 3: the diagram shows the floor plan of the 12th floor of Building 2A, Science Park, Harbin Institute of Technology, and the WiFi-based indoor positioning system is established based on this experimental environment. In the experimental environment, a total of 27 APs are arranged, and the location of the AP arrangement is where the blue wireless transmission signal shape mark is located. The height of the AP from the room floor is 2 meters. In the offline stage, NetStumbler software was installed on Lenovo V450 notebook, and 100 RSS values of APs and related information of APs were continuously sampled and recorded in four different orientations of all reference points. Store the physical coordinates of all sampling points and the corresponding physical coordinates and RSS values as the data called by the positioning process to establish a Radio Map. There are 900 reference points in the experimental environment, and the sampling density is 0.5m×0.5m, as shown in Figure 4. The Radio Map is used as the input parameter of the CM-SDE algorithm and the input data of the intrinsic dimension estimation algorithm.

2. The acquisition of the intrinsic dimension of the Radio Map is achieved through the following steps:

The intrinsic dimension is the minimum number of independent variables required for the intrinsic spatial dimension and spatial reconstruction of high-dimensional data. In actual calculations, since the eigenvalues of high-dimensional data are not obvious, it is usually not to seek the exact eigendimension, but to seek a credible value for estimating the eigendimension. Specifically, given a sample from a high-dimensional space, the central task and important content of the eigendimension estimation algorithm is to determine the eigendimension of this high-dimensional structure through these sample data.

The estimation of the eigendimension of the Radio Map is an important input parameter of the CM-SDE algorithm, which is related to whether the result of dimensionality reduction can represent the characteristics of the high-dimensional space of the Radio Map, so accurate and effective estimation of the eigendimension is crucial important. At present, the commonly used eigendimension estimation algorithms are divided into two categories: local estimation and global estimation. The eigendimension of RadioMap is estimated by global algorithm estimation, and it is used as the input variable of CM-SDE algorithm. In this experiment, the geodesic minimum spanning tree algorithm (Geodesic Minimum Spanning Tree, GMST) is used to estimate the intrinsic dimension of the Radio Map.

The theory of GMST algorithm is analyzed below.

Geodesic minimum spanning tree (GMST) estimation is based on the length function of the geodesic minimum spanning tree depending on the intrinsic dimension d. GMST refers to the minimum spanning tree of neighbor curves defined on the data set X. The length function L(X) of the GMST is the sum of the Euclidean distances corresponding to all edges in the geodesic minimum spanning tree.

GMST estimation constructs a neighbor curve G on the data set X, where each data point _xi in X is related to its k neighbors connected. A geodesic minimum spanning tree T is defined as the smallest curve on X that has length

in, is the set of all subtrees of the curve G, e is an edge of the tree T, g _e is the Euclidean distance corresponding to the edge e, and its calculation formula is shown in formula (2).

g _e =||x _i -x _j ||,x _i ,x _j ∈ e (2)

In GMST estimation, some subset consists of various sizes m, and the length L(A) of the GMST of the subset A also needs to be calculated. In theory, It is linear, so it can be estimated by a function of the form y=ax+b, and the variables a and b can be estimated by the least square method. It can be shown that from the estimated value of a and An estimate of the eigendimension can be obtained. The expression of the intrinsic dimension d given by the GMST algorithm is shown in formula (3). The intrinsic dimension d is another important input parameter of the CM-SDE algorithm.

3. CM-SDE is a semi-supervised manifold learning algorithm. During the implementation of CM-SDE algorithm, it is necessary to classify all reference points. Considering that in the current WiFi indoor positioning environment, the number of reference points is nearly 1000 points, and all the reference points are not artificially labeled, but a certain classification algorithm is used to mark the category of the reference points.

The goal of clustering is to divide the data set X={x ₁ ,x ₂ ,…,x _n } into c categories and the data of each category are not related to each other. The basic clustering algorithm is implemented as follows:

(1) Generate c cluster centers, denoted as v _i , i=1,2,...,c.

(2) Classify each element of the data set X={x ₁ ,x ₂ ,…,x _n }, and use the nearest neighbor (Nearest Neighbor) algorithm to determine the belonging relationship of the elements. The equivalent expression is:

In formula (4), x _i is the i-th data point, and G _i is the adjacency graph formed by the i-th class. D( _xi ,v _j ) means to calculate the Euclidean distance between x _i and v _j .

(3) The update of the cluster center, for the cluster center of the i-th class, the update is:

In formula (5), |·| means to calculate the number of elements in a certain class.

(4) Convergence check and iteration

If one of the convergence conditions in the following four cases is satisfied, the iteration stops, otherwise (2)-(3) are repeated until the iteration converges or the maximum number of executions is reached. The four convergence criteria are:

Condition 1: The cluster center remains unchanged;

Condition 2: The elements of each cluster are unchanged;

Condition 3: The change of the cluster center converges within the radius ε;

Condition 4: The change of clustering elements converges within the radius ε.

In general, the above convergence judgment conditions can be expressed as the following formula:

max||v _i -v _i ′||≤ε,ε≥0 (6)

Among them, v _i ′ represents the updated cluster center of the i-th class.

From the analysis of the basic implementation of the clustering algorithm above, the algorithm used to determine the belonging relationship of elements constitutes the core of clustering. Different types of clustering algorithms propose different classification indicators, and this function is generally called a loss function (LossFunction). The basic clustering method uses Euclidean distance as the loss function. This patent uses the KFCM algorithm to analyze the category of the RadioMap to obtain the cluster center and the category label of the Radio Map. The theoretical analysis of the KFCM algorithm is as follows:

The goal of fuzzy c-means clustering with kernel function is to transform the space where the original data set is located into infinite-dimensional Hilbert Space (Hilbert Space), and then perform corresponding cluster analysis on the transformed space. Through the transformation of the kernel function, it is easier to express and distinguish the category features between the original data after further transformation. The objective function of the fuzzy c-means clustering algorithm based on kernel function is:

In formula (7), Φ(x _k ) and W _i represent the data set and the corresponding cluster center in the Hilbert space respectively. Through derivation, it can be concluded that the solution of KFCM algorithm is expressed as:

The key to the solution of KFCM is to calculate the loss function or similarity function of the Hilbert space. In this paper, the theoretical analysis and implementation of the FCM (Fuzzy C-Means) algorithm that introduces the Gaussian Kernel Function (Gaussian Kernel Function) are considered. The Gaussian kernel function is shown in formula (9).

In Hilbert space, by Expressing its corresponding loss function, this formula is further expressed as formula (10).

In formula (10), <·,·> means to calculate the kernel function value of the corresponding formula. In fact, the transformation of infinite space does not exist, therefore, formula (10) is further simplified as shown in formula (11).

The fully expanded formula of formula (11) is shown in formula (12).

In formula (12), <Φ(x _k ),Φ(x _j )> is calculated by Gaussian kernel function, namely:

In the implementation of the algorithm, instead of randomly generating cluster centers, c elements are randomly selected from the data set X={x ₁ ,x ₂ ,…,x _n } as cluster centers to form a set Y={y ₁ , ..., y _c }. Therefore, the initialized loss function value is calculated as shown in Eq.

4. Use the CM-SDE algorithm to reduce the dimension of the Radio Map and obtain the feature weight matrix through the following steps:

The CM-SDE algorithm is a manifold learning algorithm based on maximizing the inter-class divergence and intra-class divergence between labeled data and unlabeled data. Before the theoretical analysis of the CM-SDE algorithm, the input data given by the CM-SDE algorithm is explained as follows: Input high-dimensional data points The class label of the data point _xi is y _i ∈ {1,2,…,P}, where P means to divide the high-dimensional data into P submanifolds, that is, to divide the input high-dimensional data into P classes, and record the clustering of P classes The class center is V={v ₁ ,v ₂ ,…,v _P }. Express the input high-dimensional data in the form of matrix: X=[x ₁ ,x ₂ ,…,x _m ]∈R ^n×m . From the form of matrix representation, the columns in the matrix represent a high-dimensional data point.

For a RadioMap _ul containing unlabeled data, all unlabeled data X _u =[x _u1 ,x _u2 ,…,x _uk ]∈R ^n×k are used for category matching, and the labeled data are recorded as X _l =[x _l1 ,x _l2 ,…,x _lc ]∈R ^n×c . Ordinal category matching is performed for all data in X _u . The meaning of order is that when a certain unlabeled data is assigned, it will affect the cluster center of the corresponding class, so it will affect the class discrimination of the next unlabeled data. The time sequence of signal acquisition is mainly considered in this patent. Assume X _u is in chronological order. Use formula (15) to calculate the class belonging x _u1 , and use formula (5) to update the corresponding cluster center. Then classify all unlabeled data in turn

The objective function of the CM-SDE algorithm is:

In formula (16), S _w , S _b , and S _t represent intra-class divergence, inter-class divergence and total divergence respectively, which can be calculated by formula (17):

In formula (17), is the mean value of the i-th class, l _i is the number of sampling points of the i-th class; is the mean value of all sampling points, and N is the number of sampling points.

For the objective function shown in formula (16), it can also represent the objective function form of the local discriminative embedding manifold learning algorithm, and its expression is:

In formula (18), w _ij represents the weight distribution among data of the same type, and w _ij ′ represents the weight distribution among data of different types, expressed as W _N×N and W _N×N ′ respectively. The weight calculation process is completed in two steps. Step 1: Construct a neighborhood graph. Construct undirected graphs G and G′ according to the class label information of high-dimensional data points and their neighbor relations. Among them, the neighbor relationship is the criterion given by the KNN algorithm, that is, select the nearest K points of the data point as its neighbors, and G means that when the class label information y _i of x _i and x _j = y _j and x _i and x _j mutually is the K-nearest neighbor relationship; G′ indicates that when the class label information y _{i ≠} y _j of x _i and x _{j is} the K-nearest neighbor relationship. Step 2: Calculate the weight matrix. According to the adjacency graph constructed in the first step, a Gaussian function is used to calculate the weight matrix. Its expressions (19), (20) are as shown. In the formula, w _ij represents the weight between the neighbor point x _i and x _j , || _xi -x _j || ² is the distance between the neighbor point and x _j , the distance is calculated by matrix, and t is the weight Normalization parameters, U, L represent the number of unmarked and marked sampling points, respectively. According to the analysis, it can be known that W _N×N and W _N×N ′ can be composed of three parts, namely: the weight between marked data and marked data, the weight between marked data and unmarked data, and the weight between unmarked data and unmarked data. The weights between data and unlabeled data are expressed as:

From the above calculation formula and the properties of the matrix, we can get: From this, it can be deduced that W _N×N and W _N×N ′ are expressed in the form of block matrix, as shown in formula (21).

According to the calculation formula of the matrix: The calculation formula is expressed as the calculation method of the matrix of the matrix A, and the method given by the calculation formula is consistent with the calculation formula of the trace of the matrix, namely: ||A|| ² =tr(AA ^T ). From this formula (18) can be expressed as the calculation method of the trace of the matrix:

Formula (22) can be simplified as:

The scalar properties and weight elements of the calculation of the matrix trace are all real numbers, and the formula (23) can be simplified as:

According to the simple mathematical relationship, formula (24) can be simplified as:

J(V)=2tr{V ^T [X(D′-W′ _N×N )X ^T ]V} (25)

In formula (25): X is the input data, λ and v are the eigenvalues and eigenvectors, W and W′ are the weight matrices corresponding to G and G′ respectively, D and D′ are diagonal matrices, and their diagonal Elements can be represented by formula (26).

According to the derivation method of formula (25), similarly, the constraints in formula (18) can be written in a form similar to formula (25). Therefore, (18) can be expressed as the following form:

Applying the Lagrange multiplier method to formula (27), it can be obtained as shown in formula (28):

X(D′-W′ _N×N )X ^T v=λX(DW _N×N )X ^T v (28)

Carry out generalized eigenvalue decomposition on formula (28), and obtain the eigenvalue and eigenvector of its eigenvalue decomposition, expressed as: λ=[λ ₁ ,λ ₂ ,…,λ _n ] ^T , and the corresponding eigenvector is: v=[v ₁ ,v ₂ ,…,v _n ] ^T . Take the eigenvectors corresponding to the first d largest eigenvalues to form a transformation matrix V=[v ₁ ,v ₂ ,…,v _d ]. From the output data transformation method of the CM-SDE algorithm, it can be concluded that the data after dimensionality reduction is:

z _i = V ^T x _i (29)

In Equation (29), _zi represents the low-dimensional output data transformed from the input high-dimensional data point _xi . The implementation steps of the off-line stage given by the content of the invention in this patent are: the first step is to use the CM-SDE algorithm to perform dimensionality reduction processing on all reference point Radio Maps, and obtain the corresponding dimensionality reduction Radio Maps of the reference points, namely As a matching localization database (RadioMap ^* ) for the online phase. The second step is to reduce the dimensionality of the Radio Map with unmarked data, that is, RadioMap _ul , to obtain the feature transformation matrix V′. From this the required databases for the offline phase can be created: RadioMap ^* and V'.

5. The RSS obtained by different users in the online stage positioning stage is not marked with category attributes, and the process of adding it to Radio Map and forming Radio Map _ul is called category. Its implementation method is as follows:

Add the unmarked RSS obtained from the positioning stage test of different users in the online stage to the existing Radio Map by category matching, and obtain the corresponding RadioMap _ul that contains unmarked signal coverage; increase the data volume of the Radio Map through the category matching method, Furthermore, the density of the Radio Map can be increased to provide new dimensionality reduction data for the CM-SDE algorithm. At the same time, the cluster center can be updated to provide new category data for the CM-SDE algorithm. The category matching method is divided into two steps, and its implementation process is as follows:

In the first step, look for category attributes of untagged RSS. Record a group of unlabeled RSS as RSS _i , match it with the cluster center in step 3, and complete the category labeling of RSS _i by formula (4).

Step 2: Perform threshold detection on the RSS. The cluster center vi is expressed as v _i =(v _i1 ,v _i2 ,...,v _iN ), and N is the number of APs in the indoor positioning system. RSS _i is expressed as RSS _i =(RSS _i1 ,RSS _i2 ,...,RSS _iN ). Computes the generalized symbolic value defined by:

Among them, sgn( ) is defined as:

When S _i is greater than the set threshold value, add RSS _i to the Radio Map and update the cluster center, otherwise discard RSS _i and not add it to the Radio Map. In this patent, the threshold V _T =0.9N. The update of the cluster center is completed by formula (5):

6. Offline database implementation of WiFi indoor positioning method based on CM-SDE algorithm:

The offline database mode consists of three parts. First, establish the Radio Map of all reference points, and use the CM-SDE algorithm to obtain RadioMap ^* . Second, randomly sample the unmarked data of point U and add it to the original Radio Map, and use the CM-SDE algorithm to obtain V′, and download (store) the formed positioning database to the positioning mobile terminal. Third, realize online positioning and update Radio Map. The specific implementation of the third part is as follows:

In the online phase, the RSS received at the test point=[AP ₁ ,AP ₂ ,...,AP _n ], where n represents the number of APs deployed by the indoor positioning system. Multiply the RSS with the feature transformation matrix V′ to obtain the dimensionally reduced RSS′=[AP ₁ ,AP ₂ ,…,AP _d ], where d represents the intrinsic dimension. Then use the KNN algorithm to realize the matching between RSS′ and RadioMap ^* . The average value of the coordinates of the K reference points closest to RSS' is used as the test point (x', y'), and its expression is:

The RSS measured by the positioning user in this positioning is added to the RadioMap as unmarked data by category matching, and the local online matching positioning database is updated on the mobile terminal, and the local data is dynamically updated, thereby realizing the offline database The positioning method, shown in Figure 1, is implemented in the user positioning terminal in the WiFi indoor positioning method of the semi-supervised manifold learning of category matching;

7. Online database implementation of WiFi indoor positioning method based on CM-SDE algorithm:

The online database method consists of four parts. First, establish the Radio Map of all reference points, and use the CM-SDE algorithm to obtain RadioMap ^* . Second, randomly sample the unmarked data of point U and add it to the original Radio Map, and use the CM-SDE algorithm to obtain V′, and download (store) the formed positioning database to the positioning mobile terminal. Third, realize online positioning and update Radio Map. The specific implementation of the third part is as follows:

In the online phase, the RSS received at the test point=[AP ₁ ,AP ₂ ,...,AP _n ], where n represents the number of APs deployed by the indoor positioning system. Multiply the RSS with the feature transformation matrix V′ to obtain the dimensionally reduced RSS′=[AP ₁ ,AP ₂ ,…,AP _d ], where d represents the intrinsic dimension. Then use the KNN algorithm to realize the matching between RSS′ and RadioMap ^* . The average value of the coordinates of the K reference points closest to RSS' is used as the test point (x', y'), and its expression is:

Part 4: After the user's online positioning is completed, upload the RSS value measured online by the user to the server where the online positioning database is located, and update the online positioning database on the server side, and send the online positioning data back to the server that uploaded the RSS data The positioning terminal, that is, the offline phase shown in Figure 2 is completed on the server where the online positioning database is located, while the online phase is completed on the positioning terminal.

Claims (6)

1. The WiFi indoor positioning method based on semi-supervised manifold learning of class matching is characterized in that the positioning process of the WiFi indoor positioning method based on semi-supervised manifold learning of class matching in the off-line stage is realized according to the following steps:

firstly, arranging an access point AP in an indoor area to be positioned, enabling a wireless signal to cover the indoor area to be positioned, and completing the construction of a wireless fidelity WiFi network;

selecting and recording corresponding coordinates of a reference point in an indoor area to be positioned regularly, measuring and sequentially recording signal strength RSS signals of all APs received by the reference point as position characteristic information, constructing a network signal coverage Map Radio Map, and storing the Radio Map;

secondly, analyzing the intrinsic dimension of the Radio Map constructed in the first step by adopting a geodesic minimum spanning tree GMST intrinsic dimension estimation algorithm, and determining the dimension of the Radio Map after dimension reduction by using the obtained intrinsic dimension as one of input parameters of a class matching-based semi-supervised local identification embedded CM-SDE algorithm;

thirdly, performing clustering analysis on the Radio Map by adopting a kernel fuzzy C mean KFCM algorithm to realize the established class mark of the Radio Map, using the class mark as one of input parameters of the CM-SDE, and providing a corresponding initial clustering center and the corresponding class mark;

fourthly, taking the intrinsic dimension in the second step and the category mark in the third step as input parameters, adopting a CM-SDE algorithm to reduce the dimension of the Radio Map constructed in the first step, and obtaining a corresponding dimension-reduced network signal overlay Radio Map^*，RadioMap^*As in the matching location database for the online location phase;

fifthly, adding the unmarked RSS obtained by the test of different users in the on-line positioning stage into the existing Radio Map by adopting a category matching mode to obtain the corresponding Radio Map containing the unmarked signal overlay_ulThe cluster center updated by class matching is used as a new class input parameter in the CM-SDE algorithm;

sixthly, taking the updated clustering center in the step five as an input parameter, and adopting a CM-SDE algorithm to perform the RadioMap_ulDimension reduction to obtain characteristic transformation matrixes V ', V' and RadioMap^*Together forming an online matching positioning database for online stage positioning; wherein the line stage positioning specifically comprises:

sixthly, testing RSS on line;

sixthly, adopting V to reduce the RSS dimension into the reduced signal strength RSS^*；

Sixthly, matching and positioning by adopting a K nearest neighbor method KNN algorithm to output a positioning result;

sixthly, updating a user positioning terminal positioning database;

namely, an off-line stage implementation mode of the WiFi indoor positioning method based on semi-supervised manifold learning of class matching is completed.

2. The WiFi indoor positioning method based on class matching semi-supervised manifold learning as recited in claim 1, wherein in the second step, GMST eigen-dimension estimation algorithm is adopted to analyze eigen-dimension of the Radio Map constructed in the first step, and the calculation formula is as follows:

$d_{\mathrm{int}rinsi\dim }=\frac{1}{1-a},$

in the above formulaA in (a) represents the slope of the linear fitting expression y of the minimum spanning tree, ax + b.

3. The WiFi indoor positioning method based on semi-supervised manifold learning of class matching as claimed in claim 1, wherein the new dimension-reduced signal coverage map RADIO MAP is generated in step four^*And V' in the sixth step is expressed as:

Radio Map*＝V′·X

x is the Radio Map that needs dimension reduction.

4. The WiFi indoor positioning method based on semi-supervised manifold learning of class matching as claimed in claim 1, wherein class matching is implemented in step five, and the core process is completed in two steps:

firstly, finding the category attribute of the unmarked RSS, and finishing the marking of the category attribute according to the following formula:

the second step is that: performing threshold detection on RSS: by calculating and determining the generalized symbol value and the threshold value V_TThe updating of the Radio Map and the class mark data is realized, and the updating of the generalized symbol value and the clustering center is respectively completed by the following two formulas:

$S_i=\underset{j=1}{\overset{N}{\&Sigma;}}\mathrm{sgn}({\mathrm{RSS}}_{ij}-v_{ij})$

$v_i=\frac{1}{\left|G_i\right|}\underset{x_k\&Element;G_i}{\&Sigma;}{x}_k$

wherein the threshold value V_T0.9N; c is the number of clustering centers; x is the number of_iIs the ith data point; g_iThe adjacency graph is formed by the ith class; d (x)_i,v_j) Representing a calculation x_iAnd v_jEuropean distance betweenSeparating; | represents calculating the number of elements in a certain class; n is the number of APs in the indoor positioning system; sgn (·) is defined as:

5. the WiFi indoor positioning method based on semi-supervised manifold learning of class matching as claimed in claim 1, wherein the WiFi indoor positioning method based on semi-supervised manifold learning of class matching is implemented in an online stage positioning process through the following steps:

firstly, testing RSS on line;

secondly, performing dimensionality reduction transformation on the obtained RSS to be located by adopting a feature transformation matrix to obtain RSS;

thirdly, matching RSS and Radio Map by adopting a KNN algorithm, predicting the specific position coordinate of the to-be-positioned point and updating online data, wherein the implementation process comprises the following steps:

(1) in the online phase, RSS received at the test point is [ AP ]₁,AP₂,…,AP_n]Multiplying the obtained result by a feature transformation matrix V 'to obtain the RSS' after dimension reduction ═ AP₁,AP₂,…AP_d]Wherein d represents an intrinsic dimension;

(2) the matching of RSS 'and Radio Map is realized by adopting a KNN algorithm, and the average value of the coordinates of K reference points nearest to the RSS' is used as a test point (x ', y'), wherein the expression is as follows:

$(x^{\&prime;},y^{\&prime;})=\frac{1}{K}\underset{i=1}{\overset{K}{\&Sigma;}}(x_i,y_i)$

wherein (x ', y') is the predicted coordinate of the test point, (x)_i,y_i) The coordinate of the ith neighbor point is shown, and K is the number of neighbors in the KNN algorithm;

and fourthly, updating a positioning database of the user positioning terminal, namely completing the WiFi on-line stage indoor positioning method based on semi-supervised manifold learning of category matching.

6. The WiFi indoor positioning method based on semi-supervised manifold learning of class matching according to claim 5, wherein the prediction of the specific position coordinates of the point to be positioned and the update of the online data in the third step are realized by an offline database and an online database:

the off-line database is realized in the following way: adding RSS measured by a positioning user in the positioning process into a Radio Map as unmarked data in a category matching mode, updating a local online matching positioning database on the mobile terminal, and dynamically updating local data so as to realize an offline database positioning mode;

the online database is realized in the following way: after the online positioning of the user is completed, the RSS value measured online by the user is uploaded to a server where an online positioning database is located, the online positioning database is updated at the server side, and the online positioning data is returned to a positioning terminal which uploads the RSS data.