With the development of regional health information sharing services, an increasing number of patient records are released. However, the adversary can infer the patient’s privacy information through the patient’s attributes, thereby causing the patient’s privacy leakage. Based on the above requirements, a privacy protection data publishing algorithm based on KD tree is proposed. By the properties of KD-tree, the generalized value of each attribute is decomposed until the generalized value of all attributes cannot be decomposed to ensure that the generalized value of all attributes of each leaf node is minimized to reduce the information loss. During the decomposition of equivalent tuple attributes, the number of sensitive attribute values for each node is made to be a diversity constraint to reduce the risk of privacy leakage. The experimental results show that this scheme can reduce the risk of leakage of privacy, and information loss.