WO2024245413A1 - Post-correction-based high-entropy knn clustering method and device, and medium - Google Patents

Abstract

The present application relates to the field of electric digital data processing, and discloses a post-correction-based high-entropy KNN clustering method and device, and a medium. The method comprises: determining a set of samples needing to be clustered, and carrying out initial classification on a plurality of specified samples in the set of samples on the basis of the mode of a same similarity; selecting K prior samples closest to samples to be classified as comparison samples; on the basis of the mode of different similarities, obtaining category labels of the samples to be classified; and re-classifying the plurality of prior samples on the basis of the mode of different similarities. The accuracy of prior samples is effectively guaranteed, then on the basis of the mode of different similarities, the requirements of inter-class homogeneity and intra-class heterogeneity are effectively met, and finally, the prior samples are subjected to post-correction and re-classification, so that the high-entropy clustering process of all the samples can be achieved, and the requirements for high-entropy clustering are met.

Description

A high entropy KNN clustering method, device and medium based on post-correction

This application claims the priority of the Chinese patent application filed with the China Patent Office on June 1, 2023, with application number 202310636506.0 and invention name “A high entropy KNN clustering method, device and medium based on post-correction”, the entire contents of which are incorporated by reference in this application.

Technical Field

The present application relates to the field of electronic digital data processing, and in particular to a post-correction based high entropy KNN clustering method, device and medium.

Background Art

K-NearestNeighbor (KNN) is a supervised learning algorithm that can determine the state of a sample based on the states of its K nearest neighbors and is often used for sample classification. Generally speaking, the KNN algorithm can present the characteristics of being very different between classes and homogeneous within classes, that is, it can achieve the effect of high entropy between classes and low entropy within classes.

However, with the development of technology, some application requirements have emerged, such as homogeneity between classes and heterogeneity within classes. For example, when classifying multiple types of products or multiple types of data, it is only necessary to ensure that each type of product or data in each category meets a certain proportion. In this case, during the classification process, it is necessary to ensure the effect of low entropy between classes and high entropy within classes, which is difficult to achieve through the traditional KNN algorithm.

Summary of the invention

In order to solve the above problems, this application proposes a high entropy KNN clustering method based on post-correction, including:

Determine a sample set that needs to be clustered, and initialize classification for a number of designated samples in the sample set based on the same similarity;

The sample that has completed the initial classification is used as a priori sample, and for the remaining samples to be classified in the sample set except the priori sample, the sample with the closest distance to the sample to be classified is selected. K prior samples are used as comparison samples; K is a preset positive integer value;

Based on the difference in similarity and the category labels of the comparison samples determined in the initial classification, the category labels of the samples to be classified are obtained until all the samples to be classified are classified;

Based on the difference in similarity, several prior samples are reclassified.

On the other hand, the present application also proposes a post-correction based high entropy KNN clustering device, comprising:

at least one processor; and,

a memory communicatively connected to the at least one processor; wherein,

The memory stores instructions that can be executed by the at least one processor, and the instructions are executed by the at least one processor to enable the at least one processor to perform, for example:

Determine a sample set that needs to be clustered, and initialize classification for a number of designated samples in the sample set based on the same similarity;

The sample that has completed the initialization classification is used as a priori sample, and for the remaining samples to be classified in the sample set except the priori sample, K priori samples that are closest to the samples to be classified are selected as comparison samples; K is a preset positive integer value;

Based on the difference in similarity and the category labels of the comparison samples determined in the initial classification, the category labels of the samples to be classified are obtained until all the samples to be classified are classified;

Based on the difference in similarity, several prior samples are reclassified.

The present application also proposes a non-volatile computer storage medium storing computer executable instructions, wherein the computer executable instructions are configured as follows:

Determine a sample set that needs to be clustered, and initialize classification for a number of designated samples in the sample set based on the same similarity;

The sample that has completed the initialization classification is used as a priori sample, and for the remaining samples to be classified in the sample set except the priori sample, K priori samples that are closest to the samples to be classified are selected as comparison samples; K is a preset positive integer value;

Based on the difference in similarity and the category labels of the comparison samples determined in the initial classification, the category labels of the samples to be classified are obtained until all the samples to be classified are classified;

