You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@metron.apache.org by cestella <gi...@git.apache.org> on 2017/12/15 23:34:12 UTC
[GitHub] metron pull request #872: METRON-1366: Add an entropy stellar function
GitHub user cestella opened a pull request:
https://github.com/apache/metron/pull/872
METRON-1366: Add an entropy stellar function
## Contributor Comments
Trending entropy for various volumetric statistics (e.g. netflow data) has been a useful metric for intrusion detection (see http://www.cs.bu.edu/techreports/pdf/2005-002-anomaly-mining.pdf). To wit, it makes some sense to add an entropy calculation for Stellar. Used in conjunction with the profiler and an outlier detector, we can recreate the work of Lakhina referenced above.
You can validate this from the REPL:
* `IT_ENTROPY({ 'a' : 10, 'b' : 5, 'c' : 5} )` should yield `1.5`
* By the definition of Entropy: `H(X) = -p(a)*log_2(p(a)) - p(b)*log_2(p(b)) - p(c)*log_2(p(c)) = -0.5*-1 - 0.25*-2 - 0.25*-2 = 1.5`
* `IT_ENTROPY({})` should yield `0.0`
## Pull Request Checklist
Thank you for submitting a contribution to Apache Metron.
Please refer to our [Development Guidelines](https://cwiki.apache.org/confluence/pages/viewpage.action?pageId=61332235) for the complete guide to follow for contributions.
Please refer also to our [Build Verification Guidelines](https://cwiki.apache.org/confluence/display/METRON/Verifying+Builds?show-miniview) for complete smoke testing guides.
In order to streamline the review of the contribution we ask you follow these guidelines and ask you to double check the following:
### For all changes:
- [x] Is there a JIRA ticket associated with this PR? If not one needs to be created at [Metron Jira](https://issues.apache.org/jira/browse/METRON/?selectedTab=com.atlassian.jira.jira-projects-plugin:summary-panel).
- [x] Does your PR title start with METRON-XXXX where XXXX is the JIRA number you are trying to resolve? Pay particular attention to the hyphen "-" character.
- [x] Has your PR been rebased against the latest commit within the target branch (typically master)?
### For code changes:
- [x] Have you included steps to reproduce the behavior or problem that is being changed or addressed?
- [x] Have you included steps or a guide to how the change may be verified and tested manually?
- [x] Have you ensured that the full suite of tests and checks have been executed in the root metron folder via:
```
mvn -q clean integration-test install && build_utils/verify_licenses.sh
```
- [x] Have you written or updated unit tests and or integration tests to verify your changes?
- [x] If adding new dependencies to the code, are these dependencies licensed in a way that is compatible for inclusion under [ASF 2.0](http://www.apache.org/legal/resolved.html#category-a)?
- [ ] Have you verified the basic functionality of the build by building and running locally with Vagrant full-dev environment or the equivalent?
### For documentation related changes:
- [x] Have you ensured that format looks appropriate for the output in which it is rendered by building and verifying the site-book? If not then run the following commands and the verify changes via `site-book/target/site/index.html`:
```
cd site-book
mvn site
```
#### Note:
Please ensure that once the PR is submitted, you check travis-ci for build issues and submit an update to your PR as soon as possible.
It is also recommended that [travis-ci](https://travis-ci.org) is set up for your personal repository such that your branches are built there before submitting a pull request.
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/cestella/incubator-metron entropy
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/metron/pull/872.patch
To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:
This closes #872
----
commit d4494854e482e2532f707b28ef2f891d13e129f3
Author: cstella <ce...@gmail.com>
Date: 2017-12-15T23:25:50Z
Added entropy function.
----
---
[GitHub] metron pull request #872: METRON-1366: Add an entropy stellar function
Posted by cestella <gi...@git.apache.org>.
Github user cestella commented on a diff in the pull request:
https://github.com/apache/metron/pull/872#discussion_r160532240
--- Diff: metron-analytics/metron-statistics/src/main/java/org/apache/metron/statistics/informationtheory/InformationTheoryUtil.java ---
@@ -0,0 +1,52 @@
+/*
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ */
+package org.apache.metron.statistics.informationtheory;
+
+import java.util.Map;
+
+public enum InformationTheoryUtil {
+ INSTANCE;
+ private static final double LOG2 = Math.log(2);
+
+ public double entropy(Map<?, Integer> counts, double logOfBase) {
+ double ret = 0.0;
+ int n = 0;
+ if(counts == null || counts.isEmpty()) {
+ return ret;
+ }
+ for(Integer f : counts.values()) {
+ n+=f;
+ }
+
+ for(Integer f : counts.values()) {
+ double p = f.doubleValue()/n;
+ ret -= p * Math.log(p) / logOfBase;
+ }
+ return ret;
+ }
+
--- End diff --
This is super cool, I actually looked at how this might impact performance as a PR against your repo [here](https://github.com/ottobackwards/stream_entropy/pull/1)
---
[GitHub] metron pull request #872: METRON-1366: Add an entropy stellar function
Posted by ottobackwards <gi...@git.apache.org>.
Github user ottobackwards commented on a diff in the pull request:
https://github.com/apache/metron/pull/872#discussion_r157332057
--- Diff: metron-analytics/metron-statistics/src/main/java/org/apache/metron/statistics/informationtheory/InformationTheoryUtil.java ---
@@ -0,0 +1,52 @@
+/*
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ */
+package org.apache.metron.statistics.informationtheory;
+
+import java.util.Map;
+
+public enum InformationTheoryUtil {
+ INSTANCE;
+ private static final double LOG2 = Math.log(2);
+
+ public double entropy(Map<?, Integer> counts, double logOfBase) {
+ double ret = 0.0;
+ int n = 0;
+ if(counts == null || counts.isEmpty()) {
+ return ret;
+ }
+ for(Integer f : counts.values()) {
+ n+=f;
+ }
+
+ for(Integer f : counts.values()) {
+ double p = f.doubleValue()/n;
+ ret -= p * Math.log(p) / logOfBase;
+ }
+ return ret;
+ }
+
--- End diff --
for giggles
```java
public double stream_entropy(Map<?, Integer> counts, double logOfBase) {
double ret = 0.0;
if (counts == null || counts.isEmpty()) {
return ret;
}
final int n = counts.values().stream().mapToInt((d) -> d).sum();
return counts.values().stream().collect(reducing(0.0, (f) -> f.doubleValue(), (a, b) -> {
double p = b.doubleValue() / n;
a -= p * Math.log(p) / logOfBase;
return a;
}));
}
```
---
[GitHub] metron pull request #872: METRON-1366: Add an entropy stellar function
Posted by asfgit <gi...@git.apache.org>.
Github user asfgit closed the pull request at:
https://github.com/apache/metron/pull/872
---
[GitHub] metron issue #872: METRON-1366: Add an entropy stellar function
Posted by justinleet <gi...@git.apache.org>.
Github user justinleet commented on the issue:
https://github.com/apache/metron/pull/872
+1. Thanks for the contribution, this is valuable to have.
---
[GitHub] metron pull request #872: METRON-1366: Add an entropy stellar function
Posted by ottobackwards <gi...@git.apache.org>.
Github user ottobackwards commented on a diff in the pull request:
https://github.com/apache/metron/pull/872#discussion_r157332543
--- Diff: metron-analytics/metron-statistics/src/main/java/org/apache/metron/statistics/informationtheory/InformationTheoryUtil.java ---
@@ -0,0 +1,52 @@
+/*
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ */
+package org.apache.metron.statistics.informationtheory;
+
+import java.util.Map;
+
+public enum InformationTheoryUtil {
+ INSTANCE;
+ private static final double LOG2 = Math.log(2);
+
+ public double entropy(Map<?, Integer> counts, double logOfBase) {
+ double ret = 0.0;
+ int n = 0;
+ if(counts == null || counts.isEmpty()) {
+ return ret;
+ }
+ for(Integer f : counts.values()) {
+ n+=f;
+ }
+
+ for(Integer f : counts.values()) {
+ double p = f.doubleValue()/n;
+ ret -= p * Math.log(p) / logOfBase;
+ }
+ return ret;
+ }
+
--- End diff --
https://github.com/ottobackwards/stream_entropy
---
[GitHub] metron issue #872: METRON-1366: Add an entropy stellar function
Posted by cestella <gi...@git.apache.org>.
Github user cestella commented on the issue:
https://github.com/apache/metron/pull/872
@justinleet I think that was just an alternative implementation with streams rather than explicit loops. I interpreted it as not a suggested change, but a cool new way to compute entropy.
---
[GitHub] metron issue #872: METRON-1366: Add an entropy stellar function
Posted by justinleet <gi...@git.apache.org>.
Github user justinleet commented on the issue:
https://github.com/apache/metron/pull/872
@cestella Any response to the comment by @ottobackwards ? I glanced over it, and I like it and think it's valuable, but he's hitting at the core impl, so I don't want to +1 anything.
---
[GitHub] metron issue #872: METRON-1366: Add an entropy stellar function
Posted by mmiklavc <gi...@git.apache.org>.
Github user mmiklavc commented on the issue:
https://github.com/apache/metron/pull/872
Nice addition! +1 from me as well, via inspection.
---