In various embodiments, a device classification service forms a device cluster by applying clustering to attributes of endpoint devices observed in one or more networks. The device classification service applies an initial device classification rule to the endpoint devices in the device cluster, based on one or more of the endpoint devices in the device cluster matching the initial device classification rule. The device classification service computes metrics for the initial device classification rule that quantify how well the attributes of the endpoint devices in the device cluster match the initial device classification rule. The device classification service decides, based on the metrics, whether to associate the initial device classification rule with the device cluster or generate a new device classification rule based on the device cluster.