Based on the difference in similarity, several prior samples are reclassified.

The high entropy KNN clustering method based on post-correction proposed in this application can bring the following beneficial effects:

The prior samples are obtained through the traditional method of the same similarity, which effectively guarantees the accuracy of the prior samples. Then, based on the method of different similarities, the requirements of homogeneity between classes and differences within classes are effectively met. Finally, the prior samples are post-corrected and reclassified to realize the high-entropy clustering process of all samples, meeting the needs for high-entropy clustering.

BRIEF DESCRIPTION OF THE DRAWINGS

The drawings described herein are used to provide a further understanding of the present application and constitute a part of the present application. The illustrative embodiments of the present application and their descriptions are used to explain the present application and do not constitute an improper limitation on the present application. In the drawings:

FIG1 is a schematic diagram of a process of a high entropy KNN clustering method based on post-correction in an embodiment of the present application;

FIG2 is a schematic diagram of initialization classification in an embodiment of the present application;

FIG3 is a schematic diagram of the results of a traditional KNN clustering algorithm in an embodiment of the present application;

FIG4 is a schematic diagram of classification in different ways corresponding to the similarities in the first case in an embodiment of the present application;

FIG5 is a schematic diagram of classification in different ways corresponding to the similarities in the second case in an embodiment of the present application;

FIG6 is a schematic diagram of classification in different ways corresponding to the similarities in the third case in an embodiment of the present application;

FIG7 is a schematic diagram of classification results in different similarities according to an embodiment of the present application;

FIG8 is a schematic diagram of a priori sample post-correction in an embodiment of the present application;

FIG9 is a schematic diagram of a high entropy KNN clustering device based on post-correction in an embodiment of the present application.

DETAILED DESCRIPTION

In order to make the purpose, technical solution and advantages of this application clearer, the technical solution of this application will be clearly and completely described below in combination with the specific embodiments of this application and the corresponding drawings. Obviously, the described embodiments are only part of the embodiments of this application, not all of them. The embodiments in the application and all other embodiments obtained by ordinary technicians in this field without making any creative work are within the scope of protection of this application.

The technical solutions provided by various embodiments of the present application are described in detail below in conjunction with the accompanying drawings.

As shown in FIG1 , the embodiment of the present application provides a high entropy KNN clustering method based on post-correction, including:

S101: Determine a sample set that needs to be clustered, and perform initial classification for a number of designated samples in the sample set based on the same similarity.

Different from the traditional KNN clustering, the purpose of high entropy KNN clustering in this paper is different. In the pre-acquired data set, several data are selected, which can be product data, image data, audio data, etc.

Several data are used as sample sets to cluster the sample sets. At this time, the purpose of clustering is no longer to gather data of the same or similar categories into one cluster, but to make the data of different categories meet the preset ratio in the clusters of the clustering results. For example, taking product data as an example, in each cluster finally obtained, the ratio of product quality meets the preset ratio, and the ratio of excellent products, good products, and poor products meets the ratio of 5:3:2, which can achieve the preset purpose.

When initializing the classification, several designated samples are selected from the sample set. The designated samples here are samples with identifiable characteristics (also called significant characteristics). For example, taking product data as an example, some products are of excellent quality or have very obvious defects, which can be considered to have identifiable characteristics. Or, when recognizing image data, if the designated object is obviously present in the image, or if the designated object is obviously absent, it is considered to have identifiable characteristics. Generally speaking, the number of designated samples selected is small compared to the sample set.

For each designated sample, select the K samples closest to the designated sample, and use the category label with the most occurrences among the K samples as the category label of the designated sample. As shown in Figure 2, a total of 12 designated samples are selected and divided into two categories, which are marked with different icons in the figure. At this time, these designated samples are obtained in the same similarity, which conforms to the clustering process and effect in the traditional KNN clustering process.

S102: taking the samples that have completed the initialization classification as prior samples, and selecting K prior samples that are closest to the samples to be classified from the remaining samples to be classified in the sample set except the prior samples as comparison samples; K is a preset positive integer value.

The K value should not be too large or too small. Generally speaking, it is proportional to the sample size of the sample set. At this time, determine the sample size corresponding to the sample set, and determine the corresponding K value and the number of selected samples in the classification process according to the sample size. The ratio of the K value to the sample size is a positive integer within [0.03, 0.09], and the K value is an odd number. When the sample size is 100, the K value can be 3, 5, 7, or 9. The number of selected samples needs to be higher than the maximum value of the K value selection range to facilitate the selection of comparative samples.

S103: Based on the different similarities and the category labels of the comparison samples determined in the initial classification, the category labels of the samples to be classified are obtained until all the samples to be classified are classified.

As shown in Figure 3, according to the traditional KNN clustering algorithm, when clustering is still performed in the same similarity manner, the final result is still very different between classes and homogeneous within classes. At this time, the class is still in a low entropy state, which does not meet the requirements of this article.

Based on this, the method of similarity difference is adopted to determine the category labels that appear in the corresponding comparison samples for each sample to be classified, as well as the number of occurrences of each category label. Among all the category labels, the category label with the least number of occurrences is selected as the category label of the sample to be classified.

As shown in Figures 4, 5 and 6, let the K value be 3. For the convenience of description, the icons in the hollow boxes represent the first category, the icons with a cross in the box represent the second category, and the icons in the solid boxes represent the undetermined category. In Figure 4, among the three samples closest to sample 1, the number of the first category is 1, and the number of the second category is 2. The number of the first category is smaller, so sample 1 is the first category. In Figure 5, for sample 2, the number of the first category and the second category are 2 and 1 respectively, so sample 2 is the second category. In Figure 6, for sample 3, the number of the first category and the second category are 3 and 0 respectively, so the category of sample 3 is the second category. Similarly, it can be obtained that the category of sample 4 is the first category.

At this point, the final effect can be shown in Figure 7, achieving the effect of homogeneity between classes and great differences within classes. At this time, the class is in a high entropy state, which meets the requirements.

S104: Reclassify a number of prior samples based on different similarities.

In the above text, the samples to be classified have been clustered according to the method of different similarities. However, the a priori samples obtained at the beginning are still clustered according to the method of the same similarity, which does not meet the requirements. At this time, for each a priori sample, among the samples to be classified that have been classified (because the a priori samples do not meet the requirements, when selecting the comparison file, select the samples to be classified that have been classified). Take), select the nearest K prior samples as comparison samples. Similarly, determine the category labels that appear in the comparison samples, as well as the number of occurrences of each category label. Among all category labels, select the category label with the least number of occurrences as the category label obtained after reclassification of the prior sample.

As shown in Figure 8, the circled samples are prior samples. By comparing them with the three closest comparison samples in terms of similarity difference, it is found that they need to be changed in category, so they are changed from the first category to the second category. Therefore, the prior samples are reclassified through post-correction, and the clustering of all samples in terms of similarity difference is completed, so that all samples in the sample set finally meet the requirements.

The prior samples are obtained through the traditional method of the same similarity, which effectively guarantees the accuracy of the prior samples. Then, based on the method of different similarities, the requirements of homogeneity between classes and differences within classes are effectively met. Finally, the prior samples are post-corrected and reclassified to realize the high-entropy clustering process of all samples, meeting the needs for high-entropy clustering.

In one embodiment, it is described above that the closest sample needs to be selected as a comparison sample. When calculating the distance between samples, the number of dimensions contained in each sample in the sample set is determined, and the distance between the sample to be classified and all other prior samples is calculated based on the number of dimensions, so as to select the K prior samples with the closest distance as comparison samples.

The number of dimensions usually includes one-dimensional to three-dimensional data. For example, text data contains one-dimensional data of text, 2D plane images contain two-dimensional data of pixels on the x-axis and y-axis, and product data contains three-dimensional data of appearance, function, and price.

When the samples in the sample set are one-dimensional, the distance between the sample to be classified and the prior sample is obtained by d _i =| _xi - _x1 |, where d _i is the distance between the sample to be classified and the i-th prior sample, _xi is the coordinate of the i-th prior sample, and _x1 is the coordinate of the sample to be classified.

When the samples in the sample set are two-dimensional, The distance between the sample to be classified and the prior sample is obtained, where d _i is the distance between the sample to be classified and the i-th prior sample, (x _i , y _i ) is the coordinate of the i-th prior sample, and (x ₁ , y ₁ ) is the coordinate of the sample to be classified;

When the samples in the sample set are three-dimensional, Get the distance between the sample to be classified and the prior sample, where d _i is the distance between the sample to be classified and the i-th prior sample, (x _i , y _i , z _i ) is the coordinate of the i-th prior sample, and (x ₁ , y ₁ , z ₁ ) is the coordinate of the sample to be classified. Coordinates of the classified samples.

Of course, the number of dimensions can also include more dimensions, in which case a similar formula can be derived to calculate the distance between samples.

As shown in FIG9 , the present application also proposes a post-correction based high entropy KNN clustering device, comprising:

at least one processor; and,

a memory communicatively connected to the at least one processor; wherein,

The memory stores instructions that can be executed by the at least one processor, and the instructions are executed by the at least one processor to enable the at least one processor to perform, for example:

Determine a sample set that needs to be clustered, and initialize classification for a number of designated samples in the sample set based on the same similarity;

The sample that has completed the initialization classification is used as a priori sample, and for the remaining samples to be classified in the sample set except the priori sample, K priori samples that are closest to the samples to be classified are selected as comparison samples; K is a preset positive integer value;

Based on the difference in similarity and the category labels of the comparison samples determined in the initial classification, the category labels of the samples to be classified are obtained until all the samples to be classified are classified;

Based on the difference in similarity, several prior samples are reclassified.

The present application also proposes a non-volatile computer storage medium storing computer executable instructions, wherein the computer executable instructions are configured as follows:

Determine a sample set that needs to be clustered, and initialize classification for a number of designated samples in the sample set based on the same similarity;

The sample that has completed the initialization classification is used as a priori sample, and for the remaining samples to be classified in the sample set except the priori sample, K priori samples that are closest to the samples to be classified are selected as comparison samples; K is a preset positive integer value;

Based on the difference in similarity and the category labels of the comparison samples determined in the initial classification, the category labels of the samples to be classified are obtained until all the samples to be classified are classified;

Based on the difference in similarity, several prior samples are reclassified.

The various embodiments in this application are described in a progressive manner. The same or similar parts between the various embodiments can be referred to each other. Each embodiment focuses on the differences from other embodiments. In particular, for the device and medium embodiments, since they are basically similar to the method embodiments, the description The method is relatively simple, and the relevant parts can be referred to the partial description of the method embodiment.

The devices and media provided in the embodiments of the present application correspond one-to-one to the methods. Therefore, the devices and media also have similar beneficial technical effects as the corresponding methods. Since the beneficial technical effects of the methods have been described in detail above, the beneficial technical effects of the devices and media will not be repeated here.

Those skilled in the art will appreciate that the embodiments of the present application may be provided as methods, systems, or computer program products. Therefore, the present application may adopt the form of a complete hardware embodiment, a complete software embodiment, or an embodiment in combination with software and hardware. Moreover, the present application may adopt the form of a computer program product implemented in one or more computer-usable storage media (including but not limited to disk storage, CD-ROM, optical storage, etc.) that include computer-usable program code.

The present application is described with reference to the flowchart and/or block diagram of the method, device (system) and computer program product according to the embodiment of the present application. It should be understood that each process and/or box in the flowchart and/or block diagram, and the combination of the process and/or box in the flowchart and/or block diagram can be realized by computer program instructions. These computer program instructions can be provided to a processor of a general-purpose computer, a special-purpose computer, an embedded processor or other programmable data processing device to produce a machine, so that the instructions executed by the processor of the computer or other programmable data processing device produce a device for realizing the function specified in one process or multiple processes in the flowchart and/or one box or multiple boxes in the block diagram.

These computer program instructions may also be stored in a computer-readable memory that can direct a computer or other programmable data processing device to work in a specific manner, so that the instructions stored in the computer-readable memory produce a manufactured product including an instruction device that implements the functions specified in one or more processes in the flowchart and/or one or more boxes in the block diagram.

These computer program instructions may also be loaded onto a computer or other programmable data processing device so that a series of operational steps are executed on the computer or other programmable device to produce a computer-implemented process, whereby the instructions executed on the computer or other programmable device provide steps for implementing the functions specified in one or more processes in the flowchart and/or one or more boxes in the block diagram.

In a typical configuration, a computing device includes one or more processors (CPU), input/output interfaces, network interfaces, and memory.

Memory may include non-permanent storage in a computer-readable medium, in the form of random access memory (RAM) and/or non-volatile memory, such as read-only memory (ROM) or flash memory (flash RAM). Memory is an example of a computer-readable medium.

Computer-readable media include permanent and non-permanent, removable and non-removable media that can be stored in any computer. Any method or technology to achieve information storage. Information can be computer-readable instructions, data structures, modules of programs or other data. Examples of computer storage media include, but are not limited to, phase change memory (PRAM), static random access memory (SRAM), dynamic random access memory (DRAM), other types of random access memory (RAM), read-only memory (ROM), electrically erasable programmable read-only memory (EEPROM), flash memory or other memory technology, compact disk read-only memory (CD-ROM), digital versatile disk (DVD) or other optical storage, magnetic cassettes, magnetic tape magnetic disk storage or other magnetic storage devices or any other non-transmission media that can be used to store information that can be accessed by a computing device. As defined herein, computer-readable media does not include transitory media such as modulated data signals and carrier waves.

It should also be noted that the terms "include", "comprises" or any other variations thereof are intended to cover non-exclusive inclusion, so that a process, method, commodity or device including a series of elements includes not only those elements, but also other elements not explicitly listed, or also includes elements inherent to such process, method, commodity or device. In the absence of more restrictions, the elements defined by the sentence "comprises a ..." do not exclude the existence of other identical elements in the process, method, commodity or device including the elements.

The above is only an embodiment of the present application and is not intended to limit the present application. For those skilled in the art, the present application may have various changes and variations. Any modification, equivalent replacement, improvement, etc. made within the spirit and principle of the present application should be included in the scope of the claims of the present application.

Claims (7)

A high entropy KNN clustering method based on post-correction, comprising: Determine a sample set that needs to be clustered, and initialize classification for a number of designated samples in the sample set based on the same similarity; wherein, in a pre-acquired data set, select a number of data as the sample set, and the number of data is product data; the designated samples are samples with identifiable characteristics, and the identifiable characteristics include excellent product quality and defective products; The sample that has completed the initialization classification is used as a priori sample, and for the remaining samples to be classified in the sample set except the priori sample, K priori samples that are closest to the samples to be classified are selected as comparison samples; K is a preset positive integer value; Based on the difference in similarity and the category labels of the comparison samples determined in the initial classification, the category labels of the samples to be classified are obtained until all the samples to be classified are classified; Based on the difference in similarity, several prior samples are reclassified so that the proportion of product quality in each cluster finally obtained meets the preset proportion; Initializing classification for a number of designated samples in the sample set based on the same similarity, specifically including: Determining a number of designated samples that have been selected from the sample set; For each specified sample, select the K samples closest to the specified sample, and use the category label with the largest number of occurrences among the K samples as the category label of the specified sample; Based on the different similarities and the category labels of the comparison samples determined in the initial classification, the category labels of the samples to be classified are obtained, specifically including: Determine the category labels that appear in the comparison sample, and the number of occurrences of each category label that appears; Among all the category labels, the category label with the least number of occurrences is selected as the category label of the sample to be classified. The method according to claim 1, wherein a plurality of The prior samples are reclassified, including: For each priori sample, select the nearest K classified samples from the classified samples as comparison samples; Determine the category labels that appear in the comparison sample, and the number of occurrences of each category label that appears; Among all the category labels, the category label with the least number of occurrences is selected as the category label obtained after the prior sample is reclassified. The method according to claim 1, wherein after determining the sample set to be clustered, the method further comprises: Determining a sample capacity corresponding to the sample set; The corresponding K value and the number of selected samples in the classification process are determined according to the sample capacity, wherein the ratio range of the K value to the sample capacity is a positive integer within [0.03, 0.09], the K value is an odd number, and the number of selected samples is higher than the maximum value of the K value selection range. The method according to claim 1, wherein selecting K prior samples closest to the sample to be classified as comparison samples specifically comprises: Calculate the distance between the sample to be classified and all other prior samples according to the number of dimensions contained in each sample in the sample set; Select the K prior samples closest to each other as comparison samples. The method according to claim 4, wherein calculating the distance between the sample to be classified and all other prior samples specifically comprises: When the samples in the sample set are one-dimensional, the distance between the sample to be classified and the priori sample is obtained by d _i =| _xi - _x1 |, wherein d _i is the distance between the sample to be classified and the i-th priori sample, _xi is the coordinate of the i-th priori sample, and _x1 is the coordinate of the sample to be classified; When the samples in the sample set are two-dimensional, Obtaining the distance between the sample to be classified and the priori sample, wherein d _i is the distance between the sample to be classified and the i-th priori sample, (x _i , y _i ) is the coordinate of the i-th priori sample, and (x ₁ , y ₁ ) is the coordinate of the sample to be classified; When the samples in the sample set are three-dimensional, The distance between the sample to be classified and the priori sample is obtained, wherein d _i is the distance between the sample to be classified and the i-th priori sample, (xi _{, yi} , z _i ) is the coordinate of the i-th priori sample, and ( _x1 , _y1 , _z1 ) is the coordinate of the sample to be classified. A high entropy KNN clustering device based on post-correction, comprising: at least one processor; and, a memory communicatively coupled to the at least one processor; The memory stores instructions executable by the at least one processor, and the instructions are executed by the at least one processor so that the at least one processor can perform the following operations: Determine a sample set that needs to be clustered, and initialize classification for a number of designated samples in the sample set based on the same similarity; wherein, in a pre-acquired data set, select a number of data as the sample set, and the number of data includes product data; the designated samples are samples with identifiable characteristics, and the identifiable characteristics include excellent product quality and defective products; The sample that has completed the initialization classification is used as a priori sample, and for the remaining samples to be classified in the sample set except the priori sample, K priori samples that are closest to the samples to be classified are selected as comparison samples; K is a preset positive integer value; Based on the difference in similarity and the category labels of the comparison samples determined in the initial classification, the category labels of the samples to be classified are obtained until all the samples to be classified are classified; Based on the difference in similarity, several prior samples are reclassified so that the proportion of product quality in each cluster finally obtained meets the preset proportion; Initializing classification for a number of designated samples in the sample set based on the same similarity, specifically including: Determining a number of designated samples that have been selected from the sample set; For each specified sample, select the K samples closest to the specified sample, and use the category label with the largest number of occurrences among the K samples as the category label of the specified sample; Based on the difference in similarity, and the category label determined by the comparison sample in the initial classification Label, and obtain the category label of the sample to be classified, specifically including: Determine the category labels that appear in the comparison sample, and the number of occurrences of each category label that appears; Among all the category labels, the category label with the least number of occurrences is selected as the category label of the sample to be classified. A non-volatile computer storage medium storing computer executable instructions, wherein the computer executable instructions are configured to: Determine a sample set that needs to be clustered, and initialize classification for a number of designated samples in the sample set based on the same similarity; wherein, in a pre-acquired data set, select a number of data as the sample set, and the number of data includes product data; the designated samples are samples with identifiable characteristics, and the identifiable characteristics include excellent product quality and defective products; The sample that has completed the initialization classification is used as a priori sample, and for the remaining samples to be classified in the sample set except the priori sample, K priori samples that are closest to the samples to be classified are selected as comparison samples; K is a preset positive integer value; Based on the difference in similarity and the category labels of the comparison samples determined in the initial classification, the category labels of the samples to be classified are obtained until all the samples to be classified are classified; Based on the difference in similarity, several prior samples are reclassified so that the proportion of product quality in each cluster finally obtained meets the preset proportion; Initializing classification for a number of designated samples in the sample set based on the same similarity, specifically including: Determining a number of designated samples that have been selected from the sample set; For each specified sample, select the K samples closest to the specified sample, and use the category label with the largest number of occurrences among the K samples as the category label of the specified sample; Based on the different similarities and the category labels of the comparison samples determined in the initial classification, the category labels of the samples to be classified are obtained, specifically including: Determine the category labels that appear in the comparison sample, and the corresponding Number of occurrences; Among all the category labels, the category label with the least number of occurrences is selected as the category label of the sample to be classified